记录
KD树与SKD树
KD树与SKD树 首先给出两个搜到的有点内容的KD树文章,论述的比我说的更完整(更冗长),可以先看,也可以看完本文再看. * https://www.zybuluo.com/l1ll5/note/967681 * http://www.whudj.cn/?p=920 主体思想 * KD树和SKD树都使用坐标轴对齐的最小包围盒来描述空间. * 例如,平面内,一堆点的点集对应的空间可以用点A=(min(all_x),min(all_y)),B=(max(all_x),max(all_y)) 对应的矩形空间来描述. 当点的个数变为1时,这个矩形空间也会自然地退化为一个点. * 构建时的主要思想: 每个节点node都对应了一个空间box(node),node->plane用一个超平面把这个空间box(node)一分为二,记为sub_left,