Комментарии 25
Переписали критичный к скорости исполнения кусок кода на PHP, попрощавшись с C?? Поясните, пожалуйста, эту деталь.
определение принадлежности к региону – это только часть задачи, не было смысла систему разносить на 100 частей и писать на разных языках.
Если там была одна функция(или даже несколько), то можно попробовать сделать расширение для PHP при помощи swig.
Мне кажется вы изобрели велосипед.
Во-первых, ваш алгоритм можно еще улучшить, если по каждому полигону вместо выпуклого многоугольника строить описывающий прямоугольник (bounding box). Таким образом каждый регион в упрощенном виде станет набором из двух координат (противоположный углов прямоугольника), допустим это будет левый нижний угол и правый верхний ((x1, y1) (x2, y2)), таким образом логика поиска попадания точки в такой прямоугольник будет совсем простая. Если координаты точки (xp, yp) то для попадания в прямоугольник необходимо проверить только то, что x1<=xp<=x2 и y1<=yp<=y2. Это должно значительно ускорить поиск. К тому же такой подход позволяет легко построить индекс по таким прямоугольникам, что еще сильнее ускорит поиск;
Во-вторых, многие современные СУБД из коробки (или почти из коробки) поддерживают хранение и поиск пространственных данных. Благодаря нативному коду, построению индексов по пространственным данным и более совершенным алгоритмам эти решения будут на много порядков быстрее вашего. Например, на моей девелоперской машине Postgresql (с Postgis) определяет попадание точки в регион (все регионы имеют в совокупности более миллиона точек) за ~10мс;
В-третьих, даже без баз данных есть хорошо зарекомендовавшие себя готовые решение для различных манипуляций с геометрий. Одно из самых известных это GEOS;
Во-первых, ваш алгоритм можно еще улучшить, если по каждому полигону вместо выпуклого многоугольника строить описывающий прямоугольник (bounding box). Таким образом каждый регион в упрощенном виде станет набором из двух координат (противоположный углов прямоугольника), допустим это будет левый нижний угол и правый верхний ((x1, y1) (x2, y2)), таким образом логика поиска попадания точки в такой прямоугольник будет совсем простая. Если координаты точки (xp, yp) то для попадания в прямоугольник необходимо проверить только то, что x1<=xp<=x2 и y1<=yp<=y2. Это должно значительно ускорить поиск. К тому же такой подход позволяет легко построить индекс по таким прямоугольникам, что еще сильнее ускорит поиск;
Во-вторых, многие современные СУБД из коробки (или почти из коробки) поддерживают хранение и поиск пространственных данных. Благодаря нативному коду, построению индексов по пространственным данным и более совершенным алгоритмам эти решения будут на много порядков быстрее вашего. Например, на моей девелоперской машине Postgresql (с Postgis) определяет попадание точки в регион (все регионы имеют в совокупности более миллиона точек) за ~10мс;
В-третьих, даже без баз данных есть хорошо зарекомендовавшие себя готовые решение для различных манипуляций с геометрий. Одно из самых известных это GEOS;
насчет bounding box, действительно хорошая идея (использую, если будет нехватать скорости), насчет постгрес и других систем, это только небольшая часть проекта, переписать это мне показалось проще, чем интегрировать кучу инструментов.
Ну если вы уже используете в своем проекте СУБД, то возможно, что она поддерживает это функционал и от вас не потребуется установка дополнительного инструментария. Из распространенных СУБД, поддерживающих операции с пространственными данными мне известны: PostgresSQL, MySQL, MS SQL, Oracle, Sqlite, MongoDB
хм, да, использую MySQL — не знал о таком функционале, можно поподробнее для MySQL?
Можно. Ваша задача в MySQL будет решаться приблизительно так:
Взято отсюда: http://dev.mysql.com/doc/refman/5.1/en/functions-for-testing-spatial-relations-between-geometric-objects.html
mysql> SET @g1 = GeomFromText('Polygon((0 0,0 3,3 3,3 0,0 0))');
mysql> SET @g2 = GeomFromText('Point(1 1)');
mysql> SELECT MBRIntersects(@g1,@g2);
Взято отсюда: http://dev.mysql.com/doc/refman/5.1/en/functions-for-testing-spatial-relations-between-geometric-objects.html
На самом деле есть еще одна сложность – это анклавы (Москва лежит внутри Московской области, как и Питер, было решено использовать приоритеты, сначала проверяется лежит ли точка в Москве, а потом уже в Московской области)
Поясните, пожалуйста, в чем возникла сложность?
в том, что внутри области, например, Свердловская область. Есть кусочек другой области:
то есть нужно проставлять приоритеты обхода областей, в данном случае, точка, лежащая в этой области – определится как «Свердловская область», а на самом деле – это «Тюменская область»
то есть нужно проставлять приоритеты обхода областей, в данном случае, точка, лежащая в этой области – определится как «Свердловская область», а на самом деле – это «Тюменская область»
Мне кажется ещё оптимальнее для каждого региона определить его центр (центроид), затем при получение sy и sx отсортировать все регионы по расстоянию между центрами и sy, sx и начинать поиск с тех регионов которые ближе до первого вхождения региона каждого уровня.
Даже чисто влоб видно куда более оптимальное решение.
Делим всю карту на квадраты, строим из них QTree. Чем меньше квадрат — тем больше будет данных, но и тем быстрее отработается запрос.
Для каждого элемента QTree считаем и сохраняем, какие регионы в нём присутствуют. Дополнительно можно в него же сохранить границы регионов, предварительно обрезав их по границам квадрата.
Дальше оптимизируем QTree — в квадратах, у которых все четыре подквадрата относятся к одному региону — подквадраты прибиваем, ибо ни к чему.
В итоге получим qtree, плотность данных которого будет большой вдоль границ и низкой «внутри» регионов.
Ну а выборка тривиальна. Найти квадрат, включающий заданные координаты — копеечная операция. Дальше если в квадрате сходятся несколько регионов — то проверяем принадлежность к кускам границ квадрата — они небольшие и операция получится недолгая.
Никаких проблем с анклавами, можно хранить и проверять хоть весь земной шар с детализацией до района города — сложность выборки почти постоянна.
Делим всю карту на квадраты, строим из них QTree. Чем меньше квадрат — тем больше будет данных, но и тем быстрее отработается запрос.
Для каждого элемента QTree считаем и сохраняем, какие регионы в нём присутствуют. Дополнительно можно в него же сохранить границы регионов, предварительно обрезав их по границам квадрата.
Дальше оптимизируем QTree — в квадратах, у которых все четыре подквадрата относятся к одному региону — подквадраты прибиваем, ибо ни к чему.
В итоге получим qtree, плотность данных которого будет большой вдоль границ и низкой «внутри» регионов.
Ну а выборка тривиальна. Найти квадрат, включающий заданные координаты — копеечная операция. Дальше если в квадрате сходятся несколько регионов — то проверяем принадлежность к кускам границ квадрата — они небольшие и операция получится недолгая.
Никаких проблем с анклавами, можно хранить и проверять хоть весь земной шар с детализацией до района города — сложность выборки почти постоянна.
Код на PHP не выложите?
Ну во-первых я пишу не на php, а во-вторых если вы представите geo-координаты в виде целого числа с чередующимися битами координат (xyxyxyxy), то дальше всё будет тривиально, а задача разбиения на квадраты и поиска квадрата включающего заданную координату будет очень похожей на работу с таблицами ip-адресов. Т.е. да, у квадрата будет ещё битовая маска.
Само же раскидывание границ по квадратам и вообще геоданных по квадратам очень хорошо параллелится, неплохо ложится на map-reduce, а при большом желании даже загоняется на GPU.
Само же раскидывание границ по квадратам и вообще геоданных по квадратам очень хорошо параллелится, неплохо ложится на map-reduce, а при большом желании даже загоняется на GPU.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Точное определение региона по GPS координатам