空間索引使用的意義及網格索引和四叉樹索引簡單介紹

《空間索引使用的意義及網格索引和四叉樹索引簡單介紹》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、空間索引在介紹空間索引之前，先談談什么叫“索引“。對一個數據集做”索引“，是為了提高對這個數據集檢索的效率。書的”目錄“就是這本書內容的”索引“，當我們拿到i本新書，想查看感興趣內容的時候，我們會先查看目錄，確定感興趣的內容會在哪些頁里，直接翻到那些頁，就OKT,而不是從第一章節(jié)開始翻，一個字一個字地找我們感興趣的內容，直到找到為止，這種檢索內容的效率也太低了，如果一本書沒有目錄，可以想象有多么不方便…可見書的目錄有多重要，索引有多重要??！現在大家對索引有了感性認識，那什么是“空間索引“呢？”空間索引“也是”索引“,是對空間圖形集合做的一個”目錄“，

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循環(huán)10萬次；建立索引將使得For循環(huán)的次數下降很多很多，效率自然提高很多！呵呵…想必大家都知道空間索引的好處了，也不知不覺向大家介紹了點圖層的網格索引,還有哪些常用的空間索引呢？這些空間索引乂該如何實現呢？帶

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代表網格的列數，每個數組元素為一個“集合對象”，用于存儲這個網格單元所關聯的所有圖元的地址或引用，這樣網格索引就建立好了。下一步，我們該怎么用這個網格索引呢？所有的圖形顯示和操作都可以借助于“空間索引”來提高效率。舉幾個例子來說明“空間索引“的使用：一、放大開窗顯示，正如上一節(jié)介紹的，當我們在地圖上畫一個矩形想放大地圖的時候，首先得確定放大后的地圖在屏幕上需要顯示哪些圖元？所以，我們需要判斷這個地圖中有哪些圖元全部或者部分落在這個矩形中。判斷步驟：1,確定所畫矩形左上角和右下角所在的網格數組

6、元素；即可得到這個矩形所關聯覆蓋的所有網格集合；2,遍歷這個網格集合中的元素，取到每個網格元素List中所記錄的圖元；3,畫出這些圖元即可。(當然整個過程涉及到兩點：1,屏幕坐標和地圖坐標的互相變換；2,窗口裁減，也可以不裁減)二、包含判斷，給出一個點point和一個多邊形polygon,判斷點是否在面內，首先判斷這個點所在的網格，是否同時關聯這個polygon，如果不是，表明點不在面內，如果是，可以下一步的精確解析兒何判斷，或者精度允許的情況下，即判斷polygon是包含point的。另外，GoogleMap應該也是采用地理網格的方式，對地圖圖象進

7、行索引的，可見一斑，網格索引在圖形顯示，選擇，拓撲判斷上的廣泛應用。但同時也存在很嚴重的缺陷：當被索引的圖元對彖是線，或者多邊形的時候，存在索引的冗余，即一個線或者多邊形的引用在多個網格中都有記錄。隨著冗余量的增大，效率明顯下降。所以，很多學者提出了各種方法來改進網格索引，這個將在下面的章節(jié)屮介紹。而點圖元非常適合網格索引，不存在兀余問題。四叉樹索引(Quadtree)類似于前面介紹的網格索引，也是対地理空間進行網格劃分，對地理空間遞歸進行四分來構建四叉樹，本文將在普通I川叉樹的基礎上，介紹一種改進的四叉樹索引結構。首先，先介紹一個GTS(Geogr

8、aphicInformationSystem)或者計算機圖形學上非常重要的概念最小外包矩形(MBR-Mini