GIS中KD树空间索引

关于KD树

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

GIS中的KD树

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

示意图如下:

其他相关文章

如果对本文有其他疑问,可以在本文下方留言。 如果有其他GIS、3S相关疑问也可以到 麻辣GIS问答 版块发表提问。
本站QQ群:291616564; 微信公众号:malagis,扫描 二维码 直接关注。

打赏¥1

作者:,GIS爱好者。
分享本文,请您带上本文链接
分享到:

发表评论