Эффективный алгоритм поиска ближайших отрезков для каждой точки

Question

Учитывая многоугольное подразделение S и набор точек P, найдите ближайший линейный сегмент в S для каждой точки (в 2-мерном пространстве).
В моей настройке у меня есть сотни тысяч сегментов и паратысяча точек.

Проверка каждой строки для каждой точки займет слишком много времени.Есть ли эффективный алгоритм для этого?

Я рассматривал несколько вариантов, но не могу понять, какой из них лучше.

1. Построить трапециевидную карту и запросить грань каждой точкив. Затем перейдите по краям грани (в подразделении), чтобы найти ближайшую линию.
2. Постройте дерево диапазона или дерево сегментов.Запросите прямоугольник вокруг точки и найдите в нем ближайший отрезок.В этом поле должен быть сегмент, чтобы что-нибудь найти.
3. Построить диаграмму вороного сегмента линии.Каждая грань описывает ближайший сегмент, но я не знаю, как выполнить точечный запрос, поскольку ребра могут быть параболическими дугами.

Что является хорошим подходом высокого уровня для этой проблемы?

Answer 1

Ближайший сосед в Postgis

Подход Postgis заключается в использовании R-деревьев с пользовательским алгоритмом поиска.Спускаясь по дереву, как в обычном запросе, они отслеживают минимальное и максимальное расстояние до объектов в ограничивающих областях, с которыми они сталкиваются в дереве.Каждая встреченная ветвь дерева добавляется в список активных ветвей ( ABL ), который сокращается с использованием метрик расстояния.

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

Теоретический наихудший случай - линейный для запроса, но на практике он дает гораздо лучшие результаты.