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

1、拓?fù)潢P(guān)系介紹拓?fù)潢P(guān)系介紹1.1 拓?fù)涞膩碓赐負(fù)涞膩碓?.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ù)涞膩碓赐負(fù)涞膩碓?.1.拓?fù)涞膩碓赐負(fù)涞膩碓?“ “拓?fù)渫負(fù)銽opologyTopology）”一次來自希臘文，它的原意是一次來自希臘文，它的原意是“形狀的研究形狀的研究”。拓?fù)鋵W(xué)時(shí)幾何學(xué)的一個(gè)分支，它研究在拓?fù)?。拓?fù)鋵W(xué)時(shí)幾何學(xué)的一個(gè)分支，它研究在拓?fù)渥儞Q下能夠保持不變的幾何屬性變換

2、下能夠保持不變的幾何屬性拓?fù)鋵傩?。拓?fù)鋵傩?。例子：設(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)行這些變換的過程中，圖形的一些屬性消失，一些屬性將繼續(xù)保持存在。設(shè)想象些變換的過程中，圖形的一些屬性消失，一些屬性將繼續(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ù)鋵傩?，而面積不是拓?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)系總是不圓滿的。關(guā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)、線、面來表示，這種歸納正好地圖要素可以抽象為點(diǎn)、線、面來表示，這種歸納正好適合于建立拓?fù)潢P(guān)系和建立拓?fù)浔硎尽＿m合于建立拓?fù)潢P(guān)系和建立拓?fù)浔硎尽?.1.若地圖平面上反映一定意義的零維圖形的附近沒有其它圖形若地圖平面上反映一定意義的零維圖形的附近沒有其它圖形與之聯(lián)系，則稱這個(gè)零維圖形為獨(dú)立點(diǎn)與之聯(lián)系，則稱這個(gè)零維圖形為獨(dú)立點(diǎn)PointPoint）。如水井）。如水井3.3.地圖平面上連接兩結(jié)點(diǎn)的有一定意義的一維圖形稱為邊地圖平面上連接兩結(jié)點(diǎn)的有一定意義的一維圖形稱為邊EdgeEdge） ，也叫弧段，也叫弧段Ar

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

7、素之間注意是“偶對(duì)集合”）。一般用來描述面域鄰接。 拓?fù)潢P(guān)聯(lián)關(guān)系存在于不同類型元素之間。一般用來描述結(jié)點(diǎn)與邊、邊與面的關(guān)系。 拓?fù)浒P(guān)系用來說明面域包含于其中的點(diǎn)、弧段、面域的對(duì)應(yīng)關(guān)系。包含關(guān)系有同類的，也有不同類的。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線段號(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（一條弧線組成）Polygonarc表表弧線坐標(biāo)序列e15,3 5,5 8,5e67,4 6,3

10、 Arc坐標(biāo)表坐標(biāo)表2.Arc/Info多邊形與弧線拓?fù)浣Y(jié)構(gòu)多邊形與弧線拓?fù)浣Y(jié)構(gòu)弧 線左多邊形右多邊形e1AEe2ADe3ACe4ABe5EDe6BEe7BDe8BFe9DCe10CB弧線坐標(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ǔ)在Arc文件中）文件中）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)要素弧線和結(jié)點(diǎn)的基礎(chǔ)上表示附加的地理信息。也就是說：地理數(shù)據(jù)作為X，Y坐標(biāo)對(duì)序列來存儲(chǔ)，分別代表點(diǎn)、線、多邊

11、形。這些地理特征之間的關(guān)系通過拓?fù)浣Y(jié)構(gòu)來表達(dá)。相關(guān)的表格數(shù)據(jù)存儲(chǔ)在表格中，通過內(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)模型由組成多邊形邊界的弧的列表來構(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ǔ)兩次，這通常通過數(shù)字化兩次或者弧的拷貝來完成。這種重復(fù)數(shù)據(jù)是地理分析更為困難，因?yàn)橄到y(tǒng)不能夠觀察出這兩個(gè)多邊形的拓?fù)潢P(guān)系。非拓?fù)浣Y(jié)構(gòu)模型是許多CAD、繪圖和制圖系統(tǒng)支持的常見模型。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ù)獲取有各種不同的方法，但無論哪種方法獲取空間數(shù)據(jù)獲取有各種不同的方法，但無論哪種方法獲取的數(shù)據(jù)都可能存在這樣或者那樣的問題和誤差，如數(shù)字化錯(cuò)的數(shù)據(jù)都可能存在這樣或者那樣的問題和誤差，如數(shù)字化錯(cuò)誤、數(shù)據(jù)格式不一致、比例尺或投影不統(tǒng)一、數(shù)據(jù)冗余等。誤、數(shù)據(jù)格式不一致、比例尺或投影不統(tǒng)一、數(shù)據(jù)冗余等。 因此：只有通過空間數(shù)據(jù)的處理才能使空間數(shù)據(jù)符合因此：只有通過空間數(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ù)?、空間數(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、?；《蔚闹虚g相交：弧段的中間相交：要求中間斷開要求中間斷開弧段的端點(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 檢查多邊形閉合可檢查多邊形閉合可以通過判斷一條弧的以通過判斷一條弧的端點(diǎn)是否有與之匹配端點(diǎn)是否有與之匹配的端點(diǎn)來進(jìn)行。的端點(diǎn)來進(jìn)行。 圖中弧段圖中弧段a的端點(diǎn)的端點(diǎn)P沒

15、沒有與之匹配的端點(diǎn)，因有與之匹配的端點(diǎn)，因此無法使用這條弧與其此無法使用這條弧與其它弧組成閉合多邊形。它弧組成閉合多邊形。 可能的原因是：結(jié)點(diǎn)匹配限差的問題造成端點(diǎn)未匹配；數(shù)字化誤差較大，甚至數(shù)字化錯(cuò)誤，這些都可以通過圖形編輯或重新匹配來確定。另外如果該弧段本來就是懸掛弧線，不需要拓?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í)針方向構(gòu)建多邊形順時(shí)針方向構(gòu)建多邊形 所謂順時(shí)針方向構(gòu)建多邊形是指多邊形在弧段的右側(cè)。這所謂順時(shí)針方向構(gòu)建多邊形是指多邊形在弧段的右側(cè)。這需要定義弧線的方向。需要定義弧線的方向。AB左邊左邊右邊右邊左邊左邊右邊右邊AB2.4.1 基本常識(shí)基本常識(shí)2）2.2.最靠右邊的弧段最靠右邊的弧段acdb 最靠右邊的弧段是指從弧段的一個(gè)端點(diǎn)出發(fā)，在這個(gè)弧段的方向上最靠右邊的一條弧段。如圖：弧段如圖：弧段a a最靠右邊的弧段是最靠右邊的弧段是d.d. 找最靠右邊的弧段可以通過計(jì)算弧段的方向和夾角來實(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í)針方向構(gòu)成時(shí)，面積為正；否。根據(jù)該公式，當(dāng)多邊形右順時(shí)針方向構(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í)針方向順序記錄；按照數(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開始跟蹤，則圈定多邊形A的環(huán)