格网型空间索引的基本思想是将研究区域用横竖线条划分大小相等和不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。

把一幅图的矩形地理范围均等地划分为 m行n列，即规则地划分二维数据空间，得到m×n个小矩形网格区域。每个网格区域为一个索引项，并分配一个动态存储区，全部或部分落入该网格的空间对象的标识以及外接矩形存入该网格。

网格索引是一种多对多的索引,会导致冗余，网格划分得越细，搜索的精度就越高，当然冗余也越大，耗费的磁盘空间和搜索时间也越长。网格法由于必须预先定义好网格大小，因此它不是一种动态的数据结构。适合点数据。网格索引搜索算法的时间复杂度为o(N2)。

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

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

一、 放大开窗显示，正如上一节介绍的，当我们在地图上画一个矩形想放大地图的时候，首先得确

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

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

这个矩形所关联覆盖的所有网格集合；2，遍历这个网格集合中的元素，取到每个网格元素List中所

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

变换；2，窗口裁减，也可以不裁减）

二、 包含判断，给出一个点point和一个多边形polygon，判断点是否在面内，首先判断这个点所在的

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

何判断，或者精度允许的情况下，即判断polygon是包含point的。

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