第二章-2空間數(shù)據(jù)結(jié)構(gòu)的類型

1、2.3 空間數(shù)據(jù)結(jié)構(gòu)的類型2.3.1 空間數(shù)據(jù)結(jié)構(gòu)的概念和類型空間數(shù)據(jù)結(jié)構(gòu)的概念和類型 空間數(shù)據(jù)結(jié)構(gòu)空間數(shù)據(jù)結(jié)構(gòu) 也稱為圖形數(shù)據(jù)格式，是指適用于也稱為圖形數(shù)據(jù)格式，是指適用于計(jì)算機(jī)系統(tǒng)存貯、管理和處理的地理圖形數(shù)據(jù)的邏計(jì)算機(jī)系統(tǒng)存貯、管理和處理的地理圖形數(shù)據(jù)的邏輯結(jié)構(gòu)，是地理實(shí)體的空間排列方式和相互關(guān)系的輯結(jié)構(gòu)，是地理實(shí)體的空間排列方式和相互關(guān)系的抽象描述抽象描述。換句話說，是指空間數(shù)據(jù)以什么形式在換句話說，是指空間數(shù)據(jù)以什么形式在計(jì)算機(jī)中存儲和管理。計(jì)算機(jī)中存儲和管理。 在地理信息系統(tǒng)中，常用的空間數(shù)據(jù)結(jié)構(gòu)有兩種，即矢量數(shù)據(jù)結(jié)構(gòu)和柵格數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)和柵格數(shù)據(jù)結(jié)構(gòu)。 常用的空間數(shù)據(jù)結(jié)構(gòu)常

2、用的空間數(shù)據(jù)結(jié)構(gòu)XYijx1 y1x2 y2xi yixn yn同一條曲線的矢量矢量與柵格表示法柵格表示法 （1） 定義 基于矢量模型的數(shù)據(jù)結(jié)構(gòu)簡稱為矢量數(shù)據(jù)結(jié)構(gòu)。 矢量也叫向量，數(shù)學(xué)上稱“具有大小和方向的量”為向量。 在計(jì)算機(jī)圖形中，相鄰兩結(jié)點(diǎn)間的弧段長度表示大小，弧段兩端點(diǎn)的順序表示方向，因此弧段也是一個直觀的矢量。注意：由于坐標(biāo)空間設(shè)為連續(xù)，所以允許任意位置、長度和面積的精確定義。 但是，其精度僅受數(shù)字化設(shè)備的精度和數(shù)值記錄字長的限制，在一般情況下，比柵格結(jié)構(gòu)精度高得多 。矢量數(shù)據(jù)模型 對于對于點(diǎn)實(shí)體（點(diǎn)實(shí)體（0維對象），沒有長度和寬度維對象），沒有長度和寬度 只只記錄其在特定坐標(biāo)系下的

3、坐標(biāo)和屬性記錄其在特定坐標(biāo)系下的坐標(biāo)和屬性代碼代碼； 線實(shí)體（線實(shí)體（1維對象），只有長度沒有寬度：維對象），只有長度沒有寬度：用一系列足夠短的直線首尾相接表示一條用一系列足夠短的直線首尾相接表示一條曲線。曲線。 矢量結(jié)構(gòu)中矢量結(jié)構(gòu)中只記錄這些小線段的端點(diǎn)坐標(biāo)，只記錄這些小線段的端點(diǎn)坐標(biāo)，將曲線表示為一個坐標(biāo)序列，坐標(biāo)之間認(rèn)將曲線表示為一個坐標(biāo)序列，坐標(biāo)之間認(rèn)為是以直線段相連，為是以直線段相連，在一定精度范圍內(nèi)可在一定精度范圍內(nèi)可以逼真地表示各種形狀的線狀地物以逼真地表示各種形狀的線狀地物 。 “多邊形多邊形”在地理信息系統(tǒng)中是在地理信息系統(tǒng)中是指一個任指一個任意形狀、邊界完全閉合的空間區(qū)域意

