Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Задачка !!!
|
|||
|---|---|---|---|
|
#18+
Привет Всем! Есть следующая задачка. В таблице хранятся идентификатор контура ID и координаты точек для этих контуров X и Y. Нужно написать процедуру (входные параметры ID1 и ID2), в которой бы происходила проверка прнадлежит ли контур ID1 контуру ID2. Какие будут идеи? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.11.2001, 06:25 |
|
||
|
Задачка !!!
|
|||
|---|---|---|---|
|
#18+
"принадлежит ли контур ID1 контуру ID2" - означает ли это что количество и коодинаты ВСЕХ точек обеих контуров должны совпадать, или у какого-либо из контуров может быть меньше/больше точек ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.11.2001, 06:53 |
|
||
|
Задачка !!!
|
|||
|---|---|---|---|
|
#18+
Количество точек в обоих контурах произвольно. Контур ID1 полностью входит в ID2 если все точки ID1 принадлежат области, образуемой точками контура ID2. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.11.2001, 08:20 |
|
||
|
Задачка !!!
|
|||
|---|---|---|---|
|
#18+
Хм, мне кажется что для каждой точки контура должен быть какой-то порядковый номер. Иначе как вы определяете, что 2 конкретные точки контура яляются соседними точками, т.е. являются гранью контура? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.11.2001, 09:23 |
|
||
|
Задачка !!!
|
|||
|---|---|---|---|
|
#18+
Хорошо, добавим поле NPoint - № точки. По неообходимости можно добавить другие поля. Главное идея реализации. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.11.2001, 09:59 |
|
||
|
Задачка !!!
|
|||
|---|---|---|---|
|
#18+
Если нужна идея, то предлагается следующее. 1. Дополнительное условие на контур - выпуклый и последовательность точек задается в одном направлении обхода (например, против часовой точки) 2. В этом случае условие того, что какая либо точка лежит внутри контура - это то, что она расположена слева от всех прямых соединяющих ключевые точки, если смотреть от первой точки ко второй. 3. Если все точки второго контура находятся внутри первого, то весь второй контур лежит внутри первого. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.11.2001, 11:12 |
|
||
|
Задачка !!!
|
|||
|---|---|---|---|
|
#18+
Предложу такой вариант - контур(фигура) определяется количеством точек, соединенных отрезками. Т.е. сложный контур(фигура), например, тот же круг - это много точек(в зависимости от точности), но все равно соединенных отрезками. - каждая точка контура имеет номер и соединена только с 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 Вполне возможно (и даже скорее всего) в математике есть более оптимальные алгоритмы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.11.2001, 12:23 |
|
||
|
Задачка !!!
|
|||
|---|---|---|---|
|
#18+
По поводу алгоритма могу посоветовать сайт http://alglib.dore.ru/ В отношении реализации на SQL сервере - думаю лучше сделать это в клиентском приложении. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.11.2001, 14:24 |
|
||
|
Задачка !!!
|
|||
|---|---|---|---|
|
#18+
Решал я такую задачку в глубокой древности. Дам основные идеи. Полагаю, если с математикой знаком, остальное сам дотумкаешь. Один контур находится внутри другого, если все точки, которыми задана ломанная контура находятся внутри этого контура. И одновременно отсутствуют пересечения отрезков двух контуров. По части пересечения отрезков проблем нет - находишь точку пересечения двух прямых, образуемых парами точек и определяешь, находятся ли координаты точки перечения в диапазоне координат одного из отрезков. Далее для решения задачи необходимо научиться определять, находится ли точка с заданными координатами внутри контура или снаружи. При этом следует учесть, что контур совсем не обязательно должен быть выпуклым (то есть, точка может находиться "в заливе" ("в бухте") контура и быть коружена выступами контура, но при этом быть вне контура. Принимаешь оговоренную точку за начало вектора, конец которого должен последовательно пройти по вершинам контура и, описав замнкутую траекторию, вернуться в исходную точку. Направление обхода значения не имеет. При обходе вектор закрашивает сектор в системе координат X/Y при проходе между двумя соседними точками. Угол, образуемый сектором принимает положительное значение при движении против часовой стрелки и отрицательные в обратном направлении. Проблем с просчетом угла, описываемого вектором, не возникает. При проходе конца вектора по одному отрезку ломанной контура максимальное его значение - 180 градусов (если точка лежит на самом отрезке). По координатам концов отрезка ломанной (с учетом порядка их следования) и точки, положение которой относительно контура нужно определяешь величину угла, описываемого вектором с учетом знака этого угла. Если сложить все углы, закрашиваемые последовательно вектором при проходе по узлам ломанной, то получишь либо +360 градусов, либо -360 градусов, либо 0. Если сумма описываемых вектором углов равна плюс или минус 360 градусов - значит точка внутри контура (плюс или минус - зависит от направления прохода по контуру). Если 0 - значит вне контура. Надеюсь, помог. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.11.2001, 18:49 |
|
||
|
Задачка !!!
|
|||
|---|---|---|---|
|
#18+
Garya. Алгоритм супер, но хотелось бы переложить его на SQL. Я прошу прощения за назойливость, но хочу усложнить немного задачу. Теперь пусть одна фигура состоит из нескольких полигонов и представлена следующим образом: ID - код фигуры NPol - номер полигона NPoint - номер точки в полигоне X - Координата X Y - Координата Y Если один полигон лежит внутри другого, то его считать как "дырку" и соответственно считать его область за пределами фигуры. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.11.2001, 01:52 |
|
||
|
Задачка !!!
|
|||
|---|---|---|---|
|
#18+
Ну и какие проблемы? Алгоритм есть. Или ты хочешь, чтобы я и программу написал? И еще. Тут уже прозвучала мысль, что SQL-сервер не совсем подходящий инструмент для вычисления синусов и косинусов. И я ее полностью поддерживаю. Рекомендую делать нужные выбоорки координат на клиент, и нужные расчеты производить на нем. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.11.2001, 17:33 |
|
||
|
|

start [/forum/topic.php?fid=46&msg=32017307&tid=1824862]: |
0ms |
get settings: |
7ms |
get forum list: |
10ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
45ms |
get topic data: |
7ms |
get forum data: |
2ms |
get page messages: |
30ms |
get tp. blocked users: |
1ms |
| others: | 252ms |
| total: | 358ms |

| 0 / 0 |
