格網型空間索引

在這些格線單元中，記錄下圖元對象的地址或者引用，比如：聲明一個對象二維數組 記錄的圖元；3，畫出這些圖元即可。 格線，是否同時關聯這個polygon

格網型空間索引的基本思想是將研究區域用橫豎線條劃分大小相等和不等的格網，記錄每一個格網所包含的空間實體。當用戶進行空間查詢時，首先計算出用戶查詢對象所在格網，然後再在該格線中快速查詢所選空間實體，這樣一來就大大地加速了空間索引的查詢速度。
把一幅圖的矩形地理範圍均等地劃分為 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應該也是採用地理網格的方式，對地圖圖象進行索引的，可見一斑，格線索引在圖形顯示，選擇，拓撲判斷上的廣泛套用。但同時也存在很嚴重的缺陷：當被索引的圖元對象是線，或者多邊形的時候，存在索引的冗餘，即一個線或者多邊形的引用在多個格線中都有記錄。隨著冗餘量的增大，效率明顯下降。所以，很多學者提出了各種方法來改進格線索引，這個將在下面的章節中介紹。而點圖元非常適合格線索引，不存在冗餘問題。