powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Задачка !!!
11 сообщений из 11, страница 1 из 1
Задачка !!!
    #32017294
Alex Y
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Привет Всем!

Есть следующая задачка.
В таблице хранятся идентификатор контура ID и координаты точек для этих контуров X и Y.
Нужно написать процедуру (входные параметры ID1 и ID2), в которой бы происходила проверка
прнадлежит ли контур ID1 контуру ID2.

Какие будут идеи?
...
Рейтинг: 0 / 0
Задачка !!!
    #32017296
Glory
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
"принадлежит ли контур ID1 контуру ID2" - означает ли это что количество и коодинаты ВСЕХ точек обеих контуров должны совпадать, или у какого-либо из контуров может быть меньше/больше точек ?
...
Рейтинг: 0 / 0
Задачка !!!
    #32017307
Alex Y
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Количество точек в обоих контурах произвольно.
Контур ID1 полностью входит в ID2 если все точки ID1 принадлежат области, образуемой точками контура ID2.
...
Рейтинг: 0 / 0
Задачка !!!
    #32017318
Glory
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хм, мне кажется что для каждой точки контура должен быть какой-то порядковый номер. Иначе как вы определяете, что 2 конкретные точки контура яляются соседними точками, т.е. являются гранью контура?
...
Рейтинг: 0 / 0
Задачка !!!
    #32017321
Alex Y
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Хорошо, добавим поле NPoint - № точки. По неообходимости можно добавить другие поля.
Главное идея реализации.
...
Рейтинг: 0 / 0
Задачка !!!
    #32017328
Pandre
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Если нужна идея, то предлагается следующее.
1. Дополнительное условие на контур - выпуклый и последовательность точек задается в одном направлении обхода (например, против часовой точки)
2. В этом случае условие того, что какая либо точка лежит внутри контура - это то, что она расположена слева от всех прямых соединяющих ключевые точки, если смотреть от первой точки ко второй.
3. Если все точки второго контура находятся внутри первого, то весь второй контур лежит внутри первого.
...
Рейтинг: 0 / 0
Задачка !!!
    #32017335
Glory
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Предложу такой вариант
- контур(фигура) определяется количеством точек, соединенных отрезками. Т.е. сложный контур(фигура), например, тот же круг - это много точек(в зависимости от точности), но все равно соединенных отрезками.

- каждая точка контура имеет номер и соединена только с 2 соседними точками(номер+1 и номер-1)

Тогда

--таблица контуров
create table #figure(figure_id int, point_nr int, x int, y int)

--1-st figure
insert #figure values(1, 1, 1, 1)
insert #figure values(1, 2, 1, 10)
insert #figure values(1, 3, 15, 10)
insert #figure values(1, 4, 10, 1)

--2-nd figure
insert #figure values(2, 1, 2, 2)
insert #figure values(2, 2, 7, 7)
insert #figure values(2, 3, 5, 4)

--3-rd figure
insert #figure values(3, 1, 6, 3)
insert #figure values(3, 2, 9, 9)
insert #figure values(3, 3, 12, 7)

--4-th figure
insert #figure values(4, 1, 1, 20)
insert #figure values(4, 2, 5, 25)
insert #figure values(4, 3, 10, 20)

declare @id1 int, @id2 int
set @id1 = 1
set @id2 = 2


--вычисляем все отрезки для контура ID1
--1. отрезок от последней точки контура к первой вычисляем отдельно
select TOP 1 a.x as x11, a.y as y11, 0 as x12, 0 as y12 into #temp1 from #figure a where a.figure_id = @id1 order by a.point_nr desc
UPDATE #temp1 SET x12=a.x, y12=a.y from (select top 1x, y from #figure where figure_id = @id1 order by point_nr asc) AS a

--2. вычисляем все остальные отрезки для контура ID1
insert #temp1 select a.x, a.y, b.x, b.y
from #figure a inner join #figure b on b.figure_id = a.figure_id and b.point_nr = (a.point_nr + 1)
where a.figure_id = @id1

--3. для удобства в каждом отрезке точку с меньшей координатой по X располагаем левее
update #temp1 set
x11=case when x11 > x12 then x12 else x11 end,
x12=case when x11 > x12 then x11 else x12 end,
y11=case when x11 > x12 then y12 else y11 end,
y12=case when x11 > x12 then y11 else y12 end


-- все эти же шаги выполняем для контура ID2
-- 1.
select TOP 1 a.x as x21, a.y as y21, 0 as x22, 0 as y22 into #temp2 from #figure a where a.figure_id = @id2 order by a.point_nr desc
UPDATE #temp2 SET x22=a.x, y22=a.y from (select top 1 x, y from #figure where figure_id = @id2 order by point_nr asc) AS a

