『公告』 预祝您龙年大吉,万事如意, 过节期间, 大家如需数据服务,请拨打400 或直接添加客服微信,再祝大家龙年,心想事成。
关注我们 新浪 腾讯

GIS中KD树空间索引

GIS中KD树空间索引
在计算机科学里,k-d树(k-维树的缩写)是在k维欧几里德空间组织点的数据结构。k-d树是每个节点都为k维点的二叉树。

    关于KD

 

    在计算机科学里,k-d树(k-维树的缩写)是在k维欧几里德空间组织点的数据结构。k-d树是每个节点都为k维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分区成两部分。在超平面左边的点代表节点的左子树,在超平面右边的点代表节点的右子树。超平面的方向可以用下述方法来选择:每个节点都与k维中垂直于超平面的那一维有关。因此,如果选择按照x轴划分,所有x值小于指定值的节点都会出现在左子树,所有x值大于指定值的节点都会出现在右子树。这样,超平面可以用该x值来确定,其法矢为x轴的单位矢量。(来自维基百科)

 

    GIS中的KD

 

    KD树的基本形式存储了K维空间点。KD树的每个内部节点都包含一个点,并且和一个矩形区域相对应。树的根节点和整个研究区域相对应。树中奇数层次上的点的X坐标和偶数层次上的点的Y坐标把矩形区域分成两部分。在KD树结构中,通过沿着树下降到达一个树叶节点的方式来添加一个新点。KD树的查找是从根节点开始,查看所存储的节点(分裂的点)是否被包括在查找范围内以及和左子树或者右子树是否有交叠。对于每个和查询范围交叠的子树,查询过程将重复执行直到到达树叶那一级为止

 

    示意图如下:

 

      京ICP备2025132830号-1 京公网安备 号