Поиск ближайшего соседнего края в Quadtree

Question

Я сохранил набор точек в Quadtree. Как только квадрант был создан с точками, я затем добавляю все ребра в квадрант, чтобы каждое ребро сохранялось во ВСЕХ узлах листа, с которыми оно пересекается, начинается или заканчивается на.

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

Теперь мои вопросы

а) Как я могу идти об извлечении ближайших краев?

b) Должен ли я просто сравнивать все ребра, содержащиеся в родительском (с точки зрения интереса) узле? (Но я знаю, за то, что поставив жесткое ограничение на количество уровней нужно идти, чтобы найти ближайший край неверен основанный на интуиции)

Answer 1

Вы можете попробовать диаграммы Вороного и искать кромками внутри ячейки voronoi.

Answer 2

Каждый узел на четырехъядерном дереве представляет собой куб в пространстве (где некоторые стороны могут быть бесконечными), и вы можете рассчитать минимальное расстояние между этим кубом и целевой точкой A. Обратите внимание, что расстояние равно 0 для кубов, содержащих A.

Начиная с корневого узла, вы должны вычислить расстояние для каждого из его дочерних кубов (узлов) до A и вставить его в мини-кучу.

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

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

Обновление: Кстати, это на самом деле общий подход для поиска чего-либо с использованием четырехъядерного дерева или kd-дерева или, возможно, большинства пространственных структур.