4、形狀、邊界完全閉合的空間區(qū)域。 其邊界將整個空間劃分為兩個部分：包含其邊界將整個空間劃分為兩個部分：包含無窮遠(yuǎn)點(diǎn)的部分稱為外部，另一部分稱為無窮遠(yuǎn)點(diǎn)的部分稱為外部，另一部分稱為多邊形內(nèi)部多邊形內(nèi)部。 多邊形的邊界線同線實(shí)體一樣，可以被看多邊形的邊界線同線實(shí)體一樣，可以被看作是由一系列多而短的直線段組成。作是由一系列多而短的直線段組成。 （2） 特點(diǎn)：定位明顯，屬性隱含定位明顯，屬性隱含。 （3） 獲取方法： 手工數(shù)字化法； 手扶跟蹤數(shù)字化法； 數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換法。矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)分為以下幾種矢量數(shù)據(jù)結(jié)構(gòu)分為以下幾種主要類型主要類型 簡單數(shù)據(jù)結(jié)構(gòu)簡單數(shù)據(jù)結(jié)構(gòu) 拓?fù)鋽?shù)據(jù)結(jié)構(gòu)拓?fù)鋽?shù)據(jù)

5、結(jié)構(gòu) 曲面數(shù)據(jù)結(jié)構(gòu)曲面數(shù)據(jù)結(jié)構(gòu)1）簡單數(shù)據(jù)結(jié)構(gòu)）簡單數(shù)據(jù)結(jié)構(gòu) a.面條（面條（Spaghetti方式）方式）在簡單數(shù)據(jù)結(jié)構(gòu)中，空間數(shù)據(jù)按在簡單數(shù)據(jù)結(jié)構(gòu)中，空間數(shù)據(jù)按照以基本的空間對象（點(diǎn)、線、多邊形）為單位進(jìn)行單獨(dú)照以基本的空間對象（點(diǎn)、線、多邊形）為單位進(jìn)行單獨(dú)組織，不含有拓?fù)潢P(guān)系數(shù)據(jù)，最典型的是面條（組織，不含有拓?fù)潢P(guān)系數(shù)據(jù)，最典型的是面條（Spaghetti方式）方式） 由多邊形邊界的由多邊形邊界的x、y坐標(biāo)對集合及說明信息組成，是坐標(biāo)對集合及說明信息組成，是最簡單的一種多邊形矢量編碼，如上圖記為以下坐標(biāo)文件：最簡單的一種多邊形矢量編碼，如上圖記為以下坐標(biāo)文件：10：x1,y1；x2,y

6、2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11； x1,y1；20：x1,y1；x12,y12；x13,y13；x14,y14；x15,y15；x16,y16；x17,y17；x18,y18；x19,y19；x20,y20；x21,y21；x22,y22；x23,y23；x8,y8；x9,y9；x10,y10；x11,y11； x1,y1；30：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38；x39,y39；x40,y40； x33,y33；40：x19,y19；x20,y2

7、0；x21,y21；x28,y28；x29,y29；x30,y30；x31,y31；x32,y32； x19,y19；50：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24；x25,y25；x26,y26；x27,y27；x28,y28； x21,y21； 特點(diǎn)特點(diǎn)： 1.數(shù)據(jù)按點(diǎn)、線或多邊形為單元組織，數(shù)據(jù)編排直觀，數(shù)據(jù)按點(diǎn)、線或多邊形為單元組織，數(shù)據(jù)編排直觀，數(shù)字化操作簡單；數(shù)字化操作簡單； 2每個多邊形都以閉合線段存儲，多邊形之間的公共每個多邊形都以閉合線段存儲，多邊形之間的公共邊界被數(shù)字化和存儲兩次，造成數(shù)據(jù)冗余和不一致；邊界被數(shù)字化和

8、存儲兩次，造成數(shù)據(jù)冗余和不一致； 3點(diǎn)、線和多邊形有各自的坐標(biāo)數(shù)據(jù)，但沒有拓?fù)鋽?shù)點(diǎn)、線和多邊形有各自的坐標(biāo)數(shù)據(jù)，但沒有拓?fù)鋽?shù)據(jù)，互相之間不關(guān)聯(lián)。據(jù)，互相之間不關(guān)聯(lián)。 4. 島只作為一個單個的圖形建造，沒有與外包多邊形島只作為一個單個的圖形建造，沒有與外包多邊形的聯(lián)系；的聯(lián)系； 5不易檢查拓?fù)溴e誤。這種方法可用于簡單的粗精度不易檢查拓?fù)溴e誤。這種方法可用于簡單的粗精度制圖系統(tǒng)中制圖系統(tǒng)中 2）拓?fù)鋽?shù)據(jù)結(jié)構(gòu)）拓?fù)鋽?shù)據(jù)結(jié)構(gòu) 拓?fù)湫蛿?shù)據(jù)結(jié)構(gòu)由拓?fù)湫蛿?shù)據(jù)結(jié)構(gòu)由弧段坐標(biāo)文件、結(jié)點(diǎn)文弧段坐標(biāo)文件、結(jié)點(diǎn)文件和多邊形文件等一系列含拓?fù)潢P(guān)系的數(shù)件和多邊形文件等一系列含拓?fù)潢P(guān)系的數(shù)據(jù)文件組成據(jù)文件組成。結(jié)點(diǎn)文件由結(jié)

