posts - 5, comments - 17, trackbacks - 0, articles - 12

KD树伪码

Posted on 2005-08-15 15:34 模式识别技术 阅读(1886) 评论(2)  编辑 收藏 引用 所属分类: 计算几何

Algorithm BUILDKDTREE(P,depth)
Input: A set of points P and the current depth depth
Output: The root of a kd-tree storing P.
1.    if P contains only one point then
2.        return a leaf storing this point
3.    else if depth is even then
4.        Split P into two subsets with a vertical line l through the median x-coordinate of the points in P. Let P1 be the set of points to the left and P2 be the set of points to the right. Points exactly on the line belong to P1.
5.    else
6.        Split P into two subsets with a horizontal line l through the median y-coordinate of the points in P. Let P1 be the set of points above l and P2 be the points below l. Points exactly on the line belong to P1.
7.    Vright := BUILDKDTREE(P1,depth+1)
8.    Vleft := BUILDKDTREE(P2,depth+1)
9.    Create a node V with Vright and Vleft as its right and left children, respectively. 
10.    return V.

Feedback

# re: KD树伪码  回复  更多评论   

2007-11-16 15:02 by tank
if depth is even
能解释一下是什么意思吗?

# re: KD树伪码[未登录]  回复  更多评论   

2008-05-29 16:26 by 无名
如果是偶数层,根据Y轴来划分,如果是奇数层,根据Z轴来划分。这种方式是针对二维点集的!
只有注册用户登录后才能发表评论。