Я пытаюсь построить ограничительные рамки в 2D-пространстве с помощью первых нескольких узлов дерева kd.Например, дерево строится только до тех пор, пока я не получу 8 ограничивающих рамок.Итак, корневой узел на глубине 0 делит точки на 2 области.Левый и правый дочерние элементы на глубине 1 делят весь регион на 4 блока, и, наконец, узлы на глубине 3 делят регион на 8 блоков.
Я могу построить дерево и ограничивающие блоки следующим образом в функции build_kdtree:
val minX = points.map(p => p._1).min()
val minY = points.map(p => p._2).min()
val maxX = points.map(p => p._1).max()
val maxY = points.map(p => p._2).max()
val ll_A = (minX, minY)
val ur_A = if (axis == 0) (median._1, maxY) else (maxX, median._2)
val ll_B = if (axis == 0) (median._1, minY) else (minX, median._2)
val ur_B = (maxX,maxY)
, где 'll', 'ur' относится к нижним левым и верхним правым точкам, которые составляют ограничивающий прямоугольник.И, A и B относится к тому факту, что каждая точка делит область на 2 подобласти или прямоугольники.Кроме того, учтите, что для оси = 0 область будет разделена на левые и правые ограничивающие блоки, а для оси = 1 - на нижнюю и верхнюю ограничительные рамки.
Проблема с этим кодом заключается в том, чтоКоординаты 'll' и 'ur', полученные из точек на глубине 1 и 2, немного уменьшают пространство, потому что точки, которые дают min, max на каждой итерации, могут быть недоступны.
Например, выходные данныеЯ получаю это:
Depth 0:
Root node=(0.566325879,0.574899707)
ll_A, ur_A, ll_B, ur_B=(0.0,0.0),(0.566325879,1.0),(0.566325879,0.0),(1.0,1.0)
Depth 1:
Left=(0.340983325,0.740971924)
ll_A, ur_A, ll_B, ur_B=(0.0,0.0),(0.491409668,0.740971924),(0.0,0.740971924),(0.491409668,0.982352539)
Right=(0.412548242,0.714853613)
ll_A, ur_A, ll_B, ur_B=(0.0,0.509733984),(0.412548242,0.982352539),(0.412548242,0.509733984),(0.491409668,0.982352539)
В приведенном выше, максимальный левый ребенок и правый ребенок должны быть 1, а не 0,98.
Я испытываю потерю большего пространства, когда я пытаюсь построить большеограничивающие прямоугольники, такие как 8, 16 или 64, потому что тогда значения min и max также зависят от родителя и прародителя узлов.
Я не могу жестко закодировать этот фрагмент для каждой глубины, поэтому ограничивающие рамки строятся так, как дерево строится в каждой рекурсии.Однако я не могу придумать алгоритм, который работает на всех уровнях дерева и дает ограничивающие рамки, составляющие весь регион.
Любая помощь приветствуется в этом отношении.Спасибо.