9、點(diǎn)記錄組成，存貯每個結(jié)點(diǎn)的結(jié)點(diǎn)號、結(jié)點(diǎn)坐標(biāo)及與該結(jié)點(diǎn)連接的弧段等弧段坐標(biāo)文件存貯組成弧段的點(diǎn)的坐標(biāo)弧段文件由弧記錄組成，存貯弧段的起止結(jié)點(diǎn)號和左右多邊形號；多邊形文件由多邊形記錄組成，存貯多邊形號、組成多邊形的弧段號以及多邊形的周長、面積、中心點(diǎn)坐標(biāo)。 DIME(雙重獨(dú)立坐標(biāo)地圖編碼，雙重獨(dú)立坐標(biāo)地圖編碼，Dual Independent Map Encoding)編碼系統(tǒng)編碼系統(tǒng) DIME是美國人口調(diào)查局在人口調(diào)查的基礎(chǔ)上發(fā)展起來的，它通過有向編碼建立了多邊形、邊界、節(jié)點(diǎn)之間的拓?fù)潢P(guān)系，DIME編碼成為其它拓?fù)渚幋a結(jié)構(gòu)的基礎(chǔ) 拓?fù)湔系牡乩砭幋a和參考系統(tǒng)（拓?fù)湔系牡乩砭幋a和參考系統(tǒng)（TIG

10、ER) 多邊形轉(zhuǎn)換器（多邊形轉(zhuǎn)換器（POLYVRT） 特點(diǎn)： 點(diǎn)是相互獨(dú)立的，點(diǎn)連成線，線構(gòu)成面。 每條線始于起始結(jié)點(diǎn)（FN），止于終止結(jié)點(diǎn)（TN）并與左右多邊形（LP和RP）相鄰接。 構(gòu)成多邊形的線又稱為鏈段或弧段，兩條以上的弧段相交的點(diǎn)成為結(jié)點(diǎn)，由一條弧段組成的多邊形成為島，多邊形圖中不含島的多邊形稱為簡單多邊形，表示單連通區(qū)域；含島區(qū)的多邊形成為復(fù)合多邊形，表示復(fù)連通區(qū)域。 在這種數(shù)據(jù)結(jié)構(gòu)中，弧段或鏈段是數(shù)據(jù)組織的基本對象。 拓?fù)鋽?shù)據(jù)結(jié)構(gòu)最重要的技術(shù)特征和貢獻(xiàn)是拓?fù)鋽?shù)據(jù)結(jié)構(gòu)最重要的技術(shù)特征和貢獻(xiàn)是具有拓?fù)渚庉嫻δ?。具有拓?fù)渚庉嫻δ堋?拓?fù)渚庉嫻δ芡負(fù)渚庉嫻δ馨òǘ噙呅芜B接編輯多邊形連

11、接編輯和和結(jié)點(diǎn)結(jié)點(diǎn)連接編輯連接編輯a.多邊形連接編輯多邊形連接編輯弧段號起點(diǎn) 終點(diǎn)左多邊形右多邊形a2N2N40p4a7N3N4p4p3a8N2N3p4p2弧段號起點(diǎn) 終點(diǎn)左多邊形右多邊形a2N2N40p4a7N4N3p3p4a8N3N2p2p4弧段號起點(diǎn) 終點(diǎn)左多邊形右多邊形a2N2N40p4a8N4N3p3p4a7N3N2p2p4N1N3N5N2N4P2P1P4P3 如果依照上述順序連接的結(jié)點(diǎn)不能自行閉合，或者出現(xiàn)記錄缺損或記錄多余等情況，則表示弧段文件有錯，必須改正出錯的記錄。直到所有多邊形都經(jīng)過編輯和改正，再轉(zhuǎn)入結(jié)點(diǎn)連接編輯。b.結(jié)點(diǎn)連接編輯結(jié)點(diǎn)連接編輯N1N3N5N2N4P2P1P4

