У меня огромное количество отрезков в 2D. Я хочу представлять их всех в
KD-древовидная структура, а затем найти соседние отрезки для
конкретный отрезок. Любые идеи о том, как сделать это с KD-дерева?
Сегмент должен быть в каждом листе дерева kd, который он пересекает. То есть, скажем, отрезок представлен парой точек (p1, p2)
, вы должны хранить ссылку на этот отрезок в узлах дерева kd. Этот отрезок линии должен быть в каждом узле дерева kd, через который он проходит, эта часть отличается от той, которая имеет дело с точками, где каждая точка хранится только в пределах одного узла дерева kd.
Разбивая узел дерева kd, вы разделяете горизонтальную или вертикальную линию. Сегмент линии находится в «левом» поддереве, если хотя бы одна из конечных точек находится в левом поддереве. И аналогично для правильного поддерева.
Вы должны найти поблизости, выполнив что-то похожее на запрос точки с конечными точками отрезка. То есть посмотрите на все листья дерева kd возле конечных точек запроса.
Затем для потенциальных сегментов в этих ячейках вы можете выполнить точное сравнение длины, посмотрев на длину перпендикулярной линии от конечной точки запроса до потенциального сегмента, и наоборот (сравните конечные точки линии-кандидата с строкой запроса).
Подробности того, как это сделать, даны здесь: Наименьшее расстояние между точкой и отрезком. Вы должны сделать 4 теста, конечные точки одной линии к другой линии, и наоборот, и взять минимум. Позаботьтесь о том, чтобы игнорировать расстояния в тех случаях, когда точка проецируется за пределы отрезка.
Это работает, потому что линии не изгибаются, поэтому ближайшая точка между двумя линиями должна находиться на одной из конечных точек.
Вы не можете реализовать kd-дерево с сегментами. kd-дерево специально разработано для k-векторного пространства, а сегменты не являются частью векторного пространства. Идея в том, чтобы использовать kd-tree для разбиения kd-пространства на гиперплоскость, если вы не находитесь в kd-векторном пространстве, это не идеально.
Тем не менее, вам может понадобиться иерархия ограничивающих томов, https://en.wikipedia.org/wiki/Bounding_volume_hierarchy, техника, используемая для обнаружения столкновений.