圖形拓?fù)潢P(guān)系的構(gòu)建ppt課件

1、拓?fù)潢P(guān)系介紹拓?fù)潢P(guān)系介紹1.1 拓?fù)涞膩?lái)源拓?fù)涞膩?lái)源1.2 為什么要研究地圖上的拓?fù)潢P(guān)系為什么要研究地圖上的拓?fù)潢P(guān)系1.3 建立拓?fù)潢P(guān)系的基本概念建立拓?fù)潢P(guān)系的基本概念1.4 基本的拓?fù)潢P(guān)系基本的拓?fù)潢P(guān)系1.5 拓?fù)潢P(guān)系的表示拓?fù)潢P(guān)系的表示1.6 Arc/Info中拓?fù)潢P(guān)系的構(gòu)建中拓?fù)潢P(guān)系的構(gòu)建1.1 1.1 拓?fù)涞膩?lái)源拓?fù)涞膩?lái)源1.1.拓?fù)涞膩?lái)源拓?fù)涞膩?lái)源 “ “拓?fù)渫負(fù)銽opologyTopology）”一次來(lái)自希臘文，它的原意是一次來(lái)自希臘文，它的原意是“形狀的研究形狀的研究”。拓?fù)鋵W(xué)時(shí)幾何學(xué)的一個(gè)分支，它研究在拓?fù)?。拓?fù)鋵W(xué)時(shí)幾何學(xué)的一個(gè)分支，它研究在拓?fù)渥儞Q下能夠保持不變的幾何屬性變換

2、下能夠保持不變的幾何屬性拓?fù)鋵傩?。拓?fù)鋵傩浴＠樱涸O(shè)想一塊高質(zhì)量的橡皮，它的表面是歐幾里的平面，這塊橡皮可以任例子：設(shè)想一塊高質(zhì)量的橡皮，它的表面是歐幾里的平面，這塊橡皮可以任意被拉伸、緊縮，但是不能夠被扭轉(zhuǎn)或折疊。在橡皮的表面上有由結(jié)點(diǎn)、弧意被拉伸、緊縮，但是不能夠被扭轉(zhuǎn)或折疊。在橡皮的表面上有由結(jié)點(diǎn)、弧、環(huán)、面組成的可能任意圖形。我們對(duì)橡皮進(jìn)行拉伸、緊縮，在橡皮進(jìn)行這、環(huán)、面組成的可能任意圖形。我們對(duì)橡皮進(jìn)行拉伸、緊縮，在橡皮進(jìn)行這些變換的過(guò)程中，圖形的一些屬性消失，一些屬性將繼續(xù)保持存在。設(shè)想象些變換的過(guò)程中，圖形的一些屬性消失，一些屬性將繼續(xù)保持存在。設(shè)想象皮表面有一個(gè)多邊形，里面有一

3、個(gè)點(diǎn)。當(dāng)拉伸、壓縮橡皮時(shí)，點(diǎn)依舊在多邊皮表面有一個(gè)多邊形，里面有一個(gè)點(diǎn)。當(dāng)拉伸、壓縮橡皮時(shí)，點(diǎn)依舊在多邊形中，點(diǎn)和多邊形的位置關(guān)系不會(huì)發(fā)生變化，但是多邊形的面積會(huì)發(fā)生變化形中，點(diǎn)和多邊形的位置關(guān)系不會(huì)發(fā)生變化，但是多邊形的面積會(huì)發(fā)生變化。所以：。所以：“點(diǎn)的內(nèi)置是拓?fù)鋵傩?，而面積不是拓?fù)鋵傩?，拉伸和壓縮就是點(diǎn)的內(nèi)置是拓?fù)鋵傩裕娣e不是拓?fù)鋵傩?，拉伸和壓縮就是拓?fù)渥儞Q。拓?fù)渥儞Q。1.2 1.2 為什么要研究地圖上的拓?fù)?？為什么要研究地圖上的拓?fù)洌?.1.拓?fù)涓拍睿和負(fù)涓拍睿?拓?fù)鋵W(xué)是研究圖形在保持連續(xù)狀態(tài)下變形時(shí)的那些不拓?fù)鋵W(xué)是研究圖形在保持連續(xù)狀態(tài)下變形時(shí)的那些不變的性質(zhì)，也成為變的性質(zhì)，也

