Как лучше всего хранить строки в kd-дереве

Question

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

Answer 1

Само kd-дерево предназначено для точек объектов. Даже для коробок, сфер или чего-то подобного. Я верю, что вы можете каким-то образом использовать дерево 6d, в котором хранится minx, maxx, miny, maxy, minz, maxz; но я не совсем уверен, как правильно его запросить.

R * -дерево (Википедия) может быть лучшим выбором здесь. Он действительно предназначен для объектов с пространственным расширением. Если вы посмотрите соответствующие публикации, они даже экспериментировали с различными приближениями сложных объектов; например, окупится ли их триангуляция, использование окружности, ограничительной рамки и, что интересно, 5-угловой многоугольник IIRC в некоторых случаях показал наилучшую производительность.

В любом случае, семейство R * -деревьев может быть интересным выбором.

Answer 2

Вам нужно использовать kd-дерево?Для расширенных примитивов bv-дерево может быть более эффективным.

Answer 3

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

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

И если вы не разбиваете линии, вы тоже получите неправильный вес листьев.Нет, если вы не разбиваете строки, вы должны дублировать их в обоих листах, к которым принадлежит строка.