GIS空间数据库(14)BSP树索引

BSP树(Binary Space Partitioning Tree,二值空间划分树)是一种二叉树,它将空间逐级进行一分为二的划分,如图所示。

生成过程:

最初,整个区域被定义为 BSP树的根。之后,你继续划分区域。一旦把凹形区域划分为两个凸形区域(在最好情况下)或凹多边形,命名这些区域,它们成为其父结点的孩子,父结点实际上代表了整个区域。

优缺点

BSP树能很好地与空间对象的分布情况相适应,但一般而言,BSP树深度较大,对各种操作均有不利影响。 使用BSP树来进行从后向前排序的最大优点就是算法运行的复杂性较低 。这种方法也解决了多边形的多重交叠和多边形穿越问题。但是,通过使用一个预计算结构,我们已经失去了一定的灵活性。如果多边形的排列在运行时发生了改变, BSP树就必须发生相应的改变。

参考

8.29 什么是BSP树
二叉空间分割(BSP)树

GIS空间数据库(13)KDB树索引 GIS空间数据库(15)G树索引

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

发表评论