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

1、空間索引在介紹空間索引之前，先談?wù)勈裁唇小八饕啊σ粋€(gè)數(shù)據(jù)集做”索引“，是為了提高 對這個(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)在大家對索引有了感性認(rèn)識(shí)，那什么是“空間索引“呢？ ”空間索引“也是”索引“, 是對空間圖形集合做的一個(gè)”目錄“，提高在這個(gè)圖形集合中奩找某個(gè)圖形

2、對象的效率。比 如說，我們在一個(gè)地圖圖層上進(jìn)行矩形選擇，確定這個(gè)圖層上哪些圖元被這個(gè)矩形所完全包 含呢，在沒有”空間索引“的情況下，我們會(huì)把這個(gè)圖層上的所有圖元，一一拿來與這個(gè)矩 形進(jìn)行幾何上的包含判斷，以確泄到底哪些圖元被完全包含在這個(gè)矩形內(nèi)。您是不是覺得這 樣做很合理呢？其實(shí)不然，我們先看一個(gè)網(wǎng)格索引的例子：識(shí)1rfex0aadcmi¥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)分別與矩形逬行 幾何包含比較，最后確定a. b,c三點(diǎn)在選擇范圍內(nèi)01234567我們對這個(gè)點(diǎn)圖層作了

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

4、高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) aw 1234567(xn.yn)綠色的網(wǎng)格單元是 紅色的線所經(jīng)過的。在這些網(wǎng)格單元中，記錄下圖元對象的地址或者引用，比如：聲明一個(gè)對象二 維數(shù)組list gridmn; m代表網(wǎng)格的行數(shù)，n代表網(wǎng)格的列數(shù)，每個(gè)數(shù)組元素為一個(gè)“集合 對象”，用于存儲(chǔ)這個(gè)網(wǎng)格單元所關(guān)聯(lián)的所有圖元的地址或引用，這樣網(wǎng)格索引就建

5、立好了。 下一步，我們該怎么用這個(gè)網(wǎng)格索引呢？所有的圖形顯示和操作都可以借助于“空間索引” 來提高效率。舉幾個(gè)例子來說明“空間索引“的使用：一、放大開窗顯示，正如上一節(jié)介紹的，當(dāng)我們在地圖上畫一個(gè)矩形想放大地圖的時(shí)候， 首先得確定放大后的地圖在屏幕上需要顯示哪些圖元？所以，我們需要判斷這個(gè)地圖中有哪 些圖元全部或者部分落在這個(gè)矩形中。判斷步驟：1, 確定所畫矩形左上角和右下角所在的網(wǎng)格數(shù)組元素；即可得到這個(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,

6、窗口裁減，也可以不裁減)二、包含判斷，給出一個(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的。另外，google map應(yīng)該也是采用地理網(wǎng)格的方式，對地圖圖象進(jìn)行索引的，可見一斑， 網(wǎng)格索引在圖形顯示，選擇，拓?fù)渑袛嗌系膹V泛應(yīng)用。但同時(shí)也存在很嚴(yán)重的缺陷：當(dāng)被索 引的圖元對彖是線，或者多邊形的時(shí)候，存在索引的冗余，即一個(gè)線或者多邊形的引用在多 個(gè)網(wǎng)格中都有記錄。隨著冗余量的增大，效率明顯下降。所以，

7、很多學(xué)者提出了各種方法來 改進(jìn)網(wǎng)格索引，這個(gè)將在下面的章節(jié)屮介紹。而點(diǎn)圖元非常適合網(wǎng)格索引，不存在兀余問題。四叉樹索引(quadtree)類似于前面介紹的網(wǎng)格索引，也是対地理空間進(jìn)行網(wǎng)格劃分，對地理空間遞歸進(jìn)行四分 來構(gòu)建四叉樹，本文將在普通i川叉樹的基礎(chǔ)上，介紹一種改進(jìn)的四叉樹索引結(jié)構(gòu)。首先，先 介紹一個(gè)gts (geographic information system)或者計(jì)算機(jī)圖形學(xué)上非常重要的概念最小外包矩形(mbr-minimum bounding rectangle):最小外包矩形(mbr-minimum bounding rectangle)最小外包矩形mbr就是包圍圖元，且平

8、行于x, y軸的最小外接矩形。mbr 到底有什么用處呢，為什么要引入這個(gè)概念呢？因?yàn)?，圖元的形狀是不規(guī)則的，而mbr是平行于x, y軸的規(guī)則圖形，設(shè)想一下，如果所有的圖元都是平行于x, y軸的矩形，那針 對這樣的矩形進(jìn)行幾何上的任何判斷，是不是要簡單很多呢？不管我們?nèi)俗约簩懝剿惴ɑ?者編寫程序運(yùn)行，是不是都要比原本復(fù)雜的圖形兒何運(yùn)算要簡潔很多呢？答案很顯然。然后，我們再介紹一下gis空間操作的步驟（這個(gè)步驟，在前面忘記向大家 說明了，在這里補(bǔ)充一下）空間數(shù)據(jù)操作的慨要步驟可見，過濾階段，通過空問索引可以排除掉一些明顯不符合條件的圖元，得到 后選集合，然后對后選圖元集合進(jìn)行精確兒何運(yùn)算，得到最

9、終結(jié)果。大家可能會(huì)有這樣的疑 問，這樣有必要嗎？是不是反而把問題復(fù)雜化了？合適的空間索引只會(huì)提高計(jì)算機(jī)的效率, 沒有空間索引，我們無疑要對集合屮的每個(gè)圖元進(jìn)行精確兒何運(yùn)算，而這樣的運(yùn)算是復(fù)雜的, 是非常占用cpu的，所以需要空間索引，采取少量的內(nèi)存和簡單的cup運(yùn)算，來盡量減少 那種高耗cup的精確運(yùn)算的次數(shù)，這樣做是完全值得的。至于精確的幾何運(yùn)算到底復(fù)雜在 哪里，該如何進(jìn)行精確的幾何運(yùn)算，將在下面的章節(jié)屮詳細(xì)描述，這里主要介紹過濾階段的 空間索引?，F(xiàn)在，讓我們來具體了解一下“四叉樹索引”。四叉樹索引就是遞歸地對地理空i'可進(jìn)行四分，直到自行設(shè)定的終止條件（比如每個(gè)節(jié) 點(diǎn)關(guān)聯(lián)圖元的個(gè)數(shù)

10、不超過3個(gè)，超過3個(gè)，就再四分），最終形成一顆有層次的四叉樹。圖 中有數(shù)字標(biāo)識(shí)的矩形是每個(gè)圖元的mbr,每個(gè)葉子節(jié)點(diǎn)存儲(chǔ)了本區(qū)域所關(guān)聯(lián)的圖元標(biāo)識(shí)列 表和木區(qū)域地理范圍，非葉子節(jié)點(diǎn)僅存儲(chǔ)了區(qū)域的地理范圍。大家可以發(fā)現(xiàn)，同樣存在一個(gè) 圖元標(biāo)識(shí)被多個(gè)區(qū)域所關(guān)聯(lián)，相應(yīng)地存儲(chǔ)在多個(gè)葉子節(jié)點(diǎn)上，比如“6 “所代表的圖元，分 別存儲(chǔ)在四個(gè)分枝上。這樣，就存在索引的冗余，與網(wǎng)格索引存在同樣的弊端。下面我們介 紹一種改進(jìn)的四叉樹索引，或者說是分層的網(wǎng)格索引。改進(jìn)的四叉樹索引，就是為了避免這種空間索引的冗余，基本改進(jìn)思路 是：讓每個(gè)圖元的mbr被一個(gè)最小區(qū)域完全包含?？梢钥闯觯?和13分別都跨越了兩個(gè)區(qū)域，要被一

11、個(gè)最小區(qū)域完全包含，就只能是根 節(jié)點(diǎn)所代表的區(qū)域，2, 5跨越了兩個(gè)區(qū)域，6跨越了四個(gè)區(qū)域，要被一個(gè)最小區(qū)域完全包含， 就只能是nw區(qū)域。怎么判斷一個(gè)圖元被哪個(gè)最小區(qū)域完全包含呢？從直觀上看，遞歸地 對地理空間進(jìn)行四分，如果圖元與一個(gè)區(qū)域四分的劃分線相交，則這個(gè)圖元就歸屬于這個(gè)區(qū) 域，或者直到不再劃分了，那就屬于這個(gè)不再劃分的區(qū)域。呵呵。可能有點(diǎn)繞口，看圖， 結(jié)合“最小” “完全包含”這兩個(gè)字眼，您就明白了。這顆四叉樹中，圖元的標(biāo)識(shí)不再僅僅 存儲(chǔ)在葉子節(jié)點(diǎn)上，而是每個(gè)節(jié)點(diǎn)都有可能存儲(chǔ)，這樣也就避免了索引冗余。同時(shí)每個(gè)節(jié)點(diǎn) 存儲(chǔ)本節(jié)點(diǎn)所在的地理范圍。有了四叉樹索引，下面又該如何利用這顆樹來幫助檢

12、索查找呢？還是矩形選擇為例吧! （為什么我總是拿這個(gè)例子來說事呢？因?yàn)檫@個(gè)例子簡單，容易理解，有表性?。┪覀冊?地圖上畫一個(gè)矩形，判斷地圖上哪些圖元落在這個(gè)矩形里或者和這個(gè)所畫矩形相交。方法很 多，這里介紹一種簡單的檢索步驟，如下：1，首先，從四叉樹的根節(jié)點(diǎn)開始，把根節(jié)點(diǎn)所關(guān)聯(lián)的圖元標(biāo)識(shí)都加到一個(gè)list里；2, 比較此矩形范圍與根節(jié)點(diǎn)的四個(gè)子節(jié)點(diǎn)（或者叫子區(qū)域）是否有交集（相交或者包 含），如果有，則把相應(yīng)的區(qū)域所關(guān)聯(lián)的圖元標(biāo)識(shí)加到list集合中，如果沒有，則以下這 顆子樹都不再考慮。3, 以上過程的遞歸，直到樹的葉子節(jié)點(diǎn)終止，返回listo4, 從list集合屮根據(jù)標(biāo)識(shí)一一取出圖元，先判斷圖元mbr與矩形有無交集，如果有， 則進(jìn)行下面的精確兒何判斷，如果沒有，則不再考慮此圖元。1當(dāng)然，這里只