Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
Вот здесь я положил алгоритм, написанный мною пол-года назад и за прошедшее время протестированный. Тот алгоритм один из первых по этой теме, я профессионально занимаюсь определением позиций на карте. Вернее принадлежностью позиций какой-либо оласти. В настоящее время он разросся малость, но основная идея та же. Прошу рассмотрению глубокоуважаемой аудитории форума.
2 мар 05, 20:08    [1357897]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Alexey Sh
Member

Откуда: SPB
Сообщений: 1930
Вершина (1,0) - не принадлежит многоугольнику, а (1,1) - принадлежит,
разобраться бы надо.


(NOT(NOT((@Y > s1.Y) AND (@Y <= s.Y))
AND ((@Y > s1.Y) OR (@Y <= s.Y))))
эквивалентно, если я не ошибся,
(@Y > s1.Y) AND (@Y <= s.Y) OR (@Y<=s1.Y) AND (@Y>s.Y)
2 мар 05, 21:10    [1357962]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
к сожалению, функция определена только внутри многоугольника. На границах не определена. Для этого надо юнионом дописывать принадлежность к границе. Это то, о чем я говорил в "разросшести". Но принадлежность границе вызывает не такой интерес. Граница описывается уравнениями прямой.
2 мар 05, 21:14    [1357970]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
то, что Вы написали, это (@Y > s1.Y) XOR (@Y <= s.Y) не знаю, ошиблись ли Вы или нет, не стану проверять. XOR в SQL вроде нет, потому, то выражение пришлось выводить... а у XOR несколько вариантов представления.
2 мар 05, 21:17    [1357973]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Alexey Sh
Member

Откуда: SPB
Сообщений: 1930
Мой легче читается и в нём меньше операций :)
2 мар 05, 21:22    [1357978]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
Alexey Sh
Мой легче читается и в нём меньше операций :)


если настаиваете, я проверю :)
2 мар 05, 21:24    [1357981]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
Alexey Sh
хм, на тестовых данных похоже похоже на правду... прокручу на мировой карте :)
2 мар 05, 21:29    [1357985]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Partisan M
Member

Откуда:
Сообщений: 1396
Думаю, лучше сделать расширенную хранимую процедуру на С++ - для неё достаточно будет более простого SQL запроса для молучения массива координат. Значит, должно работать быстрее. Хотя это предположение, но если б было нужно для работы, то я бы его проверил. Если что-то можно сделать на SQL, то это ещё не значит, что нужно.
2 мар 05, 21:31    [1357990]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Alexey Sh
Member

Откуда: SPB
Сообщений: 1930
Сколько вершин на многоугольниках мировой карты?
2 мар 05, 21:32    [1357991]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
Alexey Sh
у меня карт около 300... это регионы мирового океана.
Partisan M
не соглашусь. Отбор из таблицы позиций с проверкой через эту функцию у меня происходит не медленнее, чем просто отбор по другим критериям. Это, конечно, при правильно настроенных индексах
2 мар 05, 21:35    [1357997]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
Alexey Sh

по поводу вершин.... зависит от конкретного района... на вскидку до 300, примерно
2 мар 05, 21:37    [1357999]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Alexey Sh
Member

Откуда: SPB
Сообщений: 1930
Сколько точек на береговой линии?
2 мар 05, 21:38    [1358001]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
В основном мы занимаемся промысловыми районами, смотрим за позициями судов. Про береговую линию ничего не скажу. Может, координатами берега кто сможет поделиться?
2 мар 05, 21:42    [1358007]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
кстати, с картой еще есть одна неприятность: переход долготы со 180 на -180 ... но это проблема уже другой функции.
2 мар 05, 21:44    [1358009]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Alexey Sh
Member

Откуда: SPB
Сообщений: 1930
300 - что-то маловато. Интересно как это будет шевелиться на нескольких десятках тысяч
2 мар 05, 21:54    [1358023]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Alexey Sh
Member

Откуда: SPB
Сообщений: 1930
Поделиться берегом не могу, лет 20 назад занимался.
2 мар 05, 21:57    [1358030]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
10365

6 секунд, если просматривать все 288 зон и пропускать их через функцию исправления 180 -180, если отбирать при этом позиции судов из таблицы позиций, то 7 секунд. Но обычно интересует конкретный набор зон и там редко приходится обрабатывать 180 -180.... другими словами... выборка из таблицы позиций когда происходит данные отбираются быстрее обычно, если их отфильтровывать конкретно заданными зонами
2 мар 05, 22:01    [1358035]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
из 10000 позиций (среднесуточная цыфирь), данные по району северной атлантики отбираются в среднем за 6-10 секунд
2 мар 05, 22:05    [1358041]     Ответить | Цитировать Сообщить модератору
 Re: Функция по определению принадлежности точки многоугольнику  [new]
Shurgenz
Member

Откуда: Питер
Сообщений: 1938
я не сказал еще о том, что по плану выполнения функция моя занимает при этом менее 10 процентов.... остальное - обвязка и причесывание, обвешивание справочниками и прочая спицифическая ерунда
2 мар 05, 22:10    [1358046]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить