Определение пренадлежности точки(координат её)

[iron]

Здравствуйте !
Необходима помощь.
Суть проблемы :
Есть интерактивная карта, на которую слоем наложены полигоны (области), необходимо определять принадлежит ли точка какому-то конкретному полигону.
Координаты точек описывающие полигон (его вершины) хранятся в БД.
Полигонов много, и необходима скорость обработки.

Заранее благодарен за ответ)

[iron]

Да, забыл сказать, средств отклика (например по клику на полигон) нету, карта визиком (хотя впринципе неважно),
хотелось бы узнать как можно быстро вычислить принадлежит ли точка какому либо полигону в БД(можно не в бд а например в многомерном массиве), и принадлежит ли вообще.
Буду рад любым подсказкам и помощи.

[Boris]

Теория говорит, что быстро определяется факт НЕ вхождения точки в полигон. Факт вхождения проверяется долго.

[bim2010]

Может и есть готовые решения. У меня задачка - более 6700 полигонов описываются ~ 800000 точками (politics84.dbf). Необходимо определить принадлежность 356000 (GNS.dbf) точек этим полигонам.
Я пока придумал следующее:
1. Для каждого полигона определяю его внешний ограничивающий квадрат.
Т.е. необходимо определить левую верхнюю и правую нижнюю координаты точки квадрата, в который вписывается полигон.
2. Строю индекс по координатам точек

Код: Выделить всё

INDEX ON STR(INT(long),16,8) TAG gns

умышленно округляя координату до целого.
Строю индекс по точкам полигона:

Код: Выделить всё

INDEX ON STR(objectid,9,0) TAG politics84

3. Делаю цикл по 6700 полигонам так, чтобы процедура переноса точек описывающих полигоны в массив, для дальнейшего определения принадлежности точки многоугольнику, выполнялась для одного полигона один раз.
4. Затем делаю цикл по базе из 356000 точек для определения принадлежности точек полигонам. При этом в начале, еще до цикла, делаю:

Код: Выделить всё

                    SEEK STR(INT(xmin_long),16,8)
                    IF FOUND()

При этом условие выхода из цикла :

Код: Выделить всё

	                    *  закончили работать в квадрате
                           IF INT(LONG)>INT(xmax_long)+1
                              EXIT
                           endif                           

Внутри цикла – для ускорения :
Проверяю только точки, принадлежащие внешнему ограничивающему квадрату п.1
Проверяю только точки, у которых в поле идентификатор полигона =0.
5. И только потом использую алгоритм проверки принадлежности точки многоугольнику.
http://algolist.manual.ru/maths/geom/belong/poly2d.php
Да, он не быстрый – последний пункт.
В результате в базе GNS.dbf у всех заполнено поле objected – идентификатор полигона.
Успеха !

[geologic]

То есть никакой пространственной среды, или библиотеки, вы не используете, и хотите решить задачу чисто математически, на плоскости, с нуля? Понятное дело, это изобретение велосипеда, хоть и интересное. Вы готовы к тому, что ваше решение будет заведомо плоским, без нужной гео-точности и без проекций? Возможно, оно не будет и быстрым в общем случае, механизмы перебора/сортировки/индексации - отдельная мат. задача.

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

Вообще скорость работы сильно зависит от точности координат, например, целочисленные системы намного быстрее. Они, правда, малоприемлемы для реальной географии, поскольку задают свою жесткую сетку, подобно гриду. Однако, если у вас экспресс-система, смело можете аппроксимировать ваши координаты. Это позволит не только подсократить трафик, но и алгоритмы заметно упростить. Например, в целочисленном варианте положение точки относительно полигона сложной формы - внутри или снаружи - считается просто кол-вом пересечений линии координаты точки (например, по X, неважно) и границы, если нечетное - точка внутри, если четное - снаружи. Притом сами пересечения, как можно догадаться, тоже находятся быстро, ведь линия в ЦЧС как бы состоит из отдельных "целочисленных точек", и можно перебором-индексированием к этому подкрасться. Почитайте вообще о целочисленных методах, мне всегда казалось, они весьма подходят именно для СУБД. Может показаться, что это слишком приблизительно, но если ваши целые числа - метры, может подойти.

Лучше бы, конечно, для таких дел библиотеками воспользоваться. Задачка только кажется тривиальной, но об нее немало зубов обломано.

[iron]

я с Вами полностью согласен ув. geologic , это изобретение велосипеда, до сих пор я просто математически расчитывал вхождение точки (методом направленного луча), приходилось перебирать всю БД и вычислять для каждого функцию.
я б хотел бы узнать может есть какойто инструмент (например в БД постгрескюэль, там же есть типы данных ПОЛИГОН и ФЛОАТ, или в мускуле тоже эти типы появились)
может еще как, всё равно я их в массив считываю из БД для работы...

посоветуйте, интересно, может уже есть хороший инструмент для этого

[bim2010]

viewtopic.php?f=26&t=3135&p=13682&hilit ... %83#p13682

Руководство по ГИС анализу
Энди Митчелл
Поиск объектов внутри области - стр 87

[iron]

Спасибо Ув. bim2010, за инфу. скачал, перечитал, повысил немного знания))
но это теория, а есть ли что поконкретее, с примерами...
Может способом со слоями, накладывать какойто объект совпадающий с полигоном который реагирует на события (для аджакс решений), или создать в БД таблицу соответствий по координатам (как их обобщить, и сделать чтобы добавлялись по мере необходимости)...

[bim2010]

Надо больше информации по Вашей задачке.
Вопросы:
1. В каком виде сейчас хранятся Ваши данные? Какой формат данных? Скажите хотя бы расширение файлов.
2. С какими форматами данных Вы умеете работать. Есть знания, в каком нибудь SQL или dbf или GIS форматы (шейпы, tab ...)?
3. Какая GIS у Вас установлена?
4. Какой у Вас объем данных? Приблизительно кол-во полигонов, точек ...
5. Вам необходимо эти вычисления выполнять в режиме on line? Или можно эти расчеты выполнить один раз, присвоить точкам коды полигонов и забыть?
6. Вам необходимо Web решение или desktop?
7.На каком языке?
Кстати мой пример, это маленький кусочек от задачки, которую можно назвать "Геокодирование".
viewtopic.php?f=3&t=3841
Время расчета моего примера 1час 42 минуты при включенном режиме трассировки (вывожу на экран выполнение).
Точек на самом деле больше 554000, нас.пунктов 356000
Т.е. время расчета одной точки 0.0104 секунды. Это много? Незнаю...

Лучше бы, конечно, для таких дел библиотеками воспользоваться. Задачка только кажется тривиальной, но об нее немало зубов обломано.

Кто бы спорил, конечно, это задачка для GIS.

[geologic]

Почему только для ГИС, в БД есть ряд библиотек - Oracle Spatial, например, целый язык гео-запросов, ну и среди свободных библиотек можно найти подходящие. Но вы правильно вопросы поставили, а то тема идет, а до сих пор неясно где, кому и зачем это все решать, т.е. на каком уровне. Самый нижний не заинтересовал, самый верхний - прямо в ГИС-среде - похоже, тоже не нравится... Что же тогда автору надо, какого типа?

[iron]

Спасибо что не потеряли интерес к теме,
наверное небольшие знания не давали мне поставить грамотно вопросы, но на помощь пришел bim2010

Теперь постараюсь все расписать:
1. В каком виде сейчас хранятся Ваши данные? Какой формат данных? Скажите хотя бы расширение файлов.

Хранятся данны е в географических а также локальных (для ГИС сервера) координатах в БД, в упакованном (пользовательская) виде, и при необходимости пересылаются на клиентскую часть где и распаковываются,
впринципе можно переделать под любой тип данных, для меня несущественно, если необходимо то переделаю, лишб бы задача решалась.
2. С какими форматами данных Вы умеете работать. Есть знания, в каком нибудь SQL или dbf или GIS форматы (шейпы, tab ...)?
Работаю с БД мускул и постгрес, но впринципе при наличии документации быстро осваиваю другие.
3. Какая GIS у Вас установлена?
Пользуюсь картой ВИЗИКОМа http://maps.visicom.ua/ (незнаю, может быть лучше свою ГИС поставить, инструментарий здесь оч.ограничен)
4. Какой у Вас объем данных? Приблизительно кол-во полигонов, точек ...
кол-во полигонов - измеряется сотнями тыс
5. Да в режиме онлайн.
6.У меня ВЭБ решение
7. Аякс (ява, пхп), мускул(постгрес, для меня неважно)

Если лучше поставить ГИС, то какую и как решать ?

Извиняюсь за настырность, но очень надо и ламер в ГИС.
А если кому что нужно в программировании - то помогу (знаю кучу языков прогр.)))

[Konstantin Tokar]

Я бы первым делом поставил PostgreSQL+PostGIS, не ниже 8.3, и использовал функцию within(). Кстати, с 8.3 она оптимизирована - сначала проверяет границы прямоугольника, а только потом честно проверяет полигон. Может, это тривиальное решение подойдёт сразу.

[iron]

Спасибо Konstantin Tokar а мануальчиками и ссылками неподелитесь)?

[bim2010]

По Вашей ссылке в основе реализация TMS протокол - пирамида из тайлов.
Там нет никаких баз...
http://tms0.visicom.ua/1.0.1/ukraine_ru/5/43/

Я с этого начал освоение Openlayers. Голый java - скрипт и ничего на сервере кроме сотен тысяч тайлов.

Ну а эта ссылка Вам знакома
http://alexrush.com/postgis

Он как раз к visicom имеет отношение.
И темы там интересные есть...

Если у Вас все же есть вектор visicom то следующий вопрос:
Какую CMS Вы предпочитаете?
Мне нравится вот эта сборка - комплект картографирования Mapping Kit
http://aardbodem.nl/?q=node/26
Drupal + OpenLayers и MapServer +PostgreSQl+PostGIS

Да и ответ на Ваш 1.вопрос:
тогда получается - pgrouting и библиотеки которые он использует
(Boost - это целый мир, ну просто математический клондайк)
http://pgrouting.postlbs.org/wiki

[iron]

Да, вы правы bim2010, но я использую еще обращение к их базе посредством XML-запросов, а также у меня своя БД на VPSе где и хранятся мои полигоны, точки, описания и прочая инфа, вот для них и надо мне вычисления проводить и отображать на слоях карты.
А ВИЗИКОМ или что то другое ... мне важна детализация карты Украины и в перспективе России.