Быстрый алгоритм для поиска тысяч точек в миллионах полигонов?

Question

Я попытался узнать тысячи точек в миллионе полигона через веб-службы. Сначала я реализовал алгоритм (Point in polygon) в java, но это занимает много времени. Затем я разбил таблицу в mysql и попытался использовать несколько потоков для его решения, но все же неэффективно. Есть ли более быстрый алгоритм или реализация для решения этой проблемы?

Плюс описание многоугольника. 2D, статический, сложный многоугольник (также с отверстием).

Любое предложение будет оценено.

Answer 1

I thik здесь, где деление и победа будут делать, вы могли бы попытаться сделать субполионы или упростить некоторые из плутов, возможно, попытайтесь использовать эвристический подход, есть мои 5 центов.

Answer 2

Тестирование точки против миллиона полигонов займет много времени, независимо от того, насколько эффективна ваша точка в функции многоугольника.

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

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

Answer 3

Если сбор полигонов является статическим, может быть полезно сначала зарегистрировать их в пространственной структуре данных - R-tree может быть хорошим выбором, если предположить, что многоугольники не слишком много перекрывают друг друга.

Чтобы проверить точку на коллекцию многоугольника, сначала будет найдена закрывающая листка в дереве (операция стиля O(log(n))), и тогда потребуется только выполнить полный тест «точка-в-полигоне» для полигонов, которые связанных с закрывающим листом.

Этот подход должен значительно ускорить каждый точечный тест, но для создания R-дерева требуется дополнительная настройка.

Надеюсь, это поможет.

Answer 4

Если вы имеете дело с миллионами полигонов, вам нужно какое-то разделение пространства, или оно будет медленным, независимо от того, насколько оптимизирована ваша функция проверки результатов или сколько потоков работает при решении вашего запроса.

Какое разделение пространства? зависит от:

• 2D? 3D?
• Установлен ли ваш полигон статическим? Если нет, часто ли это меняет?
• Какая просьба вы делаете на этом наборе?
• Что это за полигон? Треугольник? Выпуклые? Вогнутые? Сложный? С отверстиями?

Нам нужна дополнительная информация, чтобы помочь вам.

EDIT

Вот простая схема пространственного разделения.

Предположим, что на вашем двумерном пространстве есть декартова сетка с заданным шагом.

При добавлении многоугольника:

• вычислит его ограничительная рамку
• Найти все ячейки сетки, которые пересекаются с ограничивающим параллелепипедом
• Для каждой ячейки, добавьте строку в специальной таблице.

таблица выглядит следующим образом: cell_x, cell_y, polygon_id. Добавьте соответствующие индексы (по крайней мере cell_x и cell_y)

Конечно, вы хотите, чтобы выбрать шаг сетки так, большинство полигонов лежали в менее чем 10 клеток, или же ваша ячейка таблица быстро становится огромной.

Теперь легко найти многоугольники в данной точке:

• Compute, в котором клетка ваша точка принадлежит
• Получить все полигоны, связанные с этой ячейкой
• Для каждого полигона, используйте hit- контрольная функция

Это решение далеко не оптимально, но легко реализуется.