Как получить набор прямоугольников из дерева k-d?

Если вы посмотрите на запись в Википедии для деревьев k-d, вы увидите это иллюстрация точек и плоскостей, которые делят двумерное пространство на прямоугольники.

Мой вопрос: как мне получить результирующий набор прямоугольников? Я думал, что каждый «путь» к листовому узлу может дать мне границы. Есть ли общий способ сделать это для N точек на произвольной глубине?

Обратите внимание, что я не прошу о k-d дереве гиперпрямоугольных структур, где данный ввод представляет собой набор прямоугольников, которые затем можно запросить для поиска диапазона и т. д. Мой ввод представляет собой набор случайных точек, и я хочу вывести набор прямоугольников, которые «замощают» или полностью делят декартово пространство.


geometry kdtree
person Progger    schedule 19.11.2012    source источник
comment
Тут как бы два вопроса. Вы ищете алгоритм, который строит k-d дерево из случайного набора точек, или алгоритм, который, учитывая k-d дерево, перечисляет набор прямоугольников разбиения? Или оба?   -  person eh9    schedule 20.11.2012
comment
k-d деревья обычно не хранят прямоугольники, они хранят разделенные оси. Вы можете тривиально реализовать это, написав небольшой фрагмент кода разделения прямоугольника, который в основном проходит в 2D-прямоугольнике, который каждый узел разрезает вдоль оси разделения, отправляя 2 новых прямоугольника дочерним элементам.   -  person Jerdak    schedule 21.11.2012

Ответы (2)


arrow_upward
0
arrow_downward

Спасибо eh9 за редактирование. Просто чтобы уточнить, что ввод — это дерево k-d, построенное из набора случайных точек, выход — набор результирующих прямоугольников.

И спасибо Джердаку за «тривиальное» решение: просто пройдитесь по дереву, начиная с корневого узла, и продолжайте разбивать прямоугольники на каждой глубине оси. Единственная дополнительная информация — это внешняя граница исходного прямоугольника. Как только все узлы будут посещены, вы можете вернуть полный набор.

person Progger    schedule 20.11.2012

arrow_upward
0
arrow_downward

Многие kD-деревья фактически хранят ограничивающие гиперпрямоугольники каждого поддерева/листа, чтобы можно было лучше отсечь их при поиске KNN. Обратите внимание, что это не прямоугольники, которые покрывают все пространство, а оставляют промежутки между листьями, где нет точек. Лично я думаю, что они круче ;-)

person jkflying    schedule 14.12.2012