4、成為“橡皮板幾何學(xué)橡皮板幾何學(xué)”。 在地圖上僅用距離和方向參數(shù)描述地圖上的目標(biāo)之間的在地圖上僅用距離和方向參數(shù)描述地圖上的目標(biāo)之間的關(guān)系總是不圓滿(mǎn)的。關(guān)系總是不圓滿(mǎn)的。 因?yàn)閳D上兩點(diǎn)之間的距離和方向會(huì)隨著地圖投影的不同而發(fā)生變化，故僅用距離和方向參數(shù)還不能夠確切地表示它們之間的空間關(guān)系。（如下圖）2.2.描述目標(biāo)間關(guān)系需要描述目標(biāo)間關(guān)系需要Longitude/Latitude投影Gauss-Krivger投影 從上圖可以看出，用拓?fù)潢P(guān)系表示，不論怎么變化，其鄰接、關(guān)聯(lián)、包含等關(guān)系都不改變。拓?fù)潢P(guān)系能夠從質(zhì)的方面和整體的概念上反映空間實(shí)體的空間結(jié)構(gòu)關(guān)系。 研究拓?fù)潢P(guān)系對(duì)于地圖數(shù)據(jù)處理和正確顯示將

5、是十分重要的。1.3 1.3 拓?fù)潢P(guān)系的基本概念拓?fù)潢P(guān)系的基本概念 地圖要素可以抽象為點(diǎn)、線(xiàn)、面來(lái)表示，這種歸納正好地圖要素可以抽象為點(diǎn)、線(xiàn)、面來(lái)表示，這種歸納正好適合于建立拓?fù)潢P(guān)系和建立拓?fù)浔硎?。適合于建立拓?fù)潢P(guān)系和建立拓?fù)浔硎尽?.1.若地圖平面上反映一定意義的零維圖形的附近沒(méi)有其它圖形若地圖平面上反映一定意義的零維圖形的附近沒(méi)有其它圖形與之聯(lián)系，則稱(chēng)這個(gè)零維圖形為獨(dú)立點(diǎn)與之聯(lián)系，則稱(chēng)這個(gè)零維圖形為獨(dú)立點(diǎn)PointPoint）。如水井）。如水井3.3.地圖平面上連接兩結(jié)點(diǎn)的有一定意義的一維圖形稱(chēng)為邊地圖平面上連接兩結(jié)點(diǎn)的有一定意義的一維圖形稱(chēng)為邊EdgeEdge） ，也叫弧段，也叫弧段Ar

6、cArc）。例如：連個(gè)城市之間的道路）。例如：連個(gè)城市之間的道路4.4.由一些邊圍成的有一定意義的閉合區(qū)域稱(chēng)為面由一些邊圍成的有一定意義的閉合區(qū)域稱(chēng)為面AreaArea）。）。2.2.若在某個(gè)有一定意義的零維圖形附近還存在另外有意義的若在某個(gè)有一定意義的零維圖形附近還存在另外有意義的零維圖形與之聯(lián)系，則稱(chēng)這個(gè)零維圖形為結(jié)點(diǎn)零維圖形與之聯(lián)系，則稱(chēng)這個(gè)零維圖形為結(jié)點(diǎn)NodeNode）。）。1.4 1.4 基本的拓?fù)潢P(guān)系基本的拓?fù)潢P(guān)系 拓?fù)溧徑雍屯負(fù)潢P(guān)聯(lián)是用來(lái)描述網(wǎng)結(jié)構(gòu)元素比如結(jié)點(diǎn)、弧段、面域之間的兩類(lèi)二元關(guān)系。 基本拓?fù)潢P(guān)系分為拓?fù)溧徑雨P(guān)系、拓?fù)潢P(guān)聯(lián)關(guān)系和拓?fù)浒P(guān)系。 拓?fù)溧徑雨P(guān)系存在于同類(lèi)型元

