Хранение прямоугольников / кругов / треугольников в KD-дереве

Я смотрел на Kd-дерево и нашел некоторые реализации этого алгоритма. Все они были точками хранения (2d в большинстве случаев). То, что я пытаюсь достичь, - это хранить в нем различные формы, такие как прямоугольник, треугольник и т. д. так можно ли в KD-деревьях хранить фигуры ? У меня есть код для квадро-деревьев. В нем хранились формы.

3 2
c# algorithm kdtree

3 ответа:

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

Для каждой фигуры вы должны уметь вычислять:

  • Его центроид.

  • Его конверт.

При вычислении медианы используйте центроиды. Огибающая формы должна поместиться в квадрате. При вставке фигуры в квадрат проверьте, пересекает ли ее огибающая гиперплоскость. Если это правда, сохраните фигуру в квадрате. Если false, поместите эту фигуру в соответствующий список фигур ваш левый или правый квадроцикл строительный звонок.

Ура

2

Это зависит от того, что вы хотите сделать с вашим набором фигур, когда у вас есть kd-дерево для него. Допустим, у вас есть набор прямоугольников, и вы хотите быстро найти все прямоугольники, которые полностью содержатся в прямоугольнике запроса. Тогда подходящим способом использования KD-дерева (или, еще лучше, дерева диапазона imo) является сохранение координат min и max x и y для прямоугольника в виде 4-мерной точки и построение дерева для 4-мерных точек. Тогда для прямоугольника запроса (a0,a1)x (b0, b1), дерево используется для выполнения запроса диапазона для 4-мерных точек с использованием диапазона (a0,+inf) x (-inf, a1) x (b0, +inf) x (-inf, b1).

2

Это естественное продолжение KD-дерева.

Когда у вас есть только точки в вашем дереве:

  • узлы в дереве соответствуют областям вашего пространства
  • Дан родительский узел P и дочерние узлы C1, C2, ..., CN, дочерние узлы Ci взаимно непересекающиеся и они разбивают P
  • каждая точка x присутствует в ровно в одном листовом узле дерева

Когда у вас есть Тома в дереве:

  • узлы в дереве соответствуют областям вашего пространства
  • заданы родительский узел P и дочерние узлы C1, C2, ..., CN, дочерние узлы Ci взаимно непересекающиеся и они разбивают P
  • Каждый том v присутствует в по крайней мере в одном листовом узле дерева (он находится "в" любом листовом узле, с которым он пересекается)
1