--2.
insert #temp2 select a.x, a.y, b.x, b.y
from #figure a inner join #figure b on b.figure_id = a.figure_id and b.point_nr = (a.point_nr + 1)
where a.figure_id = @id2

--3.
update #temp2 set
x21=case when x21 > x22 then x22 else x21 end,
x22=case when x21 > x22 then x21 else x22 end,
y21=case when x21 > x22 then y22 else y21 end,
y22=case when x21 > x22 then y21 else y22 end

--основная идея в том, что ни один отрезок из контура ID2 не должен пересекать ни одни отрезок из контура ID1
select *, case when x12 > x21 and x11 < x22 and y12 > y21 and y11 < y22 then 1 else 0 end as catch_you from #temp1 a, #temp2 b
order by x11, y11, x12, y12


Остается выяснить не лежит ли второй контур полностью снаружи первого контура. Можно попробовать такой вариант - никакой отрезок, соединющий любые точки из ID1 не должен пересекать ни один отрезок, составляющий контур ID2.

Вот приблизительно моя идея

PS
Вполне возможно (и даже скорее всего) в математике есть более оптимальные алгоритмы.
...
Рейтинг: 0 / 0
Задачка !!!
    #32017350
Владимир Смирнов
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По поводу алгоритма могу посоветовать сайт http://alglib.dore.ru/
В отношении реализации на SQL сервере - думаю лучше сделать это в клиентском приложении.
...
Рейтинг: 0 / 0
Задачка !!!
    #32017373
Фотография Garya
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Решал я такую задачку в глубокой древности. Дам основные идеи. Полагаю, если с математикой знаком, остальное сам дотумкаешь.

Один контур находится внутри другого, если все точки, которыми задана ломанная контура находятся внутри этого контура. И одновременно отсутствуют пересечения отрезков двух контуров.

По части пересечения отрезков проблем нет - находишь точку пересечения двух прямых, образуемых парами точек и определяешь, находятся ли координаты точки перечения в диапазоне координат одного из отрезков.

Далее для решения задачи необходимо научиться определять, находится ли точка с заданными координатами внутри контура или снаружи. При этом следует учесть, что контур совсем не обязательно должен быть выпуклым (то есть, точка может находиться "в заливе" ("в бухте") контура и быть коружена выступами контура, но при этом быть вне контура.
Принимаешь оговоренную точку за начало вектора, конец которого должен последовательно пройти по вершинам контура и, описав замнкутую траекторию, вернуться в исходную точку. Направление обхода значения не имеет. При обходе вектор закрашивает сектор в системе координат X/Y при проходе между двумя соседними точками. Угол, образуемый сектором принимает положительное значение при движении против часовой стрелки и отрицательные в обратном направлении. Проблем с просчетом угла, описываемого вектором, не возникает. При проходе конца вектора по одному отрезку ломанной контура максимальное его значение - 180 градусов (если точка лежит на самом отрезке). По координатам концов отрезка ломанной (с учетом порядка их следования) и точки, положение которой относительно контура нужно определяешь величину угла, описываемого вектором с учетом знака этого угла.
Если сложить все углы, закрашиваемые последовательно вектором при проходе по узлам ломанной, то получишь либо +360 градусов, либо -360 градусов, либо 0. Если сумма описываемых вектором углов равна плюс или минус 360 градусов - значит точка внутри контура (плюс или минус - зависит от направления прохода по контуру). Если 0 - значит вне контура.
Надеюсь, помог.
...
Рейтинг: 0 / 0
Задачка !!!
    #32017386
Alex Y
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Garya.
Алгоритм супер, но хотелось бы переложить его на SQL.

Я прошу прощения за назойливость, но хочу усложнить немного задачу.

Теперь пусть одна фигура состоит из нескольких полигонов и представлена следующим образом:
ID - код фигуры
NPol - номер полигона
NPoint - номер точки в полигоне
X - Координата X
Y - Координата Y

Если один полигон лежит внутри другого, то его считать как "дырку" и соответственно считать его область за пределами фигуры.
...
Рейтинг: 0 / 0
Задачка !!!
    #32017718
Фотография Garya
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну и какие проблемы? Алгоритм есть. Или ты хочешь, чтобы я и программу написал?
И еще. Тут уже прозвучала мысль, что SQL-сервер не совсем подходящий инструмент для вычисления синусов и косинусов. И я ее полностью поддерживаю. Рекомендую делать нужные выбоорки координат на клиент, и нужные расчеты производить на нем.
...
Рейтинг: 0 / 0
11 сообщений из 11, страница 1 из 1
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Задачка !!!
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]