數字地圖制圖原理

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