网格索引

陈玉进李泉南京跬步科技有限公司（http://www.creable.cn）

上一节向大家介绍了空间索引的概念和用途，这一节重点介绍一种常用的空间索引形式——网格索引。
网格索引就是在一个地图图层上，按每个小网格宽△w,高△h打上均匀的格网，计算每个图元所占据的网格或者所经过的网格单元集合，

在这些网格单元中，记录下图元对象的地址或者引用，比如：声明一个对象二维数组 List grid[m][n]; m代表网格的行数，n代表网格的列数，每个数组元素为一个“集合对象”，用于存储这个网格单元所关联的所有图元的地址或引用，这样网格索引就建立好了。下一步，我们该怎么用这个网格索引呢？

所有的图形显示和操作都可以借助于“空间索引”来提高效率。举几个例子来说明“空间索引“的使用：

list: l0 level1 lfo1;">list: Ignore;">一、放大开窗显示，正如上一节介绍的，当我们在地图上画一个矩形想放大地图的时候，首先得确

list: l0 level1 lfo1;">定放大后的地图在屏幕上需要显示哪些图元？所以，我们需要判断这个地图中有哪些图元全部或者

list: l0 level1 lfo1;">部分落在这个矩形中。判断步骤：1，确定所画矩形左上角和右下角所在的网格数组元素；即可得到

list: l0 level1 lfo1;">这个矩形所关联覆盖的所有网格集合；2，遍历这个网格集合中的元素，取到每个网格元素List中所

list: l0 level1 lfo1;">记录的图元；3，画出这些图元即可。（当然整个过程涉及到两点：1，屏幕坐标和地图坐标的互相

list: l0 level1 lfo1;">变换；2，窗口裁减，也可以不裁减）

list: l0 level1 lfo1;">list: Ignore;">二、包含判断，给出一个点point和一个多边形polygon，判断点是否在面内，首先判断这个点所在的

list: l0 level1 lfo1;">网格，是否同时关联这个polygon，如果不是，表明点不在面内，如果是，可以下一步的精确解析几

list: l0 level1 lfo1;">何判断，或者精度允许的情况下，即判断polygon是包含point的。

list: l0 level1 lfo1;">

另外，Google Map应该也是采用地理网格的方式，对地图图象进行索引的，可见一斑，网格索引在图形显示，选择，拓扑判断上的广泛应用。但同时也存在很严重的缺陷：当被索引的图元对象是线，或者多边形的时候，存在索引的冗余，即一个线或者多边形的引用在多个网格中都有记录。随着冗余量的增大，效率明显下降。所以，很多学者提出了各种方法来改进网格索引，这个将在下面的章节中介绍。而点图元非常适合网格索引，不存在冗余问题。