GIS空间数据库（14）BSP树索引

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

生成过程：

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

优缺点

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

参考

8.29 什么是BSP树
二叉空间分割（BSP）树