我正在尝试实现和理解 KdTree
,以下是我找到的链接。
http://ldots.org/kdtree/#buildingAkDTree
但是我不明白下面的算法
tuple function build_kd_tree(int depth, set points):
if points contains only one point:
return that point as a leaf.
if depth is even:
Calculate the median x-value.
Create a set of points (pointsLeft) that have x-values less than
the median.
Create a set of points (pointsRight) that have x-values greater
than or equal to the median.
else:
Calculate the median y-value.
Create a set of points (pointsLeft) that have y-values less than
the median.
Create a set of points (pointsRight) that have y-values greater
than or equal to the median.
treeLeft = build_kd_tree(depth + 1, pointsLeft)
treeRight = build_kd_tree(depth + 1, pointsRight)
return(median, treeLeft, treeRight)
我不明白什么意思
计算 x 值的中位数。
最佳答案
您的点
有x
和y
值。 median x
值可以通过按 x
排序获得,然后取中间元素的 x
(对于奇数个 points
) 或两个中间 points
' x
的平均值(对于偶数个 points
)。
或者,使用快速 selection algorithm例如中位数。
关于algorithm - Kd树问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6251835/