Ищете эффективный алгоритм, быстро найдите ближайшую линию (определенную перпендикулярное расстояние) до произвольной точки

Question

У меня есть большой набор строк в 2D с известной начальной точкой и конечной точкой, и хотел бы найти ближайший (определенный перпендикулярной дистанцией) этих ребер (или расширение этих краев, прошедших их начальных и конечных точек.) до произвольной точки.

Лучшее, что я сделал до сих пор, это создать набор точек образца вдоль каждой строки и использовать KD-дерево для решения ближайшей проблемы соседа для точек - I.e. Найти ближайшую точку образца строк в точку запроса.Но это неточно и нуждается в большом количестве образцов для длинных линий.

Я видел это: алгоритм для ближайшего краяобнаружение по отношению к точке (во всех направлениях)

Но он полагался на метод развертки и небольшое количество линий конечной длины.

Answer 1

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

Есть много способов предварительно получить планарное подразделение для решения Проблема местоположения точки с логарифмической сложностью времени. Обычно разработаны некоторые иерархические данные, которые можно пройти для любой точки запроса, и она доказана, что длина пути траверса ограничена $ O (log (n)) $ , где $ n $ - это количество регионов. Как упомянуто в комментариях @pseudomyonomy, вы также можете использовать Двоичное распределение пространства (BSP) для создания Дерево BSP - это также иерархическая структура данных (двоичное дерево), которое позволит вам эффективно найти регион, содержащую точку запроса. Это похоже на вашу проблему хорошо для этого подхода BSP.

Извините, что вы можете сказать, вы можете получить регионы с $ O (n) $ граничные сегменты / лучи, где $ n $ - это количество строк. Чтобы преодолеть эту трудность, вы можете дополнительно подразделить каждый регион в Voronoi Diagram , обобщенной для его граничных сегментов и лучи. Легко видеть, что общее количество таких рафинированных регионов будет ограничено $ O (N ^ 2) $ , который до сих пор дает вам логарифмическую сложность времени для ближайшей линии поиск. Однако в среднем случае эти регионы со многими граничными сегментами / лучами составляют небольшую долю всех регионов - поэтому в среднем вы все еще сможете быстро выбирать ближайший граничный сегмент / луч, просто зацикливающую по границе области.

---

Если вы хотите узнать больше о общих свойствах геометрической структуры, с которым вы работаете - имеет смысл читать эта страница wiki.

Answer 2

Возможно, я могу неправильно понял вашу цель - предположить ли вы, края продолжаются в обоих направлениях, даже если они определяются на 2 конкретных точках вдоль них?Я предполагаю, что вы говорите, что расстояние определяется перпендикулярным расстоянием.В этом случае как насчет этого -
1. Для каждого сегмента строки рассчитайте угол.

2. Нарисуйте воображаемую строку, которая проходит через вашу произвольную точку под углом, который перпендикулярна сегменту линии.
3. Найдите точку пересечения между сегментом линии и новой воображаемой линией, найдите расстояние между этой точкой и вашей произвольной точкой.Держите самое низкое расстояние.
Если линии не являются бесконечно долго, тогда, когда вы проверяете расстояние, проверьте мин (расстояние до начала, расстояние до конечной точки).