數(shù)字地圖制圖原理

前計(jì)算機(jī)技術(shù)的出現(xiàn)，對地圖的生產(chǎn)和應(yīng)用方式乃至地圖的含義都產(chǎn)生了深刻的和變革性的影響。數(shù)字地圖的生產(chǎn)過程不再是模擬以往的手工操作流程，取而代之的是計(jì)算機(jī)和現(xiàn)代通訊技術(shù)支持下的新的作業(yè)方式和作業(yè)要求。數(shù)字技術(shù)滲入地圖生產(chǎn)，給古老的地圖制圖學(xué)科帶來了新的發(fā)展機(jī)遇，同時(shí)也提出了新的挑戰(zhàn)，迫使地圖學(xué)者重新思考地圖學(xué)實(shí)踐并且更加從數(shù)量化的角度對待地圖學(xué)理論的發(fā)展。在此趨勢下，以數(shù)字制圖技術(shù)為支撐，出現(xiàn)了一些新的發(fā)展方向和研究領(lǐng)域，如地理信息系統(tǒng)、虛擬現(xiàn)實(shí)技術(shù)與虛擬地理環(huán)境、地圖模式識別技術(shù)、地圖數(shù)據(jù)庫技術(shù)、全數(shù)字化地圖生產(chǎn)系統(tǒng)、智能化數(shù)字地圖制圖系統(tǒng)、GPS技術(shù)與數(shù)字地圖的結(jié)合等，使與地理信息相關(guān)的學(xué)科之間的界限日益模糊，這對數(shù)字制圖技術(shù)今后的發(fā)展有著決定性的影響。數(shù)字地圖學(xué)作為地理空間前計(jì)算機(jī)技術(shù)的出現(xiàn)，對地圖的生產(chǎn)和應(yīng)用方式乃至地圖的含義都產(chǎn)生了深刻的和變革性的影響。數(shù)字地圖的生產(chǎn)過程不再是模擬以往的手工操作流程，取而代之的是計(jì)算機(jī)和現(xiàn)代通訊技術(shù)支持下的新的作業(yè)方式和作業(yè)要求。數(shù)字技術(shù)滲入地圖生產(chǎn)，給古老的地圖制圖學(xué)科帶來了新的發(fā)展機(jī)遇，同時(shí)也提出了新的挑戰(zhàn)，迫使地圖學(xué)者重新思考地圖學(xué)實(shí)踐并且更加從數(shù)量化的角度對待地圖學(xué)理論的發(fā)展。在此趨勢下，以數(shù)字制圖技術(shù)為支撐，出現(xiàn)了一些新的發(fā)展方向和研究領(lǐng)域，如地理信息系統(tǒng)、虛擬現(xiàn)實(shí)技術(shù)與虛擬地理環(huán)境、地圖模式識別技術(shù)、地圖數(shù)據(jù)庫技術(shù)、全數(shù)字化地圖生產(chǎn)系統(tǒng)、智能化數(shù)字地圖制圖系統(tǒng)、GPS技術(shù)與數(shù)字地圖的結(jié)合等，使與地理信息相關(guān)的學(xué)科之間的界限日益模糊，這對數(shù)字制圖技術(shù)今后的發(fā)展有著決定性的影響。數(shù)字地圖學(xué)作為地理空間1目錄第1目錄第1章緒 234567 矢量與矩 預(yù)處 1第8章數(shù)字地圖的標(biāo)準(zhǔn) 第8章數(shù)字地圖的標(biāo)準(zhǔn) 第9章數(shù)字地圖工 參考文 2第1計(jì)算機(jī)技術(shù)的發(fā)展及其在地圖學(xué)中的應(yīng)用對地圖制圖產(chǎn)生了深刻影響。在應(yīng)用早期，地圖學(xué)中已徹底改變了人們對地圖制圖的理解以及實(shí)踐的方式。同時(shí)，由于任何擁有制圖軟件包和合適硬件的人都能生產(chǎn)地圖或類似地圖的產(chǎn)品，因而計(jì)算機(jī)的應(yīng)用也影響了1.1計(jì)算機(jī)輔第1計(jì)算機(jī)技術(shù)的發(fā)展及其在地圖學(xué)中的應(yīng)用對地圖制圖產(chǎn)生了深刻影響。在應(yīng)用早期，地圖學(xué)中已徹底改變了人們對地圖制圖的理解以及實(shí)踐的方式。同時(shí)，由于任何擁有制圖軟件包和合適硬件的人都能生產(chǎn)地圖或類似地圖的產(chǎn)品，因而計(jì)算機(jī)的應(yīng)用也影響了1.1計(jì)算機(jī)輔助地圖制圖的發(fā)很難將計(jì)算機(jī)技術(shù)從數(shù)字地圖實(shí)踐中分離出來。很多解決實(shí)際問題的算法設(shè)計(jì)甚至理60年代初，制圖工作者的態(tài)度是“走一步看一步”；2）20世紀(jì)60年代末到70年代，制圖工在計(jì)算機(jī)運(yùn)用于地圖學(xué)領(lǐng)域的早期，制圖的專業(yè)外圍設(shè)備還不存在或者不成熟。圖1－1是一個(gè)包括中央處理器CPU的基本運(yùn)算系統(tǒng)。外圍存儲設(shè)備包括硬盤、磁帶機(jī)等，輸入設(shè)CPU1－1早期的制圖程序有如SYMAP和CMAP等，SYMAP系統(tǒng)軟件是由哈佛大學(xué)計(jì)算機(jī)圖象與空間分析實(shí)驗(yàn)室開發(fā)的，CMAP被設(shè)計(jì)用來使用行式打印機(jī)作為顯示設(shè)備。但是，標(biāo)準(zhǔn)的打印單元是1/6（或1/8英寸）乘1/10英寸大小，很難達(dá)到較高的圖形顯示的精度要求。另外，如1電傳打字機(jī)終端減少了將數(shù)據(jù)輸入到處理系統(tǒng)中的步驟。鍵盤使得用戶能直接將數(shù)據(jù)輸入到系統(tǒng)中，以往的卡片穿孔的做法已經(jīng)過時(shí)了。電傳打字終端促進(jìn)了交互式系統(tǒng)的發(fā)展，即同一單元既可作為輸入單元也可作為輸出單元。但是，電傳打字終端只能進(jìn)行硬拷，由于意識到計(jì)算機(jī)能處理空間信息，從而產(chǎn)生了對專業(yè)設(shè)備的需求。帶有專用打印頭的打印機(jī)得到了發(fā)展，其大小和符號均可改變。存儲管和陰極射線管的發(fā)展使得人們能在然而這些顯示技術(shù)的進(jìn)步，并不能使計(jì)算機(jī)輔助制圖過程自動(dòng)化，只是改善了輸出效果，但幾乎仍不能與低效的手工匹敵。數(shù)字化儀和掃描儀的引進(jìn)大大減少了數(shù)據(jù)輸入的工電傳打字機(jī)終端減少了將數(shù)據(jù)輸入到處理系統(tǒng)中的步驟。鍵盤使得用戶能直接將數(shù)據(jù)輸入到系統(tǒng)中，以往的卡片穿孔的做法已經(jīng)過時(shí)了。電傳打字終端促進(jìn)了交互式系統(tǒng)的發(fā)展，即同一單元既可作為輸入單元也可作為輸出單元。但是，電傳打字終端只能進(jìn)行硬拷，由于意識到計(jì)算機(jī)能處理空間信息，從而產(chǎn)生了對專業(yè)設(shè)備的需求。帶有專用打印頭的打印機(jī)得到了發(fā)展，其大小和符號均可改變。存儲管和陰極射線管的發(fā)展使得人們能在然而這些顯示技術(shù)的進(jìn)步，并不能使計(jì)算機(jī)輔助制圖過程自動(dòng)化，只是改善了輸出效果，但幾乎仍不能與低效的手工匹敵。數(shù)字化儀和掃描儀的引進(jìn)大大減少了數(shù)據(jù)輸入的工更為重要的是，電腦及其相關(guān)的數(shù)字硬件包括掃描儀和傳感器使得人們能對感興趣的空間分布進(jìn)行顯示和分析。數(shù)字地圖學(xué)與數(shù)字圖象處理、計(jì)算幾何等一起在土木工程、計(jì)算機(jī)科學(xué)、應(yīng)用數(shù)學(xué)和資源與環(huán)境科學(xué)領(lǐng)域的應(yīng)用正在興起。這些領(lǐng)域傳統(tǒng)上的界限變得越來越模糊，制圖工作者不再是空間顯示與分析領(lǐng)域的唯一參與者，甚至不一定是主要參與者。地圖學(xué)與數(shù)字地圖學(xué)包孕在地理信息科學(xué)（GIScience）或地球空間信息科學(xué)（Geomatics）1.2數(shù)字地圖的數(shù)據(jù)模型根據(jù)傳統(tǒng)地圖的特性（可視性和真實(shí)可觸性）可將地圖分為實(shí)地圖（RealMap）地圖（VirtualMap，其中虛地圖又分三類，見表1－1。實(shí)地圖是能直接可視和永久存在的任何制圖產(chǎn)品，它包括大多數(shù)傳統(tǒng)地圖產(chǎn)品。第一類虛地圖，能直接可視，但只具有短不能直接作為地圖可視，存儲在介質(zhì)中的空間數(shù)據(jù)可歸為此類；第三類虛地圖，是既沒有表1－1地圖產(chǎn)品的分 CRT211除了地圖形式外，地圖的另外一個(gè)重要特征是功用。地圖要實(shí)用，就必須能將信息有效地傳遞給讀者。讀者能從地圖的信息提示中區(qū)分新的或不同的信息。在地圖生產(chǎn)時(shí)，制基于這一點(diǎn)，可以認(rèn)為地圖是對現(xiàn)實(shí)環(huán)境的制圖抽象。這個(gè)抽象過程包括對地圖信息的選取、分類、化簡和符號化。信息的選取取決于地圖的用途，分類是按照地圖目標(biāo)屬性的一致性或相似性進(jìn)行歸類，化簡用來剔除不必要的細(xì)節(jié)，符號化是用地圖符號呈現(xiàn)真實(shí)（Peuqet1984（Icnicmodels）僅通過比例縮放來再現(xiàn)現(xiàn)實(shí)世界，如海岸線侵蝕模型。它試圖通過縮小尺寸來保持真實(shí)世模擬模型Analogmodels）主要是根據(jù)（Symbolicmodels）用符號來表達(dá)地理特征，它是對現(xiàn)實(shí)世界的高度理想化的再現(xiàn)。實(shí)地圖是模擬模型與符號模型的（表）（，見圖－2，前者就是模擬模型，因?yàn)樗鼘⒄鎸?shí)世界按比例縮放以繪制到地圖上的，后者就是符號模型，因?yàn)樗砸环N抽象的地圖語言（如分級圓、面狀填充等）來表達(dá)屬性信息。計(jì)算機(jī)技術(shù)給地圖數(shù)據(jù)模型帶來的一個(gè)重大影響就是將地理底圖進(jìn)一步抽象成作為符，1999王家耀，20013（c）（a）（b）1－2專題地圖模型1.3地圖數(shù)據(jù)處理系1－3a（c）（a）（b）1－2專題地圖模型1.3地圖數(shù)據(jù)處理系1－3a1－3b數(shù)據(jù)處輸輸數(shù)據(jù)采數(shù)據(jù)應(yīng)數(shù)據(jù)存(a)程序控制算法單地圖(輸入地圖(輸出存儲單(b)41地圖信息處理系統(tǒng)是將地圖信息從一種形式轉(zhuǎn)換為另一種形式的一系列變換過程。先是進(jìn)行數(shù)據(jù)采集變換，這時(shí)的核心問題是對原始數(shù)據(jù)進(jìn)行篩選；然后，采集的數(shù)據(jù)又要在1地圖信息處理系統(tǒng)是將地圖信息從一種形式轉(zhuǎn)換為另一種形式的一系列變換過程。先是進(jìn)行數(shù)據(jù)采集變換，這時(shí)的核心問題是對原始數(shù)據(jù)進(jìn)行篩選；然后，采集的數(shù)據(jù)又要在拷貝地圖，見圖1－4。原始數(shù)據(jù)通過數(shù)據(jù)獲取從現(xiàn)實(shí)世界提取出來，進(jìn)而通過數(shù)據(jù)組織轉(zhuǎn)1－4計(jì)算機(jī)技術(shù)給地圖學(xué)帶來的另一個(gè)重大沖擊是數(shù)據(jù)處理系統(tǒng)功能的分離。存儲（5第2我們怎樣使計(jì)算機(jī)能數(shù)字化地“看見”人們以視覺方式看到的東西呢？這是數(shù)字地圖學(xué)所要面臨的一個(gè)基本問題。多少世紀(jì)以來，人們一直以直尺和圓規(guī)等繪圖工具來手工繪第2我們怎樣使計(jì)算機(jī)能數(shù)字化地“看見”人們以視覺方式看到的東西呢？這是數(shù)字地圖學(xué)所要面臨的一個(gè)基本問題。多少世紀(jì)以來，人們一直以直尺和圓規(guī)等繪圖工具來手工繪械筆或電子束進(jìn)行自動(dòng)化繪圖的一系列指令。這是比較復(fù)雜的，因?yàn)闅W幾里德幾何學(xué)是通過邏輯參數(shù)推演以及經(jīng)過證明的定理和公理來解決問題的，現(xiàn)在要將其替換為以代數(shù)方法這個(gè)轉(zhuǎn)換的意義已經(jīng)超出了僅僅是對地圖產(chǎn)品的復(fù)制。在數(shù)字地圖學(xué)中，已經(jīng)沒有視覺上經(jīng)驗(yàn)的限制。氣壓、氣溫或土地收益等的三維表面，它們不具有自然可視性，但可以由于地圖目標(biāo)是模塊化的，因此復(fù)雜目標(biāo)都是由簡單的原子目標(biāo)組成。制圖操作也是模塊化的，后面章節(jié)所講述的復(fù)雜操作也都是由許多簡單操作組成的。數(shù)字地圖學(xué)與解析幾何、計(jì)算幾何關(guān)系甚密。限于篇幅和課時(shí)，本章將介紹解析幾何的基礎(chǔ)知識，以為數(shù)字2.1地圖與幾何學(xué)的基本關(guān)數(shù)字地圖學(xué)的發(fā)展需要建立一個(gè)能處理空間事物的概念框架。描述空間事物的分布特地圖是表達(dá)這些空間概念的媒介，它與幾何學(xué)一樣，也作為一種空間語言。盡管幾何1700年前的古埃及時(shí)代，但是第一次用幾何學(xué)系統(tǒng)地解決現(xiàn)實(shí)世界問題還要3說，提出了一個(gè)新的幾何學(xué)說，稱為雙曲線幾何學(xué)（HyperbolicGeometry62幾何分析基礎(chǔ)xX合X可記為X=2幾何分析基礎(chǔ)xX合X可記為X={x1,x2,x3…,xn}，元素xxX。舉例來說，我們將集合X定義為華東地區(qū)所有六省一市名稱的集合，的每個(gè)元素都是它本身的集合，如上海市本身就是具有一個(gè)元素（即上海市）的集合，上素構(gòu)成。如果X中的每個(gè)元素也是Y中的元素，那么X就是YXY交集是指兩個(gè)集合的共同元素，記為X∩Y＝{x｜x∈Xandx∈Y}，即既屬于X又屬于Y的元素。舉例來說，假定X是構(gòu)成湖北省輪廓線的點(diǎn)集，Y是在同一地圖上構(gòu)成河南省輪廓并集是指包括兩個(gè)集合所有元素的集合，記為(X∪Y)＝{x｜x∈Xorx∈Y}，兩個(gè)集差集，記為(X－Y)＝{x｜x∈XandxY}，2－2a7（a）（b）笛卡爾積，給定兩個(gè)集合X和Y，一個(gè)新的集合稱為X和Y的笛卡爾積，記為Xx（x,y）｜x∈Xy是YX，Y是中南地區(qū)（即湖北省，河南省，湖南省，（a）（b）笛卡爾積，給定兩個(gè)集合X和Y，一個(gè)新的集合稱為X和Y的笛卡爾積，記為Xx（x,y）｜x∈Xy是YX，Y是中南地區(qū)（即湖北省，河南省，湖南省，Z＝XxY＝（（yf稱為函數(shù)，因此函數(shù)關(guān)系可以記為。假設(shè)X是中國各省的集合，關(guān)系 x,y)|省x與省y共享一條邊界，x的定義域和y的值域是所有與其他省共邊的省。省共享，則這個(gè)關(guān)系便不是一個(gè)函數(shù)。然而，如果X是我國所有居民地的集合，關(guān)系民地，但都只有一個(gè)省府。函數(shù)還可以是表達(dá)定義域與值域之間的多對一關(guān)系，所以值域中的某個(gè)元素可能對應(yīng)定義域中的多個(gè)元素，但定義域中的每個(gè)元素只能有一個(gè)值域中的二元函數(shù)，定義域中的每個(gè)元素只對應(yīng)一個(gè)值域上的元素，值域上的每個(gè)元素也只對應(yīng)定義域上的一個(gè)元素。二元函數(shù)也稱為變換。設(shè)X是所有居民地的集合，則關(guān)系2－3等面積變換8EXY Y2幾何分析基礎(chǔ)2－4相似性變換2幾何分析基礎(chǔ)2－4相似性變換2－5仿射變換投影變換：圖2－6，距離、角度甚至平行關(guān)系都不再保持不變，因此，目標(biāo)的面積與形狀都可能改變。投影變換用于地圖投影和測量當(dāng)中。等面積投影對于維持形狀的真實(shí)性2－6投影變換拓?fù)渥儞Q：圖2－7，幾乎在所有的地圖中，不管距離與方向如何變化，都能保持地圖目標(biāo)間的連接性。在拓?fù)鋷缀沃?，只有連通性與鄰接關(guān)系能得到保持。早期數(shù)字地圖發(fā)展2－7拓?fù)渥儞Q9（NCDCFD，1988（NCDCFD，19882.2地圖目數(shù)字地圖目標(biāo)的本質(zhì)是由數(shù)字圖象編制的模式即數(shù)據(jù)模型決定的。矢量數(shù)據(jù)模型和柵2－8。柵格空間也(a)2－8不同的格網(wǎng)模型（b）美國數(shù)字地圖數(shù)據(jù)標(biāo)準(zhǔn)國家委員會[NCDCDS，1988]已經(jīng)為數(shù)字地圖目標(biāo)建立了多種定義。首先，地圖目標(biāo)應(yīng)能夠組合空間屬性的絕對位置和相對位置概念。NCDCDS采用了“幾何”與“拓?fù)洹毙g(shù)語，而不采用絕對位置和相對位置概念；第二，地圖目標(biāo)必須是模塊化的，使得低維目標(biāo)可以用來定義高維目標(biāo)；第三，地圖目標(biāo)能夠明顯標(biāo)識所代表的地理實(shí)體，可以通過幾何學(xué)中的平面、雙曲線及橢圓等來研究。這意味著可能要用到平面或球面 02幾何分析基礎(chǔ)12幾何分析基礎(chǔ)1（a）（b）（c）(（d）（e）2－9一維目標(biāo)2－102（a）（c）（d）（e）圖2－12（a）（b）（c）（a）（c）（d）（e）圖2－12（a）（b）（c）（d）2－122幾何分析基礎(chǔ)2幾何分析基礎(chǔ)2.3笛卡爾坐標(biāo)最簡單的幾何目標(biāo)是點(diǎn)，最簡單的代數(shù)目標(biāo)是實(shí)數(shù)或標(biāo)量。所有的實(shí)數(shù)都可以通過幾一個(gè)對應(yīng)點(diǎn)?？潭染€建立了幾何點(diǎn)和代數(shù)數(shù)值之間的對應(yīng)關(guān)系。刻度線上的點(diǎn)p就是實(shí)數(shù)r的圖形表達(dá)。反過來，對于每個(gè)實(shí)數(shù)r，刻度線上只存在唯一點(diǎn)p與之對應(yīng)，它們是一一對p2－13刻度線為x的絕對值，記為|x|。一個(gè)數(shù)值的絕對值表示其與原點(diǎn)的距離，而不管其位于原點(diǎn)的左2-14數(shù)與點(diǎn)的對應(yīng)與坐標(biāo)軸正交的直線與坐標(biāo)軸的交點(diǎn)確定的，如圖2－15。通常，先給出X值，（x,y）就是點(diǎn)p的坐標(biāo)值，也記作p與坐標(biāo)軸正交的直線與坐標(biāo)軸的交點(diǎn)確定的，如圖2－15。通常，先給出X值，（x,y）就是點(diǎn)p的坐標(biāo)值，也記作p(xy)。在笛卡爾坐標(biāo)系中，X值稱為橫坐標(biāo)，Y值稱為縱坐標(biāo)。、Ⅱ、Ⅲ和Ⅳ，圖為正；第二象限，X值為負(fù)，Y值為正；第三象限，X和Y值均為負(fù)；第四象限，X值為正，Y因?yàn)樵c(diǎn)的位置可以任意設(shè)定，在很多情況下，只需要利用第一象限（正象限）2.5節(jié)，我們將看到如何將其它象限的地理特征移到第一象限。這種將二維空間劃分成四部分的方法也是柵格型四叉樹結(jié)構(gòu)的基礎(chǔ)（。有些顯示系統(tǒng)中，縱坐標(biāo)軸上的正值在原點(diǎn)以下。2－15笛卡爾坐標(biāo)平面2－162－172幾何分析2－172.42幾何分析2－172.4矢量與矩2－18矢量示例2－192－182－19值為2－182－19值為x坐標(biāo)－2 1（1，2（2，42－20分矢量2－21矢量坐標(biāo)2幾何分析基礎(chǔ)|a|(2幾何分析基礎(chǔ)|a|(x2y2)1/例如，如果a＝(1,2)，則其模為｜a｜＝(1＋4)1/2|pq|[(xx)2(yy)2]1/ 如果a＝(23)，b＝(14)，則ab相加為新矢量a＋b＝(2＋13＋4)，即為（37。2－22矢量相加同理，矢量相減也是各分量相減，矢量a-b是(2－13－4)即（1,－1。幾何上，盡管a＋b等于b＋a，但是a－b不等于矢量b－a。上例中，b-a為（1－24－3）即（－112－24標(biāo)量與矢量相乘如果h＝2，矢量a＝(23)，則標(biāo)量與其相乘后的結(jié)果為（2×22×3）即（46。如標(biāo)量倍，圖2－24。上例中，矢量(46)的模為213，它是原矢量a的模13的2倍。如,，a′＝（x′，y′標(biāo)量倍，圖2－24。上例中，矢量(46)的模為213，它是原矢量a的模13的2倍。如,，a′＝（x′，y′ y/|a點(diǎn)積。矢量乘積是各分量相乘的積。如果矢量a＝(x1,y1)和b＝(x2,y2)abx1x2y1例如，如果a＝(23)和b＝(14)，那么a·b＝(2)(1)＋(3)(4)，即14。其實(shí)，矢量的模就是該矢量本身內(nèi)積的平方根，即|a|xxyy)12。ab|a||b|所 cosab/|a||bAa12a22Ax2y22幾何分析基礎(chǔ) 數(shù)，矩陣的和即為兩個(gè)矩陣對應(yīng)元素相加后所得的矩陣，例如，如果A 3 1 2幾何分析基礎(chǔ) 數(shù)，矩陣的和即為兩個(gè)矩陣對應(yīng)元素相加后所得的矩陣，例如，如果A 3 1 BAB64A＋B＝B＋A（A＋B）＋C＝A＋（B＋CCijai1b1ai2b2jL例如：A 3和B 1(4)(3)3AB(2)(3)(2)(2)(2)(2)966(AB)C＝A(BC)，A(B＋C)＝AB＋AC的第i列，A的第j列變?yōu)锳T的第j行。對稱矩陣S，是一個(gè)方陣，其元素S＝S 轉(zhuǎn)置矩陣就是它本身，即S＝ST2×2x2y1，b＝（2，C2yy2|C|(x1y2|C|(x1y2x2y12－26在圖2－26中，矢量(2,3)和(5,1)組成的平行四邊形的面積是｜2·1－3·5｜＝｜2－行列式還可用于確定一個(gè)矢量位于另一個(gè)矢量的左邊還是右邊。用第一個(gè)矢量將平面正，則第二個(gè)矢量在左半平面。在圖2－26中，行列式的值為負(fù)，因此矢量（5,1）在矢量(2,3)的右半平面。這個(gè)結(jié)論很重要，因?yàn)樗苁箼C(jī)算機(jī)通過計(jì)算來確定矢量間的關(guān)2.5圖形的幾何變2.5.1點(diǎn)的（比例投影等各種變換。如前所述，幾何圖形的面由線組成，線是點(diǎn)的軌跡，因此構(gòu)成圖形的最基本要素是點(diǎn)。在解析幾何中，點(diǎn)可以用矢量表示。在二維空間中可用x,y）表示平面上的一點(diǎn)，因此，可以用點(diǎn)的集合（點(diǎn)集來表示一個(gè)平面圖形。當(dāng)然在三維空間中也可以用來表示三維立體。舊點(diǎn)集2幾何分析基礎(chǔ)2.5.2二維基本 若（x,y）為變換前坐標(biāo)，T2幾何分析基礎(chǔ)2.5.2二維基本 若（x,y）為變換前坐標(biāo)，T d為變換矩陣，則有baxbxdy d2.5.2.1x'xy'yy2－27bTd但由于二維圖形的點(diǎn)集矩陣是n2階的，而變換矩陣是32階的，根據(jù)矩陣乘法規(guī)則，它們是無法相乘的。為此把點(diǎn)矢量也作擴(kuò)充，將x y擴(kuò)充為x 擴(kuò)充為n3階矩陣。這樣，點(diǎn)集矩陣與變換矩陣即可進(jìn)行乘法運(yùn)算。bdaxcy bxdy 0令變換矩陣中的b,c=0，a,d=1，就得到平移變換矩陣：T 1，則有t bdaxcy bxdy 0令變換矩陣中的b,c=0，a,d=1，就得到平移變換矩陣：T 1，則有t 0 1x ym 這里k，m即為Tx、Ty，分別為X，Y為使二維變換矩陣具有更多的功能，可將32變換矩陣進(jìn)一步擴(kuò)充為33m01TT101 1xy 1 xy例如，令Tx=10，Ty＝10，則對A(10,26)，B(10,10)和C(20,10)構(gòu)成的平面三角形ABCxy 101AB11 1C在上述討論中，將（x，y）擴(kuò)充為（x,y量，將（xy1）看作Z=1平面上的點(diǎn)。也就是說。經(jīng)此擴(kuò)充后，圖形落在Z=1的平面上。將n維坐標(biāo)變?yōu)閚+1維坐標(biāo)。二維點(diǎn)（x,y）的齊次坐標(biāo)是（hx,hy,h，h是任意非零標(biāo)量。通過增加一個(gè)第三維分量（h＝1，任一二維矢量（x,y）可被轉(zhuǎn)換成一個(gè)齊次矢量（x,y,1。任一三維點(diǎn)（a,b,c）可轉(zhuǎn)換成二維點(diǎn)(a/c,b/c)。（x,y）的齊次轉(zhuǎn)換是一個(gè)經(jīng)過原點(diǎn)和點(diǎn)（x,y,1）的射線軌跡，見圖2－28。用一個(gè)非零標(biāo)量與一個(gè)三維齊次矢量相乘，不會改變該矢量的二維形式。如果m是個(gè)非零標(biāo)量，則齊次矢量(a,bc)和(ma,mb,mc)都等價(jià)于(a/c,b/c)。2.5.2.22幾何分析x'xcosyy'xsiny2幾何分析x'xcosyy'xsinyT r 1 12.5.2.3縮放操作也稱為比例變換。可對原始坐標(biāo)（xy）下的矢量產(chǎn)生拉長或縮短的效果。x'Sxy'Sy0TSsy0 在圖2－30中，通過設(shè)定比例因子Sx＝0.5，Sy＝0.5，原始坐標(biāo)8）4。當(dāng)Sx和Sy小于1和（6,8）的射線縮小成新的點(diǎn)（3,們大于1時(shí)，幾何目標(biāo)被放大；當(dāng)Sx＝Sy時(shí)，縮放后將保持原有的方向和大小。如果2.5.2.410令 4。當(dāng)Sx和Sy小于1和（6,8）的射線縮小成新的點(diǎn)（3,們大于1時(shí)，幾何目標(biāo)被放大；當(dāng)Sx＝Sy時(shí)，縮放后將保持原有的方向和大小。如果2.5.2.410令 Tsh101 1 1(shx 2－32所示，經(jīng)此變換后，Y坐標(biāo)不變，XshxY，這就相當(dāng)于原來YX方向錯(cuò)切成角的直線，且有tgyshxy1/shxshx>0時(shí)沿+X向錯(cuò)切；shx<0時(shí)，沿-X10 1 (shy角且tgxshyx1shyshy>0時(shí)沿+Y向錯(cuò)切；shy<0時(shí)，沿-Y2－322.5.3二維組合些變換僅用一種基本變換是不能實(shí)現(xiàn)的，必須由兩種或多種基本變換的組合才能實(shí)現(xiàn)。這2幾何分析基礎(chǔ)2－32 0 0002幾何分析基礎(chǔ)2－32 0 0001 1 相反地，C＝S·T 0 0 0 1 1 等都是一系列點(diǎn)轉(zhuǎn)換的結(jié)果。每個(gè)轉(zhuǎn)換從原始點(diǎn)(x,y)產(chǎn)生新的點(diǎn)(x′,y′)。2.6點(diǎn)線關(guān)＋C＝0L((xy|xR,yR,且AxByC2－33直線 1（－A/B，（－C/B（－C/A2－33直線 1（－A/B，（－C/B（－C/Aymxp(x1y2)到點(diǎn)q(x2,y2)的直線參數(shù)用矢量法表示y1x y2x1y1x2q到點(diǎn)py2x y1x2y2x1A/B（A2L{(x1,y1)h(x2x1,y2y1)|h2幾何分析（a）（b）2－35標(biāo)準(zhǔn)化直線連接p到q的矢量（x2－x1y2－y2幾何分析（a）（b）2－35標(biāo)準(zhǔn)化直線連接p到q的矢量（x2－x1y2－y1）也可以用直線表達(dá)式中的參數(shù)－矢量”式保持了直線的方向。h的值在閉區(qū)間[0l{q(1)p|01]A/(A2B2)1/2B2)1/2B/(C/(A2B2)1/235對于平面上任一點(diǎn)t(xt,yt)相對于直線L的位置關(guān)系，可以借助連接p到q的直線L計(jì)算SAxtBytL上。舉例來說，連接點(diǎn)（22）和（45）點(diǎn)（6,3）在這條直線的順時(shí)針半平面，因（－3（6（2（3＋2SAxtBytL上。舉例來說，連接點(diǎn)（22）和（45）點(diǎn)（6,3）在這條直線的順時(shí)針半平面，因（－3（6（2（3＋2＝－10＜0反，點(diǎn)（05）在這條直線的逆時(shí)針半平面，（－3（0）＋（2（5）＋2＝12＞0與直線L平行的直線L′上的所有點(diǎn)，中，點(diǎn)（4,0）在與直線：－3x＋2y＋2＝0平行的直線L′上，L′經(jīng)過點(diǎn)（63），＋2，也等于－10。一般而言，直線L的關(guān)122－37中，點(diǎn)t與直線L dB2)1/(上例中，點(diǎn)（6,3）與直線－3x＋2y＋2＝0p（x1,y1）q（x2,y2）r（xr,yr）4)1/(x1x2)/xry(yy)/ r2－38中，點(diǎn)（2,2）與點(diǎn)（6,9）之間的中點(diǎn)是（8/2,11/2P則P2幾何分析x1 y 2幾何分析x1 y [(x2y2)(x2y2)]1/2 圖2－39中，點(diǎn),2）與（4,5）2252)(2222)]1/2兩條直線Ax＋By＋C＝0與Ex＋Fy＋G＝0的交點(diǎn)i(xi,yi)(GBFC)/(FAxiy(CEAG)/(FAi 在圖2－40中直線－3x＋2y＋2＝0與2x＋4y－28＝0xi [(28)(2)(4)(2)]/[(4)(3)(2)(2)]y[(2)(2)(3)(28)]/[(4)(3)i (64)(80)2－40兩直線的交點(diǎn)然而，當(dāng)要找出兩條線段的交點(diǎn)是否存在，而不是計(jì)算兩條直線的交點(diǎn)時(shí)，將產(chǎn)生很多問題。通常我們需要兩個(gè)步驟：首先按直線等式求出交點(diǎn)，再確定交點(diǎn)是否位于某條線S 然而，當(dāng)要找出兩條線段的交點(diǎn)是否存在，而不是計(jì)算兩條直線的交點(diǎn)時(shí)，將產(chǎn)生很多問題。通常我們需要兩個(gè)步驟：首先按直線等式求出交點(diǎn)，再確定交點(diǎn)是否位于某條線S ＋5y＋9＝0(3)/512/S4/55/2/59/132－42b2－42c2幾何分析基礎(chǔ)2.7線與面的測2幾何分析基礎(chǔ)2.7線與面的測nxi)(yi1yi2其中，（xiyi）2.5節(jié)中講的，一個(gè)多邊形可以由內(nèi)外輪邊）的右側(cè)。這種a）（b）2－43a26。因此由n條邊構(gòu)成的多邊形面積便是：nrea(1/2)(xiyi1xi1yi其中，（xiyi）利用外輪廓線的順時(shí)針約定，第i+1個(gè)矢量位在第i個(gè)矢量的順時(shí)針半平面的三角形的線之外的那些三角形的面積被刪除，外輪廓線確定的面積為正。反過來，對于內(nèi)輪廓線也6，(1/2)[(4(1/2)[(4312)(2734)(4676)(6266)(6124)](1/2)[(10)(2)(18)(24)(2)(1/2)[(3435)(3544)(435(1/2)[(3)(9)(3)](3/則該多邊形總的面積是[(16)＋(－3/2)]即14.5－43bnrea1/2(xi1xi)(yi1yi其中（xi,yi）2幾何分析基礎(chǔ)2幾何分析基礎(chǔ)2－452.8本章小第3數(shù)字制圖處理系統(tǒng)中的核心問題是數(shù)字表達(dá)，它是原始數(shù)據(jù)與任何地圖顯示形式的中介。在第二章中我們知道了幾何目標(biāo)怎樣通過坐標(biāo)系轉(zhuǎn)換為數(shù)字形式，并且學(xué)到了一些用于形成高級算法的一系列基本操作。然而在設(shè)計(jì)算法的時(shí)候，我們不可能將這些操作算子第3數(shù)字制圖處理系統(tǒng)中的核心問題是數(shù)字表達(dá)，它是原始數(shù)據(jù)與任何地圖顯示形式的中介。在第二章中我們知道了幾何目標(biāo)怎樣通過坐標(biāo)系轉(zhuǎn)換為數(shù)字形式，并且學(xué)到了一些用于形成高級算法的一系列基本操作。然而在設(shè)計(jì)算法的時(shí)候，我們不可能將這些操作算子從地圖抽象到設(shè)計(jì)最后的地圖數(shù)據(jù)庫，是通過一系列的步驟將非常抽象的地圖目標(biāo)變?yōu)榉浅＞唧w的表達(dá)。真實(shí)世界（至少是其影像）通過高度的抽象和多種綜合（如選取、化簡）形成一個(gè)數(shù)據(jù)模型，并逐步轉(zhuǎn)換為更具針對性的數(shù)據(jù)結(jié)構(gòu)，并最終形成文件或數(shù)據(jù)庫結(jié)構(gòu)。在數(shù)據(jù)庫設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)以圖表、鏈表和數(shù)組來表達(dá)數(shù)據(jù)模型，并被集成進(jìn)算法3.1拓?fù)涓拍罨c解析幾何學(xué)中的代數(shù)關(guān)系形成對照，這里所要講的數(shù)據(jù)結(jié)構(gòu)是建立在拓?fù)潢P(guān)系之上的。拓?fù)鋵W(xué)（topology）一詞起源于希臘，主要研究目標(biāo)的形態(tài)。拓?fù)鋵W(xué)是幾何學(xué)的分支之一，作為近代數(shù)學(xué)的一門基礎(chǔ)理論學(xué)科，拓?fù)鋵W(xué)已經(jīng)滲透到數(shù)學(xué)的許多分支以及物理、數(shù)字地圖圖形在一定區(qū)域內(nèi)采用某種地圖投影，是將地面投影于平面的拓?fù)溆成?。在拓?fù)溆成渲?，點(diǎn)映射為點(diǎn)，線映射為線，面映射為面，面內(nèi)的點(diǎn)映射后仍在面內(nèi)，與點(diǎn)關(guān)聯(lián)的線映射后仍然與線相關(guān)聯(lián)。因此，數(shù)字地圖的點(diǎn)、線、面具有拓?fù)湫再|(zhì)，點(diǎn)、線、面是基本的拓?fù)湓亍Ｓ捎谕負(fù)鋵W(xué)是研究圖形在同胚變化下不變的性質(zhì)，拓?fù)鋵W(xué)已成為數(shù)字地圖學(xué)、地理信息系統(tǒng)以及空間關(guān)系的理論基礎(chǔ)，為空間點(diǎn)、線、面之間的包含、覆蓋、開集是指度量空間D中一個(gè)鄰域G（GD，其每個(gè)點(diǎn)都是G的內(nèi)點(diǎn)?？占?和A本身也（{A?}3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)在Rn歐氏空間中，如果Rn中所有的點(diǎn)與點(diǎn)p的距離都在ε距離之內(nèi)(一個(gè)非常小的距（a）（b）3－2相離與相交子集3－1當(dāng)且僅當(dāng)集合S不能表示為兩個(gè)相離的開子集之并時(shí)，稱S為相連的。在圖3－2a中，S是相離子集X和W的并，因此S是不相連的集合。在圖3－2b中，X和W重疊，它們的交集是非許多不同的制圖目標(biāo)可以歸為相連或不相連的集合。圖3－3a當(dāng)且僅當(dāng)集合S不能表示為兩個(gè)相離的開子集之并時(shí)，稱S為相連的。在圖3－2a中，S是相離子集X和W的并，因此S是不相連的集合。在圖3－2b中，X和W重疊，它們的交集是非許多不同的制圖目標(biāo)可以歸為相連或不相連的集合。圖3－3a中美國夏威夷群島,阿拉斯加和鄰接的48中，Connecticut（CT）與Massachusetts（MA）3－33章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)一對相關(guān)聯(lián)的單元在結(jié)構(gòu)上具有對稱性稱為對偶。在對偶關(guān)系中，原始目標(biāo)或關(guān)系可以被相對應(yīng)的對偶目標(biāo)或關(guān)系取代。原始目標(biāo)可以認(rèn)為是初始目標(biāo)，對偶目標(biāo)可認(rèn)為是初始目標(biāo)的配對物。如目標(biāo)的組成和構(gòu)造是關(guān)聯(lián)關(guān)系的兩個(gè)對偶方面。0維單元是2維單元的對偶，1維單元是1維單元的對偶。這些關(guān)系可以在圖3－4的圖解中看到，原始目標(biāo)由實(shí)線A)是一對原始關(guān)聯(lián)關(guān)系，1維單元a構(gòu)造二維單元A，A由a組成，在(a,A)的對偶關(guān)系中，1維單元a0維單元A組成，而A反過來構(gòu)造a。對偶關(guān)系闡明了2維對應(yīng)物的可定向性。當(dāng)從0維單元1指向0維單元4時(shí)，2維單元A則在右邊，2維單元B則在左邊。在對偶關(guān)系中這種方圖 初始目標(biāo)及其對利用圖表，每個(gè)子集(或目標(biāo))Si和包含它們的集合S都可表示為圓圈，每個(gè)成員Si和集對于可連接集合S，如果子集Si最多只和兩個(gè)其它的子集鄰接，那么{Si}便在S上形成（a）3－6路徑拓?fù)洌╞）3－7網(wǎng)絡(luò)拓?fù)淙魏我粋€(gè)不可連接的集合都可分解為一系列可連接的子集。這些可連接的子集本身也可形成路徑拓?fù)浠蚓W(wǎng)狀拓?fù)?，并通過鄰接關(guān)系聯(lián)結(jié)。在圖3－8a中，集合S由兩個(gè)不相連的（a）3－6路徑拓?fù)洌╞）3－7網(wǎng)絡(luò)拓?fù)淙魏我粋€(gè)不可連接的集合都可分解為一系列可連接的子集。這些可連接的子集本身也可形成路徑拓?fù)浠蚓W(wǎng)狀拓?fù)?，并通過鄰接關(guān)系聯(lián)結(jié)。在圖3－8a中，集合S由兩個(gè)不相連的3－8（Cobound3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)3.2文件結(jié)3.2.1表結(jié)文件結(jié)構(gòu)決定目標(biāo)在硬件存儲中的具體組織形式。在數(shù)據(jù)組織中，為了表達(dá)包含拓?fù)浜投攘繉傩缘臄?shù)據(jù)元素間的相互關(guān)系，提出了不同的文件結(jié)構(gòu)。每個(gè)目標(biāo)都稱為節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包括了一系列的屬性或域，它們定義了目標(biāo)的某些特性。舉例來說，將我國城市作為節(jié)點(diǎn)，則每個(gè)節(jié)點(diǎn)代表一個(gè)城市，它的屬性可能包括人口、下崗率、緯度、經(jīng)度等。正如第二章講述，拓?fù)渥儞Q保持了目標(biāo)間的鄰接關(guān)系。如果一個(gè)目標(biāo)鄰域中不包括任何其他象的數(shù)據(jù)模型和數(shù)據(jù)結(jié)構(gòu)中可能會有這些集合，但在具體的文件結(jié)構(gòu)中不會存在。在文件結(jié)構(gòu)中，所有的節(jié)點(diǎn)都存儲在介質(zhì)中的一定位置。在計(jì)算機(jī)中，節(jié)點(diǎn)是按地址存取的。集3－9線性表線性表是一個(gè)節(jié)點(diǎn)集合，它是以表中相對位置表示的開路徑拓?fù)?。表中的第一個(gè)節(jié)點(diǎn)是節(jié)點(diǎn)(j－1)和節(jié)點(diǎn)(j1)的鄰域，節(jié)點(diǎn)(j－1)是節(jié)點(diǎn)j(j＋1)j的后繼節(jié)點(diǎn)。頭節(jié)點(diǎn)沒有前趨節(jié)點(diǎn)，3－中，集合S中的所有節(jié)點(diǎn)根據(jù)LB、K、、E和相繼。刪除第j個(gè)節(jié)點(diǎn)；總是在頭或尾節(jié)點(diǎn)進(jìn)行插入、刪除和訪問修改操作的特殊表稱為堆棧、隊(duì)列或雙向隊(duì)列。堆棧是只在一端進(jìn)行插入和刪除操作的表(圖3－10a)。隊(duì)列是指在一端進(jìn)行插入，在（a）（c）總是在頭或尾節(jié)點(diǎn)進(jìn)行插入、刪除和訪問修改操作的特殊表稱為堆棧、隊(duì)列或雙向隊(duì)列。堆棧是只在一端進(jìn)行插入和刪除操作的表(圖3－10a)。隊(duì)列是指在一端進(jìn)行插入，在（a）（c）3-10SL、B、K、X、E和C。根節(jié)點(diǎn)地址是基地址s，s+n，其中n是每個(gè)節(jié)點(diǎn)所占的存儲空間大小。第二個(gè)節(jié)點(diǎn)的地址便是s+2n，3－11，這里的屬性值表示的3-11表的順序存儲在隨機(jī)存儲中，節(jié)點(diǎn)被隨機(jī)地存放在存儲介質(zhì)中，用一個(gè)順序存儲的索引數(shù)組指向各個(gè)節(jié)點(diǎn)的地址欄存有下一個(gè)節(jié)點(diǎn)的地址，直到最后一個(gè)節(jié)點(diǎn)為止。最后一個(gè)節(jié)點(diǎn)存入空地3地圖數(shù)據(jù)結(jié)構(gòu)3地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)3-12表的隨機(jī)存儲3－13表的鏈?zhǔn)酱鎯?4c)（a）（c）（b）3－14插入操作反過來說，在不改變表中任何節(jié)點(diǎn)的絕對位置時(shí)，順序存儲和隨機(jī)存儲要優(yōu)于鏈?zhǔn)酱婢€性表中還有兩個(gè)特例：循環(huán)表和雙重表，循環(huán)表包含一個(gè)閉合的路徑拓?fù)?。循環(huán)表按順序存儲時(shí)，第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)相同(圖3－15a)。按隨機(jī)存儲時(shí)，在順序索引中重復(fù)第一個(gè)地址指針作為最后一個(gè)地址指針。循環(huán)表可以容易地通過鏈?zhǔn)酱鎯?shí)現(xiàn)，僅僅只需將最后一個(gè)節(jié)點(diǎn)的空指針指向第一個(gè)節(jié)點(diǎn)(圖3－15c（a）（c）（b）3－14插入操作反過來說，在不改變表中任何節(jié)點(diǎn)的絕對位置時(shí)，順序存儲和隨機(jī)存儲要優(yōu)于鏈?zhǔn)酱婢€性表中還有兩個(gè)特例：循環(huán)表和雙重表，循環(huán)表包含一個(gè)閉合的路徑拓?fù)?。循環(huán)表按順序存儲時(shí)，第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)相同(圖3－15a)。按隨機(jī)存儲時(shí)，在順序索引中重復(fù)第一個(gè)地址指針作為最后一個(gè)地址指針。循環(huán)表可以容易地通過鏈?zhǔn)酱鎯?shí)現(xiàn)，僅僅只需將最后一個(gè)節(jié)點(diǎn)的空指針指向第一個(gè)節(jié)點(diǎn)(圖3－15c)。循環(huán)表中的第一個(gè)節(jié)點(diǎn)通?？梢匀我狻ｋp重表可以是線性的，也可以是循環(huán)的。在雙重表中的節(jié)點(diǎn)序列中，既可以前（a）（b）3－15使用循環(huán)表3－16b3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)（a）（b）3－163.2.2圖和在數(shù)據(jù)結(jié)構(gòu)中，節(jié)點(diǎn)可能包含不止一個(gè)前趨或后繼節(jié)點(diǎn)。圖是一系列節(jié)點(diǎn)組成的網(wǎng)絡(luò)拓?fù)?。例如，任何地理底圖都可以用圖來表達(dá)，底圖上的區(qū)域用節(jié)點(diǎn)來表示，而每對共享3－173－18有向圖在有向圖中，鄰接關(guān)系是非對稱的，箭頭用來表示關(guān)系的方向。如果節(jié)點(diǎn)A與節(jié)點(diǎn)B相中每個(gè)節(jié)點(diǎn)都只出現(xiàn)一次。在圖3－18中，節(jié)點(diǎn)A和D之間的一條路徑是（A，B，C，ED。D3-19樹的結(jié)構(gòu)全連通圖是指存在一個(gè)連接每對節(jié)點(diǎn)的路徑的圖，回路是指頭尾節(jié)點(diǎn)相同，中間節(jié)點(diǎn)不重復(fù)的路徑。不包含回路的全連通圖稱為樹，樹中的兩個(gè)節(jié)點(diǎn)只存在一條路徑。在有根樹中，存在一個(gè)根節(jié)點(diǎn)，包含樹中所有節(jié)點(diǎn)。樹中的節(jié)點(diǎn)通常按等級組織，其中一個(gè)節(jié)點(diǎn)位于最高級，所有其它的節(jié)點(diǎn)都在它之下(圖3－19a)。在這種組織中，樹中每個(gè)節(jié)點(diǎn)與它上一級的節(jié)點(diǎn)間只有一個(gè)連接通道。上一級節(jié)點(diǎn)通常稱為父節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)可以與多個(gè)下一級節(jié)點(diǎn)相連，下一級節(jié)點(diǎn)通常稱為子節(jié)點(diǎn)。任何一級節(jié)點(diǎn)中，具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)稱為兄弟。在樹的圖解中，位于最左邊的兄弟標(biāo)記為最老的兄弟，下一個(gè)靠左邊的兄弟稱為（a）3.3數(shù)字地圖的空間結(jié)針對所研究的地理現(xiàn)象，為了進(jìn)行空間操作和分析，必須定義空間實(shí)體及其相互之間的關(guān)系。數(shù)字地圖的拓?fù)浣Y(jié)構(gòu)就是用來描述空間實(shí)體的空間聯(lián)系。點(diǎn)、線、面三類實(shí)體的關(guān)系可以有六種組合，即點(diǎn)與點(diǎn)，如消防站與火災(zāi)地點(diǎn)的距離；點(diǎn)與線，如一條公路與兩旁城鎮(zhèn)，村莊之間的聯(lián)系；點(diǎn)與面，如排污的煙筒與周圍的環(huán)境；線與線，如表示公路、鐵路或河流組成的運(yùn)輸網(wǎng)絡(luò)；線與面，如一條輸油管道流經(jīng)哪些地區(qū)；面與面，如表示洪水影響區(qū)域與土地利用的疊合等。這些組合表現(xiàn)了實(shí)體間拓?fù)潢P(guān)系的相鄰性、連接性、閉A3-19樹的結(jié)構(gòu)全連通圖是指存在一個(gè)連接每對節(jié)點(diǎn)的路徑的圖，回路是指頭尾節(jié)點(diǎn)相同，中間節(jié)點(diǎn)不重復(fù)的路徑。不包含回路的全連通圖稱為樹，樹中的兩個(gè)節(jié)點(diǎn)只存在一條路徑。在有根樹中，存在一個(gè)根節(jié)點(diǎn)，包含樹中所有節(jié)點(diǎn)。樹中的節(jié)點(diǎn)通常按等級組織，其中一個(gè)節(jié)點(diǎn)位于最高級，所有其它的節(jié)點(diǎn)都在它之下(圖3－19a)。在這種組織中，樹中每個(gè)節(jié)點(diǎn)與它上一級的節(jié)點(diǎn)間只有一個(gè)連接通道。上一級節(jié)點(diǎn)通常稱為父節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)可以與多個(gè)下一級節(jié)點(diǎn)相連，下一級節(jié)點(diǎn)通常稱為子節(jié)點(diǎn)。任何一級節(jié)點(diǎn)中，具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)稱為兄弟。在樹的圖解中，位于最左邊的兄弟標(biāo)記為最老的兄弟，下一個(gè)靠左邊的兄弟稱為（a）3.3數(shù)字地圖的空間結(jié)針對所研究的地理現(xiàn)象，為了進(jìn)行空間操作和分析，必須定義空間實(shí)體及其相互之間的關(guān)系。數(shù)字地圖的拓?fù)浣Y(jié)構(gòu)就是用來描述空間實(shí)體的空間聯(lián)系。點(diǎn)、線、面三類實(shí)體的關(guān)系可以有六種組合，即點(diǎn)與點(diǎn)，如消防站與火災(zāi)地點(diǎn)的距離；點(diǎn)與線，如一條公路與兩旁城鎮(zhèn)，村莊之間的聯(lián)系；點(diǎn)與面，如排污的煙筒與周圍的環(huán)境；線與線，如表示公路、鐵路或河流組成的運(yùn)輸網(wǎng)絡(luò)；線與面，如一條輸油管道流經(jīng)哪些地區(qū)；面與面，如表示洪水影響區(qū)域與土地利用的疊合等。這些組合表現(xiàn)了實(shí)體間拓?fù)潢P(guān)系的相鄰性、連接性、閉AφBφBAECCAGDDAφφEBφFFBHφGCφφHFφIIFφφ3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)等是空間數(shù)據(jù)建模的基本任務(wù)。空間建模就是以一定的數(shù)據(jù)模型為基礎(chǔ)，具有其理論數(shù)學(xué)基礎(chǔ)，許多學(xué)者在圖形的數(shù)學(xué)表示方面進(jìn)行了很多深入的研究。圖形的空間結(jié)構(gòu)的描述，在某種程度上也是一個(gè)空間建模過程。采用數(shù)學(xué)的方法，描述其規(guī)律與行為，將有助3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)等是空間數(shù)據(jù)建模的基本任務(wù)?？臻g建模就是以一定的數(shù)據(jù)模型為基礎(chǔ)，具有其理論數(shù)學(xué)基礎(chǔ)，許多學(xué)者在圖形的數(shù)學(xué)表示方面進(jìn)行了很多深入的研究。圖形的空間結(jié)構(gòu)的描述，在某種程度上也是一個(gè)空間建模過程。采用數(shù)學(xué)的方法，描述其規(guī)律與行為，將有助合為G，則G＝{Mapi|MapiG，i＝1，2，……，n}，記為：MapiG理世界由點(diǎn)(point)集P（元素為頂點(diǎn)，記為pj），鏈（或弧段，line）集L（元素為鏈或弧段，記為lj）和多邊形（或面，area）集A（元素為多邊形，記為ai）構(gòu)成，則，Mapi={{P}，{L}，{A}|P，L，AMapi沒有任何點(diǎn)、弧段、面的圖為空圖（emptygraph，記作。如果的分類以及這些目標(biāo)的數(shù)字制圖表達(dá)及其鄰域關(guān)系。面域（開二維目標(biāo)）是一個(gè)基于網(wǎng)絡(luò)拓?fù)浔磉_(dá)的開點(diǎn)集。區(qū)域（閉二維目標(biāo)）是這些點(diǎn)閉集。區(qū)域中某個(gè)給定點(diǎn)的鄰域就是二維平面上的ε域。區(qū)域內(nèi)部的點(diǎn)是指它的鄰域完全包含在區(qū)域之內(nèi)（圖3－20。區(qū)域外部3－203－213－223－233－24人為指定的結(jié)點(diǎn)3－213－233－24人為指定的結(jié)點(diǎn)3－213－233－243－25線段鏈（弧段3－26多邊形3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)由于弧段上有無數(shù)多個(gè)點(diǎn)，但在數(shù)字環(huán)境下只能用有限個(gè)線段序列來表達(dá)，稱為鏈或3－25N（node3－25或多個(gè)內(nèi)環(huán)，并與其它多邊形鄰接(圖3－26)。設(shè)弧段、多邊形關(guān)系圖記作Map(L,A)，則Map(L,A)={Li|i=1，2，……，n}。如果兩個(gè)多邊形至少有一條公共邊，則稱這兩個(gè)多邊圖3－273－273－28點(diǎn)的構(gòu)成關(guān)系3－29結(jié)點(diǎn)的鄰接關(guān)系3－30線段的鄰接關(guān)系簡單點(diǎn)p等價(jià)于坐標(biāo)(xy)，并包含在弧段C中，也是前繼線段pL與后繼線段sL(圖3－個(gè)逆時(shí)針弧段RC和圍繞點(diǎn)pN的下一個(gè)逆時(shí)針弧段LC界定的邊界之內(nèi)。即所謂下一弧段表示了在終結(jié)點(diǎn)sN關(guān)聯(lián)的弧段中，該弧段逆時(shí)針方向的第一條弧段RC，而所謂上一弧段則表示了在始結(jié)點(diǎn)pN關(guān)聯(lián)的弧段中，該弧段逆時(shí)針方向的第一條弧段LC。如果沿著多邊形RP反時(shí)3－31)。這就是DCEL（Doubly-Connected-Edge-List）Preparata，19783－1簡單點(diǎn)p等價(jià)于坐標(biāo)(xy)，并包含在弧段C中，也是前繼線段pL與后繼線段sL(圖3－個(gè)逆時(shí)針弧段RC和圍繞點(diǎn)pN的下一個(gè)逆時(shí)針弧段LC界定的邊界之內(nèi)。即所謂下一弧段表示了在終結(jié)點(diǎn)sN關(guān)聯(lián)的弧段中，該弧段逆時(shí)針方向的第一條弧段RC，而所謂上一弧段則表示了在始結(jié)點(diǎn)pN關(guān)聯(lián)的弧段中，該弧段逆時(shí)針方向的第一條弧段LC。如果沿著多邊形RP反時(shí)3－31)。這就是DCEL（Doubly-Connected-Edge-List）Preparata，19783－13－32C3章地圖數(shù)據(jù)結(jié)構(gòu)3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)3.4拓?fù)鋽?shù)據(jù)模型及其結(jié)不同矢量數(shù)據(jù)模型間的主要區(qū)別在于有的是利用路徑拓?fù)洌≒athTopology）方法，有的則是網(wǎng)絡(luò)拓?fù)洌℅raphTopology）方法。在計(jì)算機(jī)輔助制圖中，前者通常認(rèn)為是非拓?fù)淠Ｐ突驇缀文Ｐ停笳邉t稱為拓?fù)淠Ｐ汀＿@兩種模型間的主要區(qū)別在于前者將二維要素的邊界作為獨(dú)立的一維要素來單獨(dú)處理，而不考慮要素之間的相互關(guān)系；而后者則著重于3.4.1路徑拓?fù)渥钤绲穆窂酵負(fù)淠Ｐ椭皇敲鏃l模型（SpaghettiModel。在這個(gè)模型中，面狀單元間的邊界作為坐標(biāo)記錄下來，沒有關(guān)于坐標(biāo)串與單個(gè)多邊形間關(guān)系的相應(yīng)信息。如表3－23－333－34裂隙問題為使多邊形操作變得容易，多邊形模型（PolygonModel）記錄和存儲了每個(gè)多邊形的3－3易標(biāo)識每個(gè)多邊形實(shí)體，但其存儲空間卻迅速擴(kuò)大。因?yàn)槎噙呅伍g的公共邊被存儲兩次。3－34。另外，所有描繪在實(shí)地圖上的多邊形，其鄰接關(guān)系是由地圖上每個(gè)多邊形的相對存儲位置隱含定義的。然而，在數(shù)字圖形中，只提供了實(shí)地圖的存儲功能，而沒有任何明顯的隱含暗示，因此很難重建多邊形間的鄰接關(guān)系。每一鄰接關(guān)系可以通過搜索多邊形的輪廓表，從中尋找兩個(gè)多邊形間相匹配的坐標(biāo)串來識別。一般來說，有效的編輯過程（第四章）和高效的顯示算法（見第六章）都會受到這些數(shù)據(jù)結(jié)構(gòu)的限制。除了缺少多邊形間(x9,y9),(x10,y10),(x11,y11),(x12,y12),(x42,y42),3－34裂隙問題為使多邊形操作變得容易，多邊形模型（PolygonModel）記錄和存儲了每個(gè)多邊形的3－3易標(biāo)識每個(gè)多邊形實(shí)體，但其存儲空間卻迅速擴(kuò)大。因?yàn)槎噙呅伍g的公共邊被存儲兩次。3－34。另外，所有描繪在實(shí)地圖上的多邊形，其鄰接關(guān)系是由地圖上每個(gè)多邊形的相對存儲位置隱含定義的。然而，在數(shù)字圖形中，只提供了實(shí)地圖的存儲功能，而沒有任何明顯的隱含暗示，因此很難重建多邊形間的鄰接關(guān)系。每一鄰接關(guān)系可以通過搜索多邊形的輪廓表，從中尋找兩個(gè)多邊形間相匹配的坐標(biāo)串來識別。一般來說，有效的編輯過程（第四章）和高效的顯示算法（見第六章）都會受到這些數(shù)據(jù)結(jié)構(gòu)的限制。除了缺少多邊形間(x9,y9),(x10,y10),(x11,y11),(x12,y12),(x42,y42),(x41,y41),(x39,y39),(x38,y38),(x37,y37),(x36,y36),(x35,y35),(x43,y43),(x7,y7),(x8,y8),(x9,y9),(x43,y43),(x35,y35),(x34,y34),(x46,y46),(x45,y45),(x44,y44),(x47,y47),(x48,y48),(x49,y49),(x7,y7)(x5,y5),(x6,y6),(x7,y7),(x49,y49),(x48,y48),(x47,y47),(x44,y44),(x5,y5),(x44,y44),(x45,y45),(x46,y46),(x34,y34),(x33,y33),(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5),(x6,y6),(x7,y7),(x8,y8),(x9,y9),(x10,y10),(x11,y11),(x12,y12)(x1,y1),(x13,y13),(x14,y14),(x15,y15),(x50,y50),(x16,y16),(x17,y17),(x18,y18),(x19,y19),(x20,y20),(x21,y21),(x22,y22)(x4,y4),(x23,y23),(x24,y24),(x25,y25),(x26,y26),(x23,y23),(x27,y27),(x28,y28),(x22,y22), (x30,y30), (x32,y32),(x33,y33),(x35,y35),(x36,y36),(x37,y37),(x38,y38),(x39,y39),(x40,y40),(x41,y41),(x42,y42),(x12,y12)(x9,y9),(x43,y43),(x5,y5),(x44,y44),(x45,y45),(x46,y46),(x44,y44),(x47,y47),(x48,y48),(x49,y49),3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)3－353－353章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)3－353－35(x31,y31),(x30,y30),(x29,y29),(x22,y22),(x21,y21),(x20,y20),(x18,y18),(x17,y17),(x16,y16),(x26,y26),(x25,y25),(x24,y24),(x23,y23),(x4,y4),(x5,y5)(x15,y15),(x28,y28),(x27,y27),(x23,y23),(x24,y24),(x25,y25),(x26,y26),(x16,y16),(x50,y50),(x15,y15)(x23,y23),(x27,y27),(x28,y28),(x15,y15),(x14,y14),(x13,y13),(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x23,y23)由此，任何多邊形的顯示都包含一個(gè)復(fù)雜的檢索過程。首先從多邊形表中得到點(diǎn)ID，再根據(jù)點(diǎn)ID獲得坐標(biāo)值。由于相同點(diǎn)的坐標(biāo)只在點(diǎn)位字典中存儲一次，因此這種方式大大3－363－5由此，任何多邊形的顯示都包含一個(gè)復(fù)雜的檢索過程。首先從多邊形表中得到點(diǎn)ID，再根據(jù)點(diǎn)ID獲得坐標(biāo)值。由于相同點(diǎn)的坐標(biāo)只在點(diǎn)位字典中存儲一次，因此這種方式大大3－363－53章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)ID值，然后根據(jù)弧段的ID值獲取點(diǎn)ID3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)ID值，然后根據(jù)弧段的ID值獲取點(diǎn)ID值，最后由點(diǎn)ID值得到相應(yīng)的坐標(biāo)。這樣可以很好解決裂隙問因?yàn)楣策吷纤谢《蔚南嗤c(diǎn)的ID值相同。題。更重要的是由于弧段的構(gòu)成細(xì)節(jié)被忽略，各多邊形被作為單個(gè)獨(dú)立的實(shí)體來考察，不3.4.2網(wǎng)絡(luò)拓?fù)湓缙诘氖噶磕Ｐ椭泻卸噙呅伍g鄰接關(guān)系的是DIME文件（DualIndependentMapEncoding。DIME文件是由美國人口統(tǒng)計(jì)局為存儲城市統(tǒng)計(jì)區(qū)的線狀面塊而設(shè)計(jì)出來的。DIME系統(tǒng)是ACG（AddressCodingGuide）系統(tǒng)的產(chǎn)物。在ACG系統(tǒng)中，能夠根據(jù)街道的地水涯線或鐵路線等的直線段。對于每個(gè)段，兩個(gè)端點(diǎn)ID分別為有方向性的“起始”和“終是按層次組織的，所以不止一個(gè)左或右多邊形的ID附加到段上。最低一級的面狀單元是街區(qū)，然后是街區(qū)群、人口統(tǒng)計(jì)區(qū)，直至到省。因此，如果段位于某個(gè)區(qū)域內(nèi)部，則其左右3－37DIME（Node3－38DIME在DIME中，由于線狀地理要素的路徑拓?fù)錄]有顯式定義，因此，獲取多邊形輪廓線是相當(dāng)復(fù)雜的。第一階段是要找出所有的DIME段及其左右多邊形，表3－7列出了所有屬于多邊形P3的段。在第二階段，這些段按以下順序排列：第一段的止點(diǎn)是后一段的起點(diǎn)。最后一個(gè)段的止點(diǎn)是第一個(gè)段的起點(diǎn)，這樣便形成了一個(gè)循環(huán)表，見表3－7。在這個(gè)過程中， P3DIME3－38DIME在DIME中，由于線狀地理要素的路徑拓?fù)錄]有顯式定義，因此，獲取多邊形輪廓線是相當(dāng)復(fù)雜的。第一階段是要找出所有的DIME段及其左右多邊形，表3－7列出了所有屬于多邊形P3的段。在第二階段，這些段按以下順序排列：第一段的止點(diǎn)是后一段的起點(diǎn)。最后一個(gè)段的止點(diǎn)是第一個(gè)段的起點(diǎn)，這樣便形成了一個(gè)循環(huán)表，見表3－7。在這個(gè)過程中， P3DIME3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)為了對其一些不足之處進(jìn)行改進(jìn)，美國計(jì)算機(jī)圖形與空間分析實(shí)驗(yàn)室基于弧段結(jié)構(gòu)構(gòu)造了POLYVRT系統(tǒng)（POLYgonconVeRTerDIME段給出，弧段的端點(diǎn)被稱3－8中，給出了弧段與結(jié)點(diǎn)間3－39給出了弧段與多邊形的關(guān)系。另外，每個(gè)弧段的點(diǎn)按序存放在一個(gè)單獨(dú)的文件中，一個(gè)指向這些點(diǎn)的開始處的指針存放在弧段文件。當(dāng)記錄下每個(gè)多邊形的循環(huán)表POLYVRTDIME模型，但它的POLYVRT模型與DIME模型的區(qū)別在于邊的不同選擇，3－8POLYVRT都是以線性要素(DIME段、弧段或鏈)作為存儲結(jié)點(diǎn)之間、弧段之間以及多邊形之間相互關(guān)系的基本單元，其缺點(diǎn)是缺乏對線性要素間鄰接關(guān)系的顯式描述。拓?fù)淠Ｐ椭辛硪活惙椒ㄊ怯媒Y(jié)點(diǎn)結(jié)構(gòu)來組織這些關(guān)系，根據(jù)任何一個(gè)結(jié)點(diǎn)都具有且僅有三個(gè)相鄰結(jié)點(diǎn)(如果存在四個(gè)以上的相鄰結(jié)點(diǎn)，則補(bǔ)入一個(gè)具有相同位置的虛結(jié)點(diǎn)，原結(jié)點(diǎn)與虛結(jié)點(diǎn)間的長度為0，以保證每個(gè)結(jié)點(diǎn)具有三個(gè)相鄰結(jié)點(diǎn)的特征)，每個(gè)結(jié)點(diǎn)都具有且僅有三條相關(guān)鏈和與這三條相關(guān)鏈相關(guān)的右多邊形(按右手法則確定)，在拓?fù)湮募杏汸PP3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)為了對其一些不足之處進(jìn)行改進(jìn)，美國計(jì)算機(jī)圖形與空間分析實(shí)驗(yàn)室基于弧段結(jié)構(gòu)構(gòu)造了POLYVRT系統(tǒng)（POLYgonconVeRTerDIME段給出，弧段的端點(diǎn)被稱3－8中，給出了弧段與結(jié)點(diǎn)間3－39給出了弧段與多邊形的關(guān)系。另外，每個(gè)弧段的點(diǎn)按序存放在一個(gè)單獨(dú)的文件中，一個(gè)指向這些點(diǎn)的開始處的指針存放在弧段文件。當(dāng)記錄下每個(gè)多邊形的循環(huán)表POLYVRTDIME模型，但它的POLYVRT模型與DIME模型的區(qū)別在于邊的不同選擇，3－8POLYVRT都是以線性要素(DIME段、弧段或鏈)作為存儲結(jié)點(diǎn)之間、弧段之間以及多邊形之間相互關(guān)系的基本單元，其缺點(diǎn)是缺乏對線性要素間鄰接關(guān)系的顯式描述。拓?fù)淠Ｐ椭辛硪活惙椒ㄊ怯媒Y(jié)點(diǎn)結(jié)構(gòu)來組織這些關(guān)系，根據(jù)任何一個(gè)結(jié)點(diǎn)都具有且僅有三個(gè)相鄰結(jié)點(diǎn)(如果存在四個(gè)以上的相鄰結(jié)點(diǎn)，則補(bǔ)入一個(gè)具有相同位置的虛結(jié)點(diǎn)，原結(jié)點(diǎn)與虛結(jié)點(diǎn)間的長度為0，以保證每個(gè)結(jié)點(diǎn)具有三個(gè)相鄰結(jié)點(diǎn)的特征)，每個(gè)結(jié)點(diǎn)都具有且僅有三條相關(guān)鏈和與這三條相關(guān)鏈相關(guān)的右多邊形(按右手法則確定)，在拓?fù)湮募杏汸PP3－39錄下各結(jié)點(diǎn)的三個(gè)相鄰結(jié)點(diǎn)、三條相關(guān)鏈和三個(gè)右多邊形，以此來實(shí)現(xiàn)數(shù)據(jù)處理時(shí)對多邊形的操作與檢索，這便是圖形拓?fù)淠Ｐ椭械腘ODE模型即結(jié)點(diǎn)模型。對于每個(gè)結(jié)點(diǎn)，其NODE模型是鏈?zhǔn)轿募Y(jié)構(gòu)稱結(jié)點(diǎn)的鄰域關(guān)系文件。每個(gè)多邊形邊界的檢索就是通過交起始結(jié)點(diǎn)的ID值，就可以通過掃描結(jié)點(diǎn)的ID記錄來查找多邊形P。多邊形P邊界的下一個(gè)結(jié)舉例來說，表3－9中，多邊形P3邊界的檢索是通過存取多邊形文件并找出其起始結(jié)點(diǎn)回到N103－9新英格蘭地區(qū)的NODE 3－39錄下各結(jié)點(diǎn)的三個(gè)相鄰結(jié)點(diǎn)、三條相關(guān)鏈和三個(gè)右多邊形，以此來實(shí)現(xiàn)數(shù)據(jù)處理時(shí)對多邊形的操作與檢索，這便是圖形拓?fù)淠Ｐ椭械腘ODE模型即結(jié)點(diǎn)模型。對于每個(gè)結(jié)點(diǎn)，其NODE模型是鏈?zhǔn)轿募Y(jié)構(gòu)稱結(jié)點(diǎn)的鄰域關(guān)系文件。每個(gè)多邊形邊界的檢索就是通過交起始結(jié)點(diǎn)的ID值，就可以通過掃描結(jié)點(diǎn)的ID記錄來查找多邊形P。多邊形P邊界的下一個(gè)結(jié)舉例來說，表3－9中，多邊形P3邊界的檢索是通過存取多邊形文件并找出其起始結(jié)點(diǎn)回到N103－9新英格蘭地區(qū)的NODE C11 3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)改進(jìn)。弧段之間的連接關(guān)系隱含在構(gòu)成多邊形輪廓線的弧段循環(huán)表中?；《蔚泥徲蚩杉右?－10擴(kuò)展弧段模型為了提取多邊形P3的邊界，假設(shè)以ID為C3的弧段作為起始搜索的弧段。在擴(kuò)展弧段表中掃描C3內(nèi)容看P3是否為其左或右多邊形；由于P3為C3的左多邊形，則弧段C6作為下一條應(yīng)該搜索的弧段。然后檢查C6，由于P3為其右多邊形，則C4為其下一弧段。最后檢查C4內(nèi)網(wǎng)絡(luò)拓?fù)淠Ｐ褪菍β窂酵負(fù)淠Ｐ偷母鞑蛔阒幍母倪M(jìn)與完善。在網(wǎng)絡(luò)拓?fù)淠Ｐ椭袕?qiáng)調(diào)了對多邊形間關(guān)系的描述，即在拓?fù)浣Y(jié)構(gòu)中，將一個(gè)多邊形圖形中的結(jié)點(diǎn)、邊和面分別顯式地描述，并記錄它們之間的關(guān)系，這樣不但可以反映出面與面間的相鄰關(guān)3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)改進(jìn)。弧段之間的連接關(guān)系隱含在構(gòu)成多邊形輪廓線的弧段循環(huán)表中?；《蔚泥徲蚩杉右?－10擴(kuò)展弧段模型為了提取多邊形P3的邊界，假設(shè)以ID為C3的弧段作為起始搜索的弧段。在擴(kuò)展弧段表中掃描C3內(nèi)容看P3是否為其左或右多邊形；由于P3為C3的左多邊形，則弧段C6作為下一條應(yīng)該搜索的弧段。然后檢查C6，由于P3為其右多邊形，則C4為其下一弧段。最后檢查C4內(nèi)網(wǎng)絡(luò)拓?fù)淠Ｐ褪菍β窂酵負(fù)淠Ｐ偷母鞑蛔阒幍母倪M(jìn)與完善。在網(wǎng)絡(luò)拓?fù)淠Ｐ椭袕?qiáng)調(diào)了對多邊形間關(guān)系的描述，即在拓?fù)浣Y(jié)構(gòu)中，將一個(gè)多邊形圖形中的結(jié)點(diǎn)、邊和面分別顯式地描述，并記錄它們之間的關(guān)系，這樣不但可以反映出面與面間的相鄰關(guān) 系，還反映了邊與邊之間、點(diǎn)與點(diǎn)之間的連接關(guān)系。關(guān)系，使得在空間數(shù)據(jù)處理和分析時(shí)，操作與檢索更為方便與迅捷。不同的模型具有不同的特點(diǎn)，因而具有不同的應(yīng)用。本節(jié)這里并沒有討論所有可能的地圖上基礎(chǔ)地理要素的數(shù)據(jù)組織方法。最合適的模型的選擇要取決于制圖處理系統(tǒng)對其功能上的需求。模型設(shè)計(jì)的指對一般應(yīng)用而言，但DIME在表示人口普查數(shù)據(jù)方面還是比POLYVRT更適合。PAN圖（Polygon-Ars-Nodes）有助于理解這種關(guān)系，它可以用來幫助開發(fā)滿足特殊用途的數(shù)據(jù)PAN系，還反映了邊與邊之間、點(diǎn)與點(diǎn)之間的連接關(guān)系。關(guān)系，使得在空間數(shù)據(jù)處理和分析時(shí)，操作與檢索更為方便與迅捷。不同的模型具有不同的特點(diǎn)，因而具有不同的應(yīng)用。本節(jié)這里并沒有討論所有可能的地圖上基礎(chǔ)地理要素的數(shù)據(jù)組織方法。最合適的模型的選擇要取決于制圖處理系統(tǒng)對其功能上的需求。模型設(shè)計(jì)的指對一般應(yīng)用而言，但DIME在表示人口普查數(shù)據(jù)方面還是比POLYVRT更適合。PAN圖（Polygon-Ars-Nodes）有助于理解這種關(guān)系，它可以用來幫助開發(fā)滿足特殊用途的數(shù)據(jù)PAN3－4，頂點(diǎn)表示多邊形目標(biāo)，頂點(diǎn)AN表示結(jié)點(diǎn)。圖中連接兩個(gè)頂點(diǎn)的箭頭表示一個(gè)類的目標(biāo)有指向另一個(gè)類的目標(biāo)的指針，或者同一個(gè)類中其他目標(biāo)的指針。例如，在結(jié)點(diǎn)結(jié)構(gòu)中，結(jié)點(diǎn)有指向其（3－40aP和N之間也有相連的箭頭。從圖中容易看出，多邊形邊3－40bPPANAN（a）3－40PAN3.4.3其它拓?fù)湓?個(gè)控制點(diǎn)的基礎(chǔ)上添加了一個(gè)虛構(gòu)控制點(diǎn)C8，代表背景區(qū)域，用虛線連接。TIN（TriangularIrregularNetwork－不規(guī)則三角網(wǎng)）的基本目標(biāo)是這些作為三角形頂點(diǎn)的形ID值；然后順序記錄構(gòu)成該三角形的控制點(diǎn)的ID值，這時(shí)以兩個(gè)控制點(diǎn)為端點(diǎn)的邊的ID3－9TIN3地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)3－41從同一控制點(diǎn)集可以有許多不同的三角剖分方法，其中一種特殊的剖分方法是Voronoi圖（VoronoiDiagram，又稱Thiessen多邊形，Thiessentesselaton）幾何中是一個(gè)被廣泛研究的問題，它是不規(guī)則點(diǎn)集的最基本的和最重要的幾何構(gòu)造。它是基于鄰近區(qū)域概念對空間的一種分割方式，一個(gè)Voronoi多邊形內(nèi)的任意一點(diǎn)到本Voronoi多邊形中心點(diǎn)的距離都小于其到其它Voronoi多邊形中心點(diǎn)的距離，見圖3－42；它也可以理解為對空間的一種內(nèi)插方式，空間中的任何一個(gè)已知點(diǎn)的值都可以由距離它最近的已知3－42邊S13S18C2C8T2T6S14S133地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)3－41從同一控制點(diǎn)集可以有許多不同的三角剖分方法，其中一種特殊的剖分方法是Voronoi圖（VoronoiDiagram，又稱Thiessen多邊形，Thiessentesselaton）幾何中是一個(gè)被廣泛研究的問題，它是不規(guī)則點(diǎn)集的最基本的和最重要的幾何構(gòu)造。它是基于鄰近區(qū)域概念對空間的一種分割方式，一個(gè)Voronoi多邊形內(nèi)的任意一點(diǎn)到本Voronoi多邊形中心點(diǎn)的距離都小于其到其它Voronoi多邊形中心點(diǎn)的距離，見圖3－42；它也可以理解為對空間的一種內(nèi)插方式，空間中的任何一個(gè)已知點(diǎn)的值都可以由距離它最近的已知3－42邊S13S18C2C8T2T6S14S13C1C8T3T1S15S14C3C8T4T2S16S15C7C8T5T3S17S16C5C8T6T4S18S17C5C8T1T5S7S6C2C5T1T8S6S12C4C5T7T6S8S1C1C2T2T7S9S2C3C1T3T9S10S3C7C3T4T10S11S4C6C7T5T11要尋找點(diǎn)集p，它們滿足等距并最接近三個(gè)中心點(diǎn)的條件，而這些點(diǎn)稱為Thiessen頂點(diǎn)或Voronoi頂點(diǎn)，每一Thiessen邊都是相鄰兩個(gè)中心點(diǎn)連線的垂直平分線。Voronoi圖的每個(gè)心，圖3－43。包含n個(gè)中心點(diǎn)的Voronoi圖有3(n-2)條Voronoi邊和2(n-2)個(gè)Voronoi如圖3－42中Voronoi圖有3(8－2)即18條邊和2(8－2)即12要尋找點(diǎn)集p，它們滿足等距并最接近三個(gè)中心點(diǎn)的條件，而這些點(diǎn)稱為Thiessen頂點(diǎn)或Voronoi頂點(diǎn)，每一Thiessen邊都是相鄰兩個(gè)中心點(diǎn)連線的垂直平分線。Voronoi圖的每個(gè)心，圖3－43。包含n個(gè)中心點(diǎn)的Voronoi圖有3(n-2)條Voronoi邊和2(n-2)個(gè)Voronoi如圖3－42中Voronoi圖有3(8－2)即18條邊和2(8－2)即12Voronoi圖與Delaunay三角網(wǎng)互為對偶，將Voronoi圖中各多邊形單元的內(nèi)點(diǎn)連接后得圓的圓心，圖3－43。由于Voronoi中心點(diǎn)、頂點(diǎn)和邊是三角網(wǎng)中的控制點(diǎn)、三角形和邊的對偶目標(biāo)，所以可以構(gòu)造與TIN模型（和結(jié)點(diǎn)模型）一致的Voronoi多邊形數(shù)據(jù)結(jié)構(gòu)。如果Voronoi頂點(diǎn)位于邊界上，則其下一元素指向該邊界上低編號的邊界頂點(diǎn)。圖3－42中，Voronoi頂點(diǎn)V1位于連接B1和B2的邊界上，則其指向B1，而V5則指向B3。見表3－10。該表是圖3－42中Voronoi圖完整的的數(shù)據(jù)結(jié)構(gòu)。每一Voronoi3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)將封閉多邊形內(nèi)部進(jìn)一步劃分為子多邊形，以使每個(gè)子多邊形內(nèi)的任意一點(diǎn)到該子多邊形所占有的原多邊形的一條邊的距離小于該點(diǎn)到原多邊形其它邊的距離，這樣的劃分稱3－44a3－45邊E13E18C2C8V2V6E14E13C1C8V3V13章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)將封閉多邊形內(nèi)部進(jìn)一步劃分為子多邊形，以使每個(gè)子多邊形內(nèi)的任意一點(diǎn)到該子多邊形所占有的原多邊形的一條邊的距離小于該點(diǎn)到原多邊形其它邊的距離，這樣的劃分稱3－44a3－45邊E13E18C2C8V2V6E14E13C1C8V3V1E15E14C3C8V4V2E16E15C7C8V5V3E17E16C5C8V6V3E18E17C5C8V1V5E7E6C2C5V1V80E6E12C4C5V7V60E8E1C1C2V2V70E9E2C3C1V3V90E10E3C7C3V4V100E11E4C6C7V5V1103－44b但如果是凸多邊形的話，那么Bimedial骨架圖和Bisector骨架圖就將相互一致，所劃分的子多邊形也一定是凸的。Bisector骨架圖是對Bimedial骨架圖區(qū)域分割方法的一種調(diào)整與3－113－46VoronoiARC/INFO的拓?fù)淇臻g表達(dá)ARC/INFOESRI在GIS領(lǐng)域已有幾十年的歷史。1997年，美國《SOFTWAREMAGAZINE》公布的全球前500名軟件廠商排名中，ESRl名列第44位，也是唯一入前50名的GIS廠商。據(jù)《GISWORLD》報(bào) 3－44b但如果是凸多邊形的話，那么Bimedial骨架圖和Bisector骨架圖就將相互一致，所劃分的子多邊形也一定是凸的。Bisector骨架圖是對Bimedial骨架圖區(qū)域分割方法的一種調(diào)整與3－113－46VoronoiARC/INFO的拓?fù)淇臻g表達(dá)ARC/INFOESRI在GIS領(lǐng)域已有幾十年的歷史。1997年，美國《SOFTWAREMAGAZINE》公布的全球前500名軟件廠商排名中，ESRl名列第44位，也是唯一入前50名的GIS廠商。據(jù)《GISWORLD》報(bào) E14 E15 E10 E10 E11 E13 3章地圖數(shù)據(jù)3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)1998息，而不僅是一個(gè)點(diǎn)?；《我越Y(jié)點(diǎn)為起止點(diǎn)，中間點(diǎn)以一串(X，Y)坐標(biāo)對表示，確定了一（二）ARC/INFO拓?fù)淇臻g關(guān)系表示模1．3－472．如圖3-48，ARC/INFO使用多邊形－弧段拓?fù)浣Y(jié)構(gòu)來定義多邊形。PAL文件中由組成多邊形的弧段來定義多邊形。圖3-48中，弧的列表按順時(shí)針方向由每個(gè)弧段的內(nèi)部順序號順序組成，在多邊形弧段表中，一條弧的順序號為負(fù)，則說明該弧在完成多邊形循環(huán)時(shí)，是按從終止結(jié)點(diǎn)到起始結(jié)點(diǎn)的方向通過的。島則通過在該島多邊形列表前加0來標(biāo)記。第一個(gè)多邊形總是定義為Coverage3－483－483－49B與，多邊形C與F3－494在ARC/INFO中，地圖數(shù)據(jù)作為X，Y坐標(biāo)對序列來存儲，分別代表點(diǎn)、線和多邊形。這些特征之間的關(guān)系通過拓?fù)浣Y(jié)構(gòu)來表達(dá)。相關(guān)的表格數(shù)據(jù)存儲在關(guān)系表格中，通過內(nèi)部標(biāo)地理特征（以及描述這些特征的屬性）按照某種相關(guān)性在邏輯上組成一些相對獨(dú)立的信息層或信息的主題，即Coverage。例如，一幅地形圖常常需要分成多個(gè)層次來存儲，如3章地圖數(shù)據(jù)結(jié)3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)除了對單獨(dú)的Coverage進(jìn)行操作外，ARC/INFO還采用了先進(jìn)的空間索引方式，可管理大數(shù)據(jù)量的圖形數(shù)據(jù)。在地圖庫里(MapLibrary)，把地圖數(shù)據(jù)水平方向劃分為Tile，縱向鎖定，以防止數(shù)據(jù)產(chǎn)生不一致性，直到用戶提交修改內(nèi)容。另外，ARC/INFO有一個(gè)專門管理地圖庫的擴(kuò)展模塊ArcStorm。它是真正基于Client／Server結(jié)構(gòu)的，可以大大減輕網(wǎng)絡(luò)型具有不同的特點(diǎn)，在前述多個(gè)模型中，DCEL模型對邊拓?fù)潢P(guān)系的表示較完善，但對面、鏈的表示缺乏完整性，對空間分析功能要求較低的計(jì)算機(jī)輔助設(shè)計(jì)（CAD）等比較適用。ARC/INFO的拓?fù)潢P(guān)系表示模型，較好地表示了點(diǎn)、線、面相互之間的拓?fù)潢P(guān)系，特別適合型具有不同的特點(diǎn)，在前述多個(gè)模型中，DCEL模型對邊拓?fù)潢P(guān)系的表示較完善，但對面、鏈的表示缺乏完整性，對空間分析功能要求較低的計(jì)算機(jī)輔助設(shè)計(jì)（CAD）等比較適用。ARC/INFO的拓?fù)潢P(guān)系表示模型，較好地表示了點(diǎn)、線、面相互之間的拓?fù)潢P(guān)系，特別適合GeoStar（武漢大學(xué)、MapGIS（中國地質(zhì)大學(xué)、AutoDeskMap／World／MapGuide（美國ARC/INFO利用拓?fù)浣Y(jié)構(gòu)在兩個(gè)簡單的坐標(biāo)要素——弧和結(jié)點(diǎn)的基礎(chǔ)上表達(dá)了附加的地理信息。拓?fù)浣Y(jié)構(gòu)通常利用內(nèi)部順序號來表示。如采用一組弧的列表定義多邊形，利用弧ARC/INFO用BUILD和CLEAN命令自動(dòng)生成和修改要素的拓?fù)浣Y(jié)構(gòu)。拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)模型可以更有效地存儲數(shù)據(jù)，它提供了進(jìn)行高級地理分析的框架。例如，拓?fù)浣Y(jié)構(gòu)模型由組成多邊形邊界的弧的列表來構(gòu)建多邊形。當(dāng)兩個(gè)多邊形共享一條公共邊時(shí)，系統(tǒng)只存儲公共弧坐標(biāo)值一次。與此相對，一個(gè)非拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)模型把每個(gè)封閉的多邊形作為一個(gè)獨(dú)立的實(shí)體存儲，鄰接多邊形公用的一條弧必須輸入并存儲兩次，這通常通過數(shù)字化兩次或弧的拷目前在建立幾何對象的拓?fù)潢P(guān)系方面形成了兩個(gè)陣營或兩種方法：一是以ARC/INFO、MGE、GENAMAP、SDTS（SpatialDataTransferStandard）等GIS系統(tǒng)和標(biāo)準(zhǔn)為代表的采用在數(shù)據(jù)結(jié)構(gòu)中存儲拓?fù)湫畔?；二是以Mapinfo、Arcview、SDE、SDO等GIS系統(tǒng)以及OpenGIS簡單要素互操作規(guī)范為代表的在數(shù)據(jù)結(jié)構(gòu)中不存儲拓?fù)湫畔?，其空間關(guān)系通過數(shù)學(xué)方法計(jì)拓?fù)鋽?shù)據(jù)模型可以高效地存儲數(shù)據(jù)，它提供了高級地理分析的框架。拓?fù)鋽?shù)據(jù)模型用圍繞多邊形的弧段來建立多邊形。對于公共弧段，系統(tǒng)只存儲一次弧段坐標(biāo)，兩個(gè)相鄰的數(shù)據(jù)庫的那種封閉式的多邊形環(huán)。這種弧段—結(jié)點(diǎn)的結(jié)構(gòu)幾乎把制圖數(shù)據(jù)的存儲量壓縮了易在生成拓?fù)浣Y(jié)構(gòu)的過程中查找出數(shù)據(jù)輸入的錯(cuò)誤。而且拓?fù)浣Y(jié)構(gòu)可以方便處理多邊形中等，國內(nèi)的MapGIS、GeoStar3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)雖然拓?fù)鋽?shù)據(jù)結(jié)構(gòu)效率很高，但計(jì)算機(jī)處理速度的加快和存儲設(shè)備容量的擴(kuò)大已逐漸降低了明確定義拓?fù)湫畔⒌谋匾?。由于拓?fù)鋽?shù)據(jù)結(jié)構(gòu)復(fù)雜，幾何對象之間相互關(guān)聯(lián)，數(shù)據(jù)經(jīng)過增加、刪除、修改等編輯操作后，拓?fù)潢P(guān)系被破壞，必須通過拓?fù)渌惴ㄖ匦聵?gòu)造拓?fù)潢P(guān)系來維護(hù)其一致性和完整性。另外圖形顯示速度慢，圖形的表達(dá)也不自然，因?yàn)橐粋€(gè)CAD（AutoCAD3章地圖數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)雖然拓?fù)鋽?shù)據(jù)結(jié)構(gòu)效率很高，但計(jì)算機(jī)處理速度的加快和存儲設(shè)備容量的擴(kuò)大已逐漸降低了明確定義拓?fù)湫畔⒌谋匾浴Ｓ捎谕負(fù)鋽?shù)據(jù)結(jié)構(gòu)復(fù)雜，幾何對象之間相互關(guān)聯(lián)，數(shù)據(jù)經(jīng)過增加、刪除、修改等編輯操作后，拓?fù)潢P(guān)系被破壞，必須通過拓?fù)渌惴ㄖ匦聵?gòu)造拓?fù)潢P(guān)系來維護(hù)其一致性和完整性。另外圖形顯示速度慢，圖形的表達(dá)也不自然，因?yàn)橐粋€(gè)CAD（AutoCAD圖和圖形系統(tǒng)（如Mapinfo、Arcview等）GISESRIARCVIEW的Shapefile是一種新的非拓?fù)鋽?shù)據(jù)結(jié)構(gòu)，它在數(shù)據(jù)集中存儲地理實(shí)體的性相連。Shapefile中有14種shape類型（ESRIShapefileTechnicalDescription，ERSI，1997表3－12shapefile中的shape值形狀類0Null13583.5剖分?jǐn)?shù)據(jù)結(jié)3-52。其二是其二維空間能否被遞歸分割而保持原有形態(tài)，方格和三角形均可以，而六邊形則不行。然而，六邊形具有輻射對稱特性，圖3-53，六邊形還是適于空間抽樣的最緊湊的形態(tài)。方格網(wǎng)最適于數(shù)組3.5剖分?jǐn)?shù)據(jù)結(jié)3-52。其二是其二維空間能否被遞歸分割而保持原有形態(tài)，方格和三角形均可以，而六邊形則不行。然而，六邊形具有輻射對稱特性，圖3-53，六邊形還是適于空間抽樣的最緊湊的形態(tài)。方格網(wǎng)最適于數(shù)組3地圖數(shù)據(jù)結(jié)構(gòu)3地圖數(shù)據(jù)結(jié)構(gòu)與