7、素之間注意是“偶對(duì)集合”）。一般用來(lái)描述面域鄰接。 拓?fù)潢P(guān)聯(lián)關(guān)系存在于不同類(lèi)型元素之間。一般用來(lái)描述結(jié)點(diǎn)與邊、邊與面的關(guān)系。 拓?fù)浒P(guān)系用來(lái)說(shuō)明面域包含于其中的點(diǎn)、弧段、面域的對(duì)應(yīng)關(guān)系。包含關(guān)系有同類(lèi)的，也有不同類(lèi)的。1.5 1.5 拓?fù)潢P(guān)系的表示拓?fù)潢P(guān)系的表示拓?fù)潢P(guān)系的表示分為：顯示表示和隱式表示。拓?fù)潢P(guān)系的表示分為：顯示表示和隱式表示。1.1.顯示表示：就是將網(wǎng)結(jié)構(gòu)元素結(jié)點(diǎn)、弧段、面域間的顯示表示：就是將網(wǎng)結(jié)構(gòu)元素結(jié)點(diǎn)、弧段、面域間的拓?fù)潢P(guān)系數(shù)據(jù)化，并作為地圖數(shù)據(jù)的一部分給以存儲(chǔ)，這就拓?fù)潢P(guān)系數(shù)據(jù)化，并作為地圖數(shù)據(jù)的一部分給以存儲(chǔ)，這就叫拓?fù)潢P(guān)系的顯式表示。叫拓?fù)潢P(guān)系的顯式表示。2.2.

8、隱式表示：不直接存儲(chǔ)拓?fù)潢P(guān)系，而是由幾何數(shù)據(jù)臨時(shí)推隱式表示：不直接存儲(chǔ)拓?fù)潢P(guān)系，而是由幾何數(shù)據(jù)臨時(shí)推導(dǎo)生成所需的拓?fù)潢P(guān)系，這就叫拓?fù)潢P(guān)系的隱式表示。導(dǎo)生成所需的拓?fù)潢P(guān)系，這就叫拓?fù)潢P(guān)系的隱式表示。 計(jì)算導(dǎo)出耗時(shí)的那部分拓?fù)潢P(guān)系用顯式表示；其余的用隱式表示。例子：顯示表示，美國(guó)人口統(tǒng)計(jì)局的雙重獨(dú)立地圖編碼。例子：顯示表示，美國(guó)人口統(tǒng)計(jì)局的雙重獨(dú)立地圖編碼。e11e10e9e8e7e6e5e4e3e2e1線(xiàn)段號(hào)始結(jié)點(diǎn)終結(jié)點(diǎn)左多邊形右多邊形e131NULLAe243NULLBe332ABe412NULLAe542BCe625NULLCe756ECe864DCe976DEe1074NULLDe1157

9、NULLE結(jié)點(diǎn)號(hào)X坐標(biāo)Y坐標(biāo)1X1Y12X2Y23X3Y34X4Y45X5Y56X6Y67X7Y71.地圖網(wǎng)絡(luò)編碼地圖網(wǎng)絡(luò)編碼3.拓?fù)浣Y(jié)構(gòu)文件拓?fù)浣Y(jié)構(gòu)文件2.結(jié)點(diǎn)坐標(biāo)文件結(jié)點(diǎn)坐標(biāo)文件雙重獨(dú)立地圖編碼雙重獨(dú)立地圖編碼DIME）弧段起點(diǎn)終點(diǎn)e121e214e313e423e543e636e7e8e9e10e11e12弧 段e1e2e3e4坐標(biāo)序列(5，5)、(9，5)1.Arc/Info中的中的“弧段與結(jié)點(diǎn)之間的拓?fù)浣Y(jié)構(gòu)弧段與結(jié)點(diǎn)之間的拓?fù)浣Y(jié)構(gòu)”多邊形弧 段B467108C3109D7529E156F8（一條弧線(xiàn)組成）Polygonarc表表弧線(xiàn)坐標(biāo)序列e15,3 5,5 8,5e67,4 6,3

10、 Arc坐標(biāo)表坐標(biāo)表2.Arc/Info多邊形與弧線(xiàn)拓?fù)浣Y(jié)構(gòu)多邊形與弧線(xiàn)拓?fù)浣Y(jié)構(gòu)弧 線(xiàn)左多邊形右多邊形e1AEe2ADe3ACe4ABe5EDe6BEe7BDe8BFe9DCe10CB弧線(xiàn)坐標(biāo)序列e15,3 5,5 8,5e67,4 6,3 Arc坐標(biāo)表坐標(biāo)表左右多邊形表左右多邊形表3.Arc/Info中左右多邊形拓?fù)浣Y(jié)構(gòu)存儲(chǔ)在中左右多邊形拓?fù)浣Y(jié)構(gòu)存儲(chǔ)在A(yíng)rc文件中）文件中）1.6 Arc1.6 ArcInfoInfo拓?fù)浣Y(jié)構(gòu)小結(jié)拓?fù)浣Y(jié)構(gòu)小結(jié) Arc/Info利用拓?fù)浣Y(jié)構(gòu)在兩個(gè)簡(jiǎn)單的坐標(biāo)要素弧線(xiàn)和結(jié)點(diǎn)的基礎(chǔ)上表示附加的地理信息。也就是說(shuō)：地理數(shù)據(jù)作為X，Y坐標(biāo)對(duì)序列來(lái)存儲(chǔ)，分別代表點(diǎn)、線(xiàn)、多邊

11、形。這些地理特征之間的關(guān)系通過(guò)拓?fù)浣Y(jié)構(gòu)來(lái)表達(dá)。相關(guān)的表格數(shù)據(jù)存儲(chǔ)在表格中，通過(guò)內(nèi)部標(biāo)識(shí)號(hào)連接到地理特征上。 拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)模型可以更有效地存儲(chǔ)數(shù)據(jù)，它提供了進(jìn)行高級(jí)地理分析框架。例如：拓?fù)浣Y(jié)構(gòu)模型由組成多邊形邊界的弧的列表來(lái)構(gòu)建多邊形。當(dāng)兩個(gè)多邊形共享一條公共邊時(shí)，系統(tǒng)只存儲(chǔ)公共弧坐標(biāo)值一次。 一個(gè)非拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)模型把每個(gè)封閉的多邊形作為一個(gè)獨(dú)立的實(shí)體存儲(chǔ)，鄰接多邊形公用的一條弧必須輸入并存儲(chǔ)兩次，這通常通過(guò)數(shù)字化兩次或者弧的拷貝來(lái)完成。這種重復(fù)數(shù)據(jù)是地理分析更為困難，因?yàn)橄到y(tǒng)不能夠觀(guān)察出這兩個(gè)多邊形的拓?fù)潢P(guān)系。非拓?fù)浣Y(jié)構(gòu)模型是許多CAD、繪圖和制圖系統(tǒng)支持的常見(jiàn)模型。1.7 1.7 拓?fù)潢P(guān)系是

12、空間數(shù)據(jù)處理拓?fù)潢P(guān)系是空間數(shù)據(jù)處理拓?fù)潢P(guān)系的建立屬于空間數(shù)據(jù)處理的內(nèi)容。拓?fù)潢P(guān)系的建立屬于空間數(shù)據(jù)處理的內(nèi)容。 空間數(shù)據(jù)獲取有各種不同的方法，但無(wú)論哪種方法獲取空間數(shù)據(jù)獲取有各種不同的方法，但無(wú)論哪種方法獲取的數(shù)據(jù)都可能存在這樣或者那樣的問(wèn)題和誤差，如數(shù)字化錯(cuò)的數(shù)據(jù)都可能存在這樣或者那樣的問(wèn)題和誤差，如數(shù)字化錯(cuò)誤、數(shù)據(jù)格式不一致、比例尺或投影不統(tǒng)一、數(shù)據(jù)冗余等。誤、數(shù)據(jù)格式不一致、比例尺或投影不統(tǒng)一、數(shù)據(jù)冗余等。 因此：只有通過(guò)空間數(shù)據(jù)的處理才能使空間數(shù)據(jù)符合因此：只有通過(guò)空間數(shù)據(jù)的處理才能使空間數(shù)據(jù)符合GISGIS數(shù)據(jù)庫(kù)的要求，才能實(shí)現(xiàn)數(shù)據(jù)庫(kù)的要求，才能實(shí)現(xiàn)GISGIS的各種功能。的各種功能

