GIS中BSP树空间索引

BSP树是一种二叉树,它将空间逐级进行一分为二的划分,如下图。BSP树能很好地与空间数据库中空间对象的分布情况相适应,但对一般情况而言,BSP树深度较大,对各种操作均有不利影响，所以在GIS系统中采用BSP空间索引的并不多见。如图：

BSP的想法最早在Fuchs(1980)中被提出，起初的目的是为了解决实时地消除隐藏面。BSP可以说是八叉树的一般化。前人在这方面已经做了很多有效的工作，Fuchs首次将BSP技术中剖分平面的定侧性质应用于多边形场景的剖分，建立起空间二叉树结构.该二叉树的每一结点表示一个子空间及空间内所包含的多边形。在每一结点空间中，选取其中一平面作为剖分平面，将该空间继续剖分成正负两子空间，分别作为该结点的两个子结点，其中与剖分平面有交的多边形被分割成两个多边形，分别归入相应的子空间中。上述过程是一个递归过程，直至每一子空间仅包含一个多边形为止。与八叉树剖分相比，BSP树具有内存耗费小，剖分方式灵活，产生的无效区域较小的优点;且对大部分场景来说，BSP树较八叉树更为平衡。