12、P3弧段號起點(diǎn)終點(diǎn)左多邊形右多邊形a8N2N3p4p2a6N3N5p3p1a7N3N4p4p3a5N1N3p2p1弧段號起點(diǎn)終點(diǎn)左多邊形右多邊形a8N2N3p4p2a6N5N3p1p3a7N4N3p3p4a5N1N3p2p1弧段號起點(diǎn)終點(diǎn)左多邊形右多邊形a5N1N3p2p1a6N5N3p1p3a7N4N3p3p4a8N2N3p4p2 如果依照上述順序連接的多邊形不能首尾呼應(yīng)，或者出現(xiàn)記錄缺損或記錄多余等情況，同樣也表示弧段文件有錯，必須改正出錯的記錄。直到結(jié)點(diǎn)都經(jīng)過編輯和改正，才能將該弧段文件和多邊形文件的自動生成以及數(shù)據(jù)庫的建立。3）曲面數(shù)據(jù)結(jié)構(gòu)）曲面數(shù)據(jù)結(jié)構(gòu) 曲面是指連續(xù)分布現(xiàn)象的覆蓋表面

13、，具有曲面是指連續(xù)分布現(xiàn)象的覆蓋表面，具有這種覆蓋表面的要素有地形、降水量、溫這種覆蓋表面的要素有地形、降水量、溫度、磁場等。表示和存儲這些要素的基本度、磁場等。表示和存儲這些要素的基本要求是必須便于連續(xù)現(xiàn)象在任一點(diǎn)的內(nèi)插要求是必須便于連續(xù)現(xiàn)象在任一點(diǎn)的內(nèi)插計(jì)算，因此經(jīng)常采用不規(guī)則三角網(wǎng)來擬合計(jì)算，因此經(jīng)常采用不規(guī)則三角網(wǎng)來擬合連續(xù)分布現(xiàn)象的覆蓋表面，稱為連續(xù)分布現(xiàn)象的覆蓋表面，稱為TIN（Triangulated Irregular Network）數(shù)據(jù)）數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)34271865 這種基于這種基于TIN的曲面數(shù)據(jù)結(jié)構(gòu)，通常用于數(shù)的曲面數(shù)據(jù)結(jié)構(gòu)，通常用于數(shù)字地形的表示，或者按照曲面要素的實(shí)

14、測字地形的表示，或者按照曲面要素的實(shí)測點(diǎn)分布，將它們連成三角網(wǎng)，三角網(wǎng)中每點(diǎn)分布，將它們連成三角網(wǎng)，三角網(wǎng)中每個三角形要求盡量接近等邊形狀，并保證個三角形要求盡量接近等邊形狀，并保證由最鄰近的點(diǎn)構(gòu)成的三角形，即三角形的由最鄰近的點(diǎn)構(gòu)成的三角形，即三角形的邊長之和最小。邊長之和最小。在所有可能的三角網(wǎng)中，在所有可能的三角網(wǎng)中，狄洛尼（狄洛尼（Delaunay）三角網(wǎng)在地形擬合方）三角網(wǎng)在地形擬合方面表現(xiàn)最為出色。面表現(xiàn)最為出色。 狄洛尼（狄洛尼（Delaunay）三角網(wǎng)）三角網(wǎng)：為相互鄰接：為相互鄰接且互相不重疊的三角形的集合，每一個三且互相不重疊的三角形的集合，每一個三角形的外接圓內(nèi)不含其他的

15、點(diǎn)。角形的外接圓內(nèi)不含其他的點(diǎn)。 狄洛尼三角形外接圓不包含其他點(diǎn)的特性狄洛尼三角形外接圓不包含其他點(diǎn)的特性被用作從一系列不重合的平面點(diǎn)建立狄洛被用作從一系列不重合的平面點(diǎn)建立狄洛尼三角網(wǎng)的基本法則，可以稱為尼三角網(wǎng)的基本法則，可以稱為狄洛尼法狄洛尼法則則狄洛尼三角網(wǎng)的構(gòu)建：狄洛尼三角網(wǎng)的構(gòu)建：（三角網(wǎng)生長法）（三角網(wǎng)生長法） Delaunay三角網(wǎng)的特性 其Delaunay三角網(wǎng)是唯一的； 三角網(wǎng)的外邊界構(gòu)成了點(diǎn)集P的凸多邊形“外殼”； 沒有任何點(diǎn)在三角形的外接圓內(nèi)部，反之，如果一個三角網(wǎng)滿足此條件，那么它就是Delaunay三角網(wǎng)； 如果將三角網(wǎng)中的每個三角形的最小角進(jìn)行升序排列，則Dela

