[ HOME ] [ UP ] [ CG in C ] [ Great Wall ] [ Polytope ] [ Graham ] [ Quickhull ] [ 3dCH ] [ CH ] [ Caliper ] [ Sweepline ] [ Width+Diameter ] [ Kernel ] [ Shortest ] [ Spiral ] [ Tripod ] [ AGP ] [ Simple ] [ Triangulation ] [ MWT ] [ VD&DT ] [ VD+DT ] [ Skeleton ] [ Gishur ] [ RealDT ] [ Closest ] [ Proximity ] [ Crust ] [ Alpha ] [ Beta ] [ Medial ] [ Beach Line ] [ Higher-Order VD ] [ Dual ] [ MRD ] [ 4D Cube ] [ 4D Polytope ] [ HyperStar ] [ MEC ] [ 3dCH+2dDT ] [ Location ] [ TrapMap ] [ BSP ] [ kd-Tree ] [ Range Tree ] [ PST ] [ Windowing ]

kd-Tree

kd-Tree@diku

注意：此处坐标系统的原点在左上角，故相对于教材及讲义，y坐标上下颠倒。

相应地：
1）各子区域均为左开右闭、上开下闭
2）若父区域含有n个点，则孩子区域分别含有ceil(n/2)和floor(n/2)个点

(Courtesy of http://www.diku.dk/hjemmesider/studerende/zrock/KDTree/)

kd-Tree@rolemaker

(Courtesy of http://www.rolemaker.dk/nonRoleMaker/uni/algogem/kdtree.htm)

TOP

[ HOME ] [ UP ] [ CG in C ] [ Great Wall ] [ Polytope ] [ Graham ] [ Quickhull ] [ 3dCH ] [ CH ] [ Caliper ] [ Sweepline ] [ Width+Diameter ] [ Kernel ] [ Shortest ] [ Spiral ] [ Tripod ] [ AGP ] [ Simple ] [ Triangulation ] [ MWT ] [ VD&DT ] [ VD+DT ] [ Skeleton ] [ Gishur ] [ RealDT ] [ Closest ] [ Proximity ] [ Crust ] [ Alpha ] [ Beta ] [ Medial ] [ Beach Line ] [ Higher-Order VD ] [ Dual ] [ MRD ] [ 4D Cube ] [ 4D Polytope ] [ HyperStar ] [ MEC ] [ 3dCH+2dDT ] [ Location ] [ TrapMap ] [ BSP ] [ kd-Tree ] [ Range Tree ] [ PST ] [ Windowing ]

Copyleft (c) 2003-3002, Junhui Deng
Last updated on 01.02.2015