空間索引使用的意義及網(wǎng)格索引和四叉樹索引簡(jiǎn)單介紹

《空間索引使用的意義及網(wǎng)格索引和四叉樹索引簡(jiǎn)單介紹》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

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

2、提高在這個(gè)圖形集合中奩找某個(gè)圖形對(duì)象的效率。比如說，我們?cè)谝粋€(gè)地圖圖層上進(jìn)行矩形選擇，確定這個(gè)圖層上哪些圖元被這個(gè)矩形所完全包含呢，在沒有”空間索引“的情況下，我們會(huì)把這個(gè)圖層上的所有圖元，一一拿來與這個(gè)矩形進(jìn)行幾何上的包含判斷，以確泄到底哪些圖元被完全包含在這個(gè)矩形內(nèi)。您是不是覺得這樣做很合理呢？其實(shí)不然，我們先看一個(gè)網(wǎng)格索引的例子：☆☆☆☆☆識(shí)1rfex☆☆0a?ad☆☆c☆☆mi￥?☆☆e☆☆☆☆先確定紅色的選擇矩形框所在網(wǎng)格矩陣數(shù)組，得到從min點(diǎn)［2,"到max點(diǎn)［5,3］.里網(wǎng)格的點(diǎn)a.b.c.d.e.f.g;把這七個(gè)點(diǎn)分別與矩形逬行幾何

3、包含比較，最后確定a.b,c三點(diǎn)在選擇范圍內(nèi)01234567我們對(duì)這個(gè)點(diǎn)圖層作了網(wǎng)格索引，判斷哪些點(diǎn)在這個(gè)矩形選擇框內(nèi)，是不需要把這個(gè)圖層里所有的點(diǎn)都要與矩形進(jìn)行兒何包含運(yùn)算的，只對(duì)a,b,c,d,e,f,g這七個(gè)點(diǎn)做了運(yùn)算。可以推想一下，如果一個(gè)點(diǎn)圖層有十萬個(gè)點(diǎn)，不建立空I'可索引，任何地圖操作都將對(duì)整個(gè)圖層的所有圖元遍歷一次，也就是要For循環(huán)10萬次；建立索引將使得For循環(huán)的次數(shù)下降很多很多，效率自然提高很多！呵呵…想必大家都知道空間索引的好處了，也不知不覺向大家介紹了點(diǎn)圖層的網(wǎng)格索引,還有哪些常用的空間索引呢？這些空間索引乂該如何實(shí)現(xiàn)呢？帶

4、著這樣的問題，下面介紹兒種常用的空間索引。網(wǎng)格索引網(wǎng)格索引就是在一個(gè)地圖圖層上，按每個(gè)小網(wǎng)格寬高Ah打上均勻的格網(wǎng)，計(jì)算每個(gè)圖元所占據(jù)的網(wǎng)格或者所經(jīng)過的網(wǎng)格單元集合，☆☆☆☆☆令☆☆☆☆☆(xi.yi☆☆☆☆☆☆☆☆☆☆☆(xn.yn)點(diǎn)8所在網(wǎng)格二維數(shù)組Grid』]編號(hào)為:行，(int)((yi-yO)/Ah)+1乳(int)((xi-xO)/Aw)+1聲明網(wǎng)格二維數(shù)組的行數(shù)和列數(shù)，也可以通過這個(gè)公式來求得(xO.yO)aw1234567(xn.yn)綠色的網(wǎng)格單元是紅色的線所經(jīng)過的。在這些網(wǎng)格單元中，記錄下圖元對(duì)象的地址或者引用，比如：聲明一個(gè)對(duì)

5、象二維數(shù)組Listgrid[m][n];m代表網(wǎng)格的行數(shù)，n代表網(wǎng)格的列數(shù)，每個(gè)數(shù)組元素為一個(gè)“集合對(duì)象”，用于存儲(chǔ)這個(gè)網(wǎng)格單元所關(guān)聯(lián)的所有圖元的地址或引用，這樣網(wǎng)格索引就建立好了。下一步，我們?cè)撛趺从眠@個(gè)網(wǎng)格索引呢？所有的圖形顯示和操作都可以借助于“空間索引”來提高效率。舉幾個(gè)例子來說明“空間索引“的使用：一、放大開窗顯示，正如上一節(jié)介紹的，當(dāng)我們?cè)诘貓D上畫一個(gè)矩形想放大地圖的時(shí)候，首先得確定放大后的地圖在屏幕上需要顯示哪些圖元？所以，我們需要判斷這個(gè)地圖中有哪些圖元全部或者部分落在這個(gè)矩形中。判斷步驟：1,確定所畫矩形左上角和右下角所在的網(wǎng)格數(shù)組

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

7、行索引的，可見一斑，網(wǎng)格索引在圖形顯示，選擇，拓?fù)渑袛嗌系膹V泛應(yīng)用。但同時(shí)也存在很嚴(yán)重的缺陷：當(dāng)被索引的圖元對(duì)彖是線，或者多邊形的時(shí)候，存在索引的冗余，即一個(gè)線或者多邊形的引用在多個(gè)網(wǎng)格中都有記錄。隨著冗余量的增大，效率明顯下降。所以，很多學(xué)者提出了各種方法來改進(jìn)網(wǎng)格索引，這個(gè)將在下面的章節(jié)屮介紹。而點(diǎn)圖元非常適合網(wǎng)格索引，不存在兀余問題。四叉樹索引(Quadtree)類似于前面介紹的網(wǎng)格索引，也是対地理空間進(jìn)行網(wǎng)格劃分，對(duì)地理空間遞歸進(jìn)行四分來構(gòu)建四叉樹，本文將在普通I川叉樹的基礎(chǔ)上，介紹一種改進(jìn)的四叉樹索引結(jié)構(gòu)。首先，先介紹一個(gè)GTS(Geogr

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