BSP树（Binary Space Partitioning Tree，二值空间划分树）是一种二叉树，它将空间逐级进行一分为二的划分，如图所示。
生成过程：
最初，整个区域被定义为 BSP树的根。之后，你继续划分区域。一旦把凹形区域划分为两个凸形区域（在最好情况下）或凹多边形，命名这些区域，它们成为其父结点的孩子，父结点实际上代表了整个区域。
优缺点
BSP树能很好地与空间对象的分布情况相适应，但一般而言，BSP树深度较大，对各种操作均有不利影响。 使用BSP树来进行从后向前排序的最大优点就是算法运行的复杂性较低 。这种方法也解决了多边形的多重交叠和多边形穿越问题。但是，通过使用一个预计算结构，我们已经失去了一定的灵活性。如果多边形的排列在运行时发生了改变， BSP树就必须发生相应的改变。
- 本文固定链接: https://www.chtfs.com/4489/
- 转载请注明: acer 于 测绘途夫 发表
这个作者貌似有点懒，什么都没有留下。