13、。 空間數(shù)據(jù)處理的主要內(nèi)容包括：圖形編輯、自動(dòng)拓?fù)洹⒖臻g數(shù)據(jù)處理的主要內(nèi)容包括：圖形編輯、自動(dòng)拓?fù)洹⒆鴺?biāo)變換、數(shù)據(jù)壓縮、結(jié)構(gòu)轉(zhuǎn)換、數(shù)據(jù)內(nèi)插等。坐標(biāo)變換、數(shù)據(jù)壓縮、結(jié)構(gòu)轉(zhuǎn)換、數(shù)據(jù)內(nèi)插等。建立多邊形拓?fù)浣⒍噙呅瓮負(fù)?.1 2.1 弧段的組織弧段的組織2.2 2.2 結(jié)點(diǎn)的匹配結(jié)點(diǎn)的匹配2.3 2.3 檢查多邊形是否閉合檢查多邊形是否閉合2.4 2.4 建立多邊形建立多邊形2.1 2.1 弧段的組織弧段的組織 邊弧段的組織：把弧段按一定順序存儲(chǔ)，如邊弧段的組織：把弧段按一定順序存儲(chǔ)，如X X坐標(biāo)坐標(biāo)或者或者Y Y坐標(biāo)的順序，便于檢索和查找，然后按順序編號(hào)。坐標(biāo)的順序，便于檢索和查找，然后按順序編號(hào)

14、。弧段的中間相交：弧段的中間相交：要求中間斷開(kāi)要求中間斷開(kāi)弧段的端點(diǎn)相交：弧段的端點(diǎn)相交：要求結(jié)點(diǎn)匹配要求結(jié)點(diǎn)匹配2.2 2.2 結(jié)點(diǎn)匹配結(jié)點(diǎn)匹配結(jié)點(diǎn)匹配結(jié)點(diǎn)匹配 結(jié)點(diǎn)匹配是指把一定限產(chǎn)誒的弧段的端點(diǎn)作為一個(gè)結(jié)點(diǎn)匹配是指把一定限產(chǎn)誒的弧段的端點(diǎn)作為一個(gè)節(jié)點(diǎn)，其坐標(biāo)值取多個(gè)端點(diǎn)的平均值，如圖，然后，對(duì)節(jié)點(diǎn)，其坐標(biāo)值取多個(gè)端點(diǎn)的平均值，如圖，然后，對(duì)結(jié)點(diǎn)順序編號(hào)。結(jié)點(diǎn)順序編號(hào)。2.3 2.3 檢查多邊形是否閉合檢查多邊形是否閉合P 檢查多邊形閉合可檢查多邊形閉合可以通過(guò)判斷一條弧的以通過(guò)判斷一條弧的端點(diǎn)是否有與之匹配端點(diǎn)是否有與之匹配的端點(diǎn)來(lái)進(jìn)行。的端點(diǎn)來(lái)進(jìn)行。 圖中弧段圖中弧段a的端點(diǎn)的端點(diǎn)P沒(méi)

15、沒(méi)有與之匹配的端點(diǎn)，因有與之匹配的端點(diǎn)，因此無(wú)法使用這條弧與其此無(wú)法使用這條弧與其它弧組成閉合多邊形。它弧組成閉合多邊形。 可能的原因是：結(jié)點(diǎn)匹配限差的問(wèn)題造成端點(diǎn)未匹配；數(shù)字化誤差較大，甚至數(shù)字化錯(cuò)誤，這些都可以通過(guò)圖形編輯或重新匹配來(lái)確定。另外如果該弧段本來(lái)就是懸掛弧線(xiàn)，不需要拓?fù)?，做一個(gè)標(biāo)記即可。2.4 2.4 構(gòu)建拓?fù)涠噙呅螛?gòu)建拓?fù)涠噙呅?.4.1 2.4.1 基本常識(shí)基本常識(shí)2.4.2 2.4.2 多邊形拓?fù)潢P(guān)系自動(dòng)建立的兩個(gè)算法多邊形拓?fù)潢P(guān)系自動(dòng)建立的兩個(gè)算法 2.4.2.1 2.4.2.1 弧段跟蹤法弧段跟蹤法 2.4.2.2 2.4.2.2 柵格填充法柵格填充法2.4.1 基本

16、常識(shí)基本常識(shí)1）1.1.順時(shí)針?lè)较驑?gòu)建多邊形順時(shí)針?lè)较驑?gòu)建多邊形 所謂順時(shí)針?lè)较驑?gòu)建多邊形是指多邊形在弧段的右側(cè)。這所謂順時(shí)針?lè)较驑?gòu)建多邊形是指多邊形在弧段的右側(cè)。這需要定義弧線(xiàn)的方向。需要定義弧線(xiàn)的方向。AB左邊左邊右邊右邊左邊左邊右邊右邊AB2.4.1 基本常識(shí)基本常識(shí)2）2.2.最靠右邊的弧段最靠右邊的弧段acdb 最靠右邊的弧段是指從弧段的一個(gè)端點(diǎn)出發(fā)，在這個(gè)弧段的方向上最靠右邊的一條弧段。如圖：弧段如圖：弧段a a最靠右邊的弧段是最靠右邊的弧段是d.d. 找最靠右邊的弧段可以通過(guò)計(jì)算弧段的方向和夾角來(lái)實(shí)現(xiàn)。2.4.1 2.4.1 基本常識(shí)基本常識(shí)3 3）3.3.多邊形面積的計(jì)算多邊形

17、面積的計(jì)算 設(shè)構(gòu)成多邊形的坐標(biāo)串為設(shè)構(gòu)成多邊形的坐標(biāo)串為XiXi，YiYi）（）（i=1i=1，2 2，3 3，n)n)，則多邊形的面積可以用如下公式求出：，則多邊形的面積可以用如下公式求出：niiiiiAxxyyS11121niiiiiAxxyyS11121niiiiiAxxyyS11121 其中，當(dāng)其中，當(dāng)i=ni=n時(shí)，時(shí)，yn+1yn+1y1y1，xn+1=x1xn+1=x1；當(dāng)；當(dāng)i=1i=1時(shí)時(shí),y0,y0ynyn。根據(jù)該公式，當(dāng)多邊形右順時(shí)針?lè)较驑?gòu)成時(shí)，面積為正；否。根據(jù)該公式，當(dāng)多邊形右順時(shí)針?lè)较驑?gòu)成時(shí)，面積為正；否則為負(fù)。則為負(fù)。正正負(fù)負(fù) 2.4.2.1 2.4.2.1 弧段

18、跟蹤法弧段跟蹤法 此法是基于弧段的鄰接關(guān)系，按照一定規(guī)則沿弧段跟蹤形成各個(gè)閉合環(huán)，然后采用內(nèi)點(diǎn)匹配法得到各個(gè)環(huán)與內(nèi)點(diǎn)的包含關(guān)系，最后根據(jù)多邊形結(jié)構(gòu)特點(diǎn)，確定環(huán)與內(nèi)點(diǎn)的圈定關(guān)系，即是建立多邊形面域與弧段的關(guān)聯(lián)關(guān)系。具體分為如下幾步：具體分為如下幾步：1.弧段鄰接關(guān)系的建立弧段鄰接關(guān)系的建立2.環(huán)的生成環(huán)的生成3.建立環(huán)與內(nèi)點(diǎn)的包含關(guān)系建立環(huán)與內(nèi)點(diǎn)的包含關(guān)系4.建立環(huán)與內(nèi)點(diǎn)的圈定關(guān)系建立環(huán)與內(nèi)點(diǎn)的圈定關(guān)系弧段鄰接關(guān)系的建立弧段鄰接關(guān)系的建立 如果兩條弧段具有相同的端點(diǎn)，則定義這兩條弧段具有鄰接關(guān)系。 記錄規(guī)則：鄰接于弧段同一端點(diǎn)的各個(gè)鄰接弧段按順時(shí)針?lè)较蝽樞蛴涗?；按照?shù)字化方向，如果鄰接弧段是首點(diǎn)鄰接，則在其前面冠以正號(hào)，否則冠以負(fù)號(hào)。1首5，2末4，62首7，3末1，53首8，4末2，74首3，8末6，1弧段鄰接關(guān)系表弧段鄰接關(guān)系表環(huán)的生成環(huán)的生成弧段2前端后端弧段3弧段1最靠左邊的弧段最靠左邊的弧段弧段1前端后端弧段2弧段4最靠左邊的弧段最靠左邊的弧段弧段4前端后端弧段1弧段3最靠左邊的弧段最靠左邊的弧段弧段3前端后端弧段4弧段2最靠左邊的弧段最靠左邊的弧段從弧段2開(kāi)始跟蹤，則圈定多邊形A的環(huán)