Как представить отрезки в kd-дереве

У меня огромное количество отрезков в 2D. Я хочу представлять их всех в
KD-древовидная структура, а затем найти соседние отрезки для
конкретный отрезок. Любые идеи о том, как сделать это с KD-дерева?

3

Решение

Сегмент должен быть в каждом листе дерева kd, который он пересекает. То есть, скажем, отрезок представлен парой точек (p1, p2), вы должны хранить ссылку на этот отрезок в узлах дерева kd. Этот отрезок линии должен быть в каждом узле дерева kd, через который он проходит, эта часть отличается от той, которая имеет дело с точками, где каждая точка хранится только в пределах одного узла дерева kd.

Разбивая узел дерева kd, вы разделяете горизонтальную или вертикальную линию. Сегмент линии находится в «левом» поддереве, если хотя бы одна из конечных точек находится в левом поддереве. И аналогично для правильного поддерева.

Вы должны найти поблизости, выполнив что-то похожее на запрос точки с конечными точками отрезка. То есть посмотрите на все листья дерева kd возле конечных точек запроса.

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

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

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

3

Другие решения

Вы не можете реализовать kd-дерево с сегментами. kd-дерево специально разработано для k-векторного пространства, а сегменты не являются частью векторного пространства. Идея в том, чтобы использовать kd-tree для разбиения kd-пространства на гиперплоскость, если вы не находитесь в kd-векторном пространстве, это не идеально.

Тем не менее, вам может понадобиться иерархия ограничивающих томов, https://en.wikipedia.org/wiki/Bounding_volume_hierarchy, техника, используемая для обнаружения столкновений.

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector