Есть ли способ быстрее найти многоугольник заданной точки?

Question

У меня есть Мультиполигон некоторых городов страны. По заданной точке хочу проверить, в каком городе она находится. (Мы можем предположить, что каждая заданная точка находится в этой стране, поэтому она находится ровно в одном городе.)

Один из подходов - перебрать каждый многоугольник и проверить, лежит ли точка в этом многоугольнике с помощью Point-in-Polygon. алгоритмы. Но поскольку у меня может быть много точек, а алгоритмы Point-in-Polygon имеют сложность не менее O (n), это не подходящий способ.

Поэтому мне нужен подходящий алгоритм для этой проблемы со следующими предположениями:

• Каждая точка находится ровно в одном городе.
• Границы города фиксированы и не меняются каждый раз.

Какой алгоритм можно использовать для эта проблема?

Answer 1

Point-in-Polygon мне кажется нужным. Но чтобы ускорить ваш алгоритм, разделите пространство сеткой. У вас может быть квад, который кодирует город, и квад, который находится внутри города, чтобы ускорить ваше обнаружение. Только если точка находится внутри внешнего четырехугольника, а не внутри внутреннего четырехугольника, используйте point-in-poly al go. Квадратные деревья, предложенные Мехди, могут быть реализованы очень быстро. Но лучшим решением, вероятно, является отображение на сетку, как описано ниже, вы получите решение O (1) :

Вероятно, вы также можете ускорить алгоритм PIP, разбивая многоугольник на мозаику.

С соответствующей функцией округления вы можете использовать координаты своей точки в качестве индексов для двумерного массива и определить в O (1) , находится ли он в конкретном городе, если нет. в городе или если требуется дальнейшее исследование.

Пример: точка (3,4560, 5,1547) Сетка 10x10. City1 - это (3,4), (3,5) граница City1 пересекает (3,3), (4,3), (4,4), (4,5), (4,6), (3, 6), (2,6), (2,5), (2,4), (2,3). Округляя точку до целых чисел, вы получаете 3,5, которые можно использовать в качестве индексов для матрицы, которая будет в Mat (3,5) = C1, где C1 означает City1. Вы можете использовать этот трюк с географическими координатами с произвольно выбранным разрешением.

формула для сопоставления координаты с индексом массива:

Coordinate c in [a,b] 
array index i in [0,n-1]
i = floor( (c-a) / ((b-a)/n) )

Answer 2

Вы можете получить значительное ускорение, работая над проекцией геометрии на вертикальную ось. Каждый многоугольник вырождается в сегмент, который вы можете вставить в дерево сегментов https://en.wikipedia.org/wiki/Segment_tree. Затем со временем запроса O (log (N) + K) вы сообщите о K многоугольниках, пересеченных прямой линией через точку.

Если многоугольники не слишком большие, вы можете ожидать уменьшения количество проверяемых многоугольников от N до √N (примерно).

Может быть полезно выполнить этот процесс также и на оси X и обработать только многоугольники, общие для обоих списков результатов. Таким образом, вы будете проверять включение только тех многоугольников, которые имеют ограничивающую рамку вокруг тестовой точки.