16、unay三角網(wǎng)的排列得到的數(shù)值最大，從這個意義上說， Delaunay三角網(wǎng)是“最接近于規(guī)則化”的三角網(wǎng)。（等邊三角形） 34271865三角形的標(biāo)識碼相鄰三角形三角形頂點(diǎn)頂點(diǎn)坐標(biāo)和特征值1231st2st3stX1，y1，z1X2，y2，z2X3，y3，z3ABCD127ABCD泰森多邊形（Thiessen Polygon） 弗若洛依圖（弗若洛依圖（Voronoi Diagram）在二維空間中）在二維空間中也稱泰森多邊形（也稱泰森多邊形（Thiessen Polygon）。）。 區(qū)域D上有n個離散點(diǎn)Pi(Xi,Yi)(i=1,2,n),若將D用一組直線段分成n個互相鄰接的多邊形,滿足: 1)

17、每個多邊形內(nèi)含且僅含一個離散點(diǎn) 2)D中任意一點(diǎn)P(X,Y)若位于Pi所在的多邊形內(nèi),則滿足 由以上定義可知,泰森多邊形泰森多邊形的分法是唯一的;每個泰森多邊形泰森多邊形均是凸多邊形;任意兩個泰森多邊形泰森多邊形不存在公共區(qū)域。從左圖中可以看出來，將泰森多邊形中各已知點(diǎn)(參考點(diǎn))相連形成的一個三角形網(wǎng)，該三角形網(wǎng)是泰森多邊形的對偶圖，它被稱為狄洛尼三角網(wǎng)（D-TIN）。 用迪洛尼三角網(wǎng)構(gòu)建泰森多邊形用迪洛尼三角網(wǎng)構(gòu)建泰森多邊形 給定一個給定一個D-TIN，對于它的所有內(nèi)邊，連接共，對于它的所有內(nèi)邊，連接共有每條內(nèi)邊的兩個三角形的外接圓的圓心，即構(gòu)有每條內(nèi)邊的兩個三角形的外接圓的圓心，即構(gòu)成該成

18、該TIN的平面點(diǎn)集的平面點(diǎn)集Voronoi圖。圖。 （1）首先構(gòu)建離散平面點(diǎn)集的）首先構(gòu)建離散平面點(diǎn)集的D-TIN； （2）然后求取各三角形的外接圓心；）然后求取各三角形的外接圓心； （3）對每一個離散點(diǎn)，按順時針或逆時針方）對每一個離散點(diǎn)，按順時針或逆時針方向連接與其關(guān)聯(lián)的三角形的外接圓心，即得到該向連接與其關(guān)聯(lián)的三角形的外接圓心，即得到該離散點(diǎn)的泰森多邊形；離散點(diǎn)的泰森多邊形； （4）將各離散點(diǎn)的泰森多邊形形成集合，即）將各離散點(diǎn)的泰森多邊形形成集合，即得到本平面點(diǎn)集的泰森多邊形。得到本平面點(diǎn)集的泰森多邊形。矢量數(shù)據(jù)結(jié)構(gòu)編碼矢量數(shù)據(jù)結(jié)構(gòu)編碼一、編碼的概念和意義一、編碼的概念和意義 地理數(shù)據(jù)

19、編碼，是根據(jù)GIS的目的和任務(wù)，把地圖、圖像等資料按一定數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為適于計(jì)算機(jī)存貯和處理的數(shù)據(jù)過程。地理內(nèi)容的編碼要反映出地理實(shí)體的幾何特征，以及地理實(shí)體的屬性特征，空間數(shù)據(jù)的編碼是地理信息系統(tǒng)設(shè)計(jì)中最重要的技術(shù)步驟，它表現(xiàn)由現(xiàn)實(shí)世界到數(shù)據(jù)世界之間的界面，是聯(lián)結(jié)從現(xiàn)實(shí)世界到數(shù)據(jù)世界的紐帶。二、矢量數(shù)據(jù)結(jié)構(gòu)編碼方法二、矢量數(shù)據(jù)結(jié)構(gòu)編碼方法 1）點(diǎn)實(shí)體矢量編碼方法 2）線實(shí)體矢量編碼方法 3）多邊形矢量編碼方法1） 點(diǎn)實(shí)體編碼點(diǎn)實(shí)體編碼比例朝向線指針線交匯編比例朝向字體文句x,y 坐標(biāo)其它非幾何屬性建立和顯示數(shù)據(jù)庫聯(lián)系的屬性簡單點(diǎn)符號文本點(diǎn)字符結(jié) 點(diǎn)符號統(tǒng)一標(biāo)識類別或系列號點(diǎn)類型簡單點(diǎn)文本點(diǎn)結(jié)

20、點(diǎn)2） 線實(shí)體編碼線實(shí)體編碼唯一標(biāo)示碼唯一標(biāo)示碼線標(biāo)示碼線標(biāo)示碼起始點(diǎn)起始點(diǎn)終止點(diǎn)終止點(diǎn)坐標(biāo)對序列坐標(biāo)對序列顯示信息顯示信息非幾何屬性非幾何屬性唯一標(biāo)識碼是系統(tǒng)排列序號；線標(biāo)識碼可以標(biāo)識線的類型；起始點(diǎn)和終止點(diǎn)號可直接用坐標(biāo)表示；顯示信息是顯示時的文本或符號等；與線相聯(lián)系的非幾何屬性可以直接存儲于線文件中，也可單獨(dú)存儲，而由標(biāo)識碼聯(lián)接查找。 3） 多邊形矢量編碼多邊形矢量編碼多邊形環(huán)路（坐標(biāo)序列法）法多邊形環(huán)路（坐標(biāo)序列法）法樹狀（層次）索引編碼法樹狀（層次）索引編碼法拓?fù)浣Y(jié)構(gòu)編碼法拓?fù)浣Y(jié)構(gòu)編碼法由多邊形邊界的x,y坐標(biāo)隊(duì)集合及說明信息組成對所有邊界點(diǎn)數(shù)字化，將坐標(biāo)對以順序方式存儲，由點(diǎn)索引與

21、邊界線號相聯(lián)系，以線索引與各多邊形相聯(lián)系形成完整的拓?fù)浣Y(jié)構(gòu)（1）多邊形環(huán)路法）多邊形環(huán)路法123456789101112131415P1P2P3P1 x1，y1；x2，y2； x3，y3；x4，y4； x5，y5；x6，y6；P2 x7，y7；x8，y8； x9，y9；x10，y10； x11，y11；x5，y5；x6，y6P3 x12，y12；x13，y13；x14，y14；x15，y15 坐標(biāo)序列法文件結(jié)構(gòu)簡單，易于實(shí)現(xiàn)以多邊形為單位的運(yùn)算和顯示。這種方法的缺點(diǎn)是： 多邊形之間的公共邊界被數(shù)字化和存儲兩次，由此產(chǎn)生冗余和碎屑多邊形； 每個多邊形自成體系而缺少鄰域信息，難以進(jìn)行鄰域處理，如消

22、除某兩個多邊形之間的共同邊界； 島只作為一個單個的圖形建造，沒有與外包多邊形的聯(lián)系； 不易檢查拓?fù)溴e誤。這種方法可用于簡單的粗精度制圖系統(tǒng)中。多邊形環(huán)路法的多邊形環(huán)路法的優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)(2) 樹狀索引法樹狀索引法123456789101112131415P1P2P3 P1P3P2 1 2 3 4 5 6 5 6 5 6 7 8 9 1012 13 14 15 123456789101112131415P1P2P3點(diǎn)文件 點(diǎn)號 坐標(biāo) 1 x1，y1 2 x2，y2 15 x15，y15(2) 樹狀索引法樹狀索引法123456789101112131415P1P2P31 2 3 4 5 6 5 6 5 6 7 8 9 1012 13 14 15 線文件線號 起點(diǎn) 終點(diǎn) 點(diǎn)號 6 5 6,1,2,3,4,5 5 6 5,6 6 5 6,7,8,9,10,11,5 12 13 12,15,14,13(2) 樹狀索引法樹狀索引法123456789101112131415P1P2P3多邊形文件多邊形號 邊界線號 1 ， 2