Я знаю, что kd-деревья традиционно используются для хранения точек, но вместо этого я хочу хранить строки. Было бы лучше разбить линию на каждом пересечении с расщеплением kd-дерева? или будет хранить только конечные точки в kd-достаточно для поиска ближайшего соседа?Как лучше хранить строки в kd-дереве
Ну, вам нужно разделить линии на перекрестках, иначе у вас возникнут проблемы с весами листьев дерева.
С другой стороны, если вы не используете SAH или какой-либо другой алгоритм для перемещения по дереву, вы можете делать все, что хотите, с оригинальной идеей kd-дерева. Но если вы : связаны с некоторыми традиционными алгоритмами, у вас есть, чтобы разделить линии. Вы должны сделать это только потому, что каждый лист дерева имеет вес (я думаю, в вашем случае это зависит от длины линий в нем).
И если вы не разделите линии, вы также получите неправильные веса листьев. Нет, если вы не разделяете строки, вы должны дублировать их в обоих листах, к которым принадлежит линия.
Вам нужно использовать kd-дерево? Для расширенных примитивов bv-tree может быть более эффективным.
Само устройство kd предназначено для объектов. Даже для ящиков, сфер или чего-то подобного. Я считаю, вы может каким-то образом использовать дерево 6d, которое хранит minx, maxx, miny, maxy, minz, maxz; но я не совсем уверен, как правильно его запросить.
R*-tree (Wikipedia) может быть лучшим выбором здесь. Он действительно предназначен для объектов с пространственной протяженностью. Если вы посмотрите на связанные публикации, они даже экспериментировали с различными приближениями сложных объектов; например, расплачиваться ли они за их треугольную форму, использовать окружность, ограничительную шкатулу и, что интересно, IIRC, в некоторых случаях наилучший результат дает 5-угольный полигон.
В любом случае, семья R * -три может быть интересным выбором.
Это зависит от того, что вы хотите сделать. Помните, что строка (сегмент) представляет собой всего лишь набор из двух координат, поэтому ее можно описать с помощью одной координаты с вдвое большим числом измерений. Таким образом, вы можете хранить строки как точки в высокоразмерном kd-дереве. –
Я пытаюсь создать поле расстояния с линиями. Поэтому я буду использовать функциональность ближайшего соседа kd-дерева. Однако я не хочу добавлять больше данных, чем то, что у меня есть (конечные точки сегментов линии. – newDelete