资源描述：
《空间索引使用的意义及网格索引和四叉树索引简单介绍》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、空间索引在介绍空间索引之前，先谈谈什么叫“索引“。对一个数据集做”索引“，是为了提高对这个数据集检索的效率。书的”目录“就是这本书内容的”索引“，当我们拿到i本新书，想查看感兴趣内容的时候，我们会先查看目录，确定感兴趣的内容会在哪些页里，直接翻到那些页，就OKT,而不是从第一章节开始翻，一个字一个字地找我们感兴趣的内容，直到找到为止，这种检索内容的效率也太低了，如果一本书没有目录，可以想象有多么不方便…可见书的目录有多重要，索引有多重要啊！现在大家对索引有了感性认识，那什么是“空间索引“呢？”空间索引“也是”索引“,是对空间图形集合做的一个”目录“，
2、提高在这个图形集合中奁找某个图形对象的效率。比如说，我们在一个地图图层上进行矩形选择，确定这个图层上哪些图元被这个矩形所完全包含呢，在没有”空间索引“的情况下，我们会把这个图层上的所有图元，一一拿来与这个矩形进行几何上的包含判断，以确泄到底哪些图元被完全包含在这个矩形内。您是不是觉得这样做很合理呢？其实不然，我们先看一个网格索引的例子：☆☆☆☆☆识1rfex☆☆0a•ad☆☆c☆☆mi¥•☆☆e☆☆☆☆先确定红色的选择矩形框所在网格矩阵数组，得到从min点［2,"到max点［5,3］.里网格的点a.b.c.d.e.f.g;把这七个点分别与矩形逬行几何
3、包含比较，最后确定a.b,c三点在选择范围内01234567我们对这个点图层作了网格索引，判断哪些点在这个矩形选择框内，是不需要把这个图层里所有的点都要与矩形进行儿何包含运算的，只对a,b,c,d,e,f,g这七个点做了运算。可以推想一下，如果一个点图层有十万个点，不建立空I'可索引，任何地图操作都将对整个图层的所有图元遍历一次，也就是要For循环10万次；建立索引将使得For循环的次数下降很多很多，效率自然提高很多！呵呵…想必大家都知道空间索引的好处了，也不知不觉向大家介绍了点图层的网格索引,还有哪些常用的空间索引呢？这些空间索引乂该如何实现呢？带
4、着这样的问题，下面介绍儿种常用的空间索引。网格索引网格索引就是在一个地图图层上，按每个小网格宽高Ah打上均匀的格网，计算每个图元所占据的网格或者所经过的网格单元集合，☆☆☆☆☆令☆☆☆☆☆(xi.yi☆☆☆☆☆☆☆☆☆☆☆(xn.yn)点8所在网格二维数组Grid』]编号为:行，(int)((yi-yO)/Ah)+1乳(int)((xi-xO)/Aw)+1声明网格二维数组的行数和列数，也可以通过这个公式来求得(xO.yO)aw1234567(xn.yn)绿色的网格单元是红色的线所经过的。在这些网格单元中，记录下图元对象的地址或者引用，比如：声明一个对
5、象二维数组Listgrid[m][n];m代表网格的行数，n代表网格的列数，每个数组元素为一个“集合对象”，用于存储这个网格单元所关联的所有图元的地址或引用，这样网格索引就建立好了。下一步，我们该怎么用这个网格索引呢？所有的图形显示和操作都可以借助于“空间索引”来提高效率。举几个例子来说明“空间索引“的使用：一、放大开窗显示，正如上一节介绍的，当我们在地图上画一个矩形想放大地图的时候，首先得确定放大后的地图在屏幕上需要显示哪些图元？所以，我们需要判断这个地图中有哪些图元全部或者部分落在这个矩形中。判断步骤：1,确定所画矩形左上角和右下角所在的网格数组
6、元素；即可得到这个矩形所关联覆盖的所有网格集合；2,遍历这个网格集合中的元素，取到每个网格元素List中所记录的图元；3,画出这些图元即可。(当然整个过程涉及到两点：1,屏幕坐标和地图坐标的互相变换；2,窗口裁减，也可以不裁减)二、包含判断，给出一个点point和一个多边形polygon,判断点是否在面内，首先判断这个点所在的网格，是否同时关联这个polygon，如果不是，表明点不在面内，如果是，可以下一步的精确解析儿何判断，或者精度允许的情况下，即判断polygon是包含point的。另外，GoogleMap应该也是采用地理网格的方式，对地图图象进
7、行索引的，可见一斑，网格索引在图形显示，选择，拓扑判断上的广泛应用。但同时也存在很严重的缺陷：当被索引的图元对彖是线，或者多边形的时候，存在索引的冗余，即一个线或者多边形的引用在多个网格中都有记录。随着冗余量的增大，效率明显下降。所以，很多学者提出了各种方法来改进网格索引，这个将在下面的章节屮介绍。而点图元非常适合网格索引，不存在兀余问题。四叉树索引(Quadtree)类似于前面介绍的网格索引，也是対地理空间进行网格划分，对地理空间递归进行四分来构建四叉树，本文将在普通I川叉树的基础上，介绍一种改进的四叉树索引结构。首先，先介绍一个GTS(Geogr
8、aphicInformationSystem)或者计算机图形学上非常重要的概念最小外包矩形(MBR-Mini
