計算機地圖制圖的理論基礎

1、第二章第二章 計算機地圖制圖計算機地圖制圖 的理論基礎的理論基礎目錄：目錄：2.1 初等幾何學及其算法 2.2 圖論 2.3 計算幾何 2.4 圖像處理的基本方法2.5 數(shù)字地面模型 2.1 初等幾何學及其算法計算機地圖制圖幾何元素間的關系：計算機地圖制圖幾何元素間的關系：點點線線面面點點線線面面是在地理坐標空間而不是在屏幕坐標空間中計算是在地理坐標空間而不是在屏幕坐標空間中計算!1. 1. 點線關系點線關系 點在線上點在線上點線相離點線相離研究重點：研究重點：點與線段的側(cè)位關系判斷、點與線點與線段的側(cè)位關系判斷、點與線拓撲關系的判別方法及點到線的距離計算。拓撲關系的判別方法及點到線的距離計算

2、。 1.1 點線側(cè)位關系判斷點線側(cè)位關系判斷 設有一條直線，其方程為：設有一條直線，其方程為： ，則對于函，則對于函數(shù)數(shù) ，任取空間一點，任取空間一點 ，有：，有：0CByAxCByAxyxf),(),(00yxm判斷點線側(cè)位關系的意義？判斷點線側(cè)位關系的意義？1.2 1.2 點、線關系的判別方法點、線關系的判別方法 點線關系判別的目的之一是確定點是否在線上。點線關系判別的目的之一是確定點是否在線上。 圖圖2-1 2-1 點線關系的判斷（虛線為投影矩形）點線關系的判斷（虛線為投影矩形）Ap1P2P3P4P5P6B1.3 1.3 點到線的距離計算點到線的距離計算 Ap1p2（a）Ap1p2（b）

3、圖圖2-2 點與線段距離的兩種情形點與線段距離的兩種情形點到線段的距離可能是該點與線段點到線段的距離可能是該點與線段某一端點某一端點的距離，的距離，也可能是點到線段的也可能是點到線段的垂距垂距。p1P2P3P4P5DA最遠距離最近距離圖圖2-3 2-3 點與線的最遠距離和最近距離點與線的最遠距離和最近距離點到線的距離有最遠距離和最近距離。點到線的距離有最遠距離和最近距離。2. 2. 線線關系線線關系 相離相離共位共位相交相交線線關系判斷的基礎是：線線關系判斷的基礎是：兩線段是否相交兩線段是否相交,可由可由1.1簡單推算之簡單推算之.圖圖2-4 2-4 折線的單調(diào)鏈劃分及其投影矩形折線的單調(diào)鏈劃

4、分及其投影矩形l1l2l3l4l5l6k1k2k3LK兩折線相交與否的判斷兩折線相交與否的判斷第一步：第一步：生成單調(diào)鏈生成單調(diào)鏈(此圖中此圖中為關于縱坐標的單調(diào)鏈為關于縱坐標的單調(diào)鏈)第二步：第二步：計算每個單調(diào)鏈的計算每個單調(diào)鏈的最小投影矩形最小投影矩形第三步：第三步：兩兩判斷最小投影兩兩判斷最小投影矩形是否相交矩形是否相交,如相交如相交,才判才判斷其對應單調(diào)鏈是否相交斷其對應單調(diào)鏈是否相交.兩兩判斷線段是否相交即可兩兩判斷線段是否相交即可,但不是最優(yōu)算法但不是最優(yōu)算法.折線自相交的判斷與此基本一樣折線自相交的判斷與此基本一樣.3.3.點面關系點面關系 圖圖2-5 2-5 點與三角形的位置

5、關系點與三角形的位置關系1111),(cybxayxf2222),(cybxayxf3333),(cybxayxf0),(),(0),(),(0),(),(332211PPBBPPAAPPCCyxfyxfyxfyxfyxfyxf若滿足：若滿足：則點則點P位于三角形的內(nèi)部，否則點位于三角形的內(nèi)部，否則點P位位于三角形的外部。于三角形的外部。ABABBCBCCACA3.13.1點與三角形位置關系的計算點與三角形位置關系的計算 void CTView:OnLButtonUp(UINT nFlags, CPoint point) / TODO: Add your message handler cod

6、e here and/or call default/CView:OnLButtonUp(nFlags, point);if(m_DrawCurrent=2)float F1=f1(PointXyz2.x,PointXyz2.y);float F2=f2(PointXyz0.x,PointXyz0.y);float F3=f3(PointXyz1.x,PointXyz1.y);float F4=f1(float(mPointOrign.x),float(mPointOrign.y);float F5=f2(float(mPointOrign.x),float(mPointOrign.y);fl

7、oat F6=f3(float(mPointOrign.x),float(mPointOrign.y);if(F1*F40 & F2*F50 & F3*F60)MessageBox( 點在三角形內(nèi)！點在三角形內(nèi)！ );else MessageBox( 點在三角形外！點在三角形外！ ); ReleaseCapture();3.2 3.2 點與多邊形位置關系的計算點與多邊形位置關系的計算 判斷點與多邊形位置關系的夾角求和算法判斷點與多邊形位置關系的夾角求和算法(只適用于簡單多邊形只適用于簡單多邊形,對于帶孔多邊形的算法改進比較麻煩對于帶孔多邊形的算法改進比較麻煩)設有一簡單設有一簡

8、單n邊形，其頂點可以表示為邊形，其頂點可以表示為Pi( (xi,yi) )，i=1,2,=1,2,n，另有待判別的獨立點，另有待判別的獨立點A A。連接點。連接點A A與多邊與多邊形的各個頂點，計算其夾角和，且規(guī)定順時針方向形的各個頂點，計算其夾角和，且規(guī)定順時針方向旋轉(zhuǎn)的角度為旋轉(zhuǎn)的角度為正正，逆時針方向旋轉(zhuǎn)的角度為，逆時針方向旋轉(zhuǎn)的角度為負負。若。若有有在多邊形外點在多邊形內(nèi)點A0A21111PPPPPPnniii圖 2-8 P1P2P4P5P6PP2圖 2-9P3P4P5PP3P6P1PXYO方位角求夾角的方法：在笛卡兒坐標系中，從在笛卡兒坐標系中，從x x軸正軸正向起逆時針旋轉(zhuǎn)某一射線

9、得到向起逆時針旋轉(zhuǎn)某一射線得到一個角度，可定義為該方向的一個角度，可定義為該方向的方位角。射線方位角。射線OPOP的方位角。方的方位角。方位角的取值范圍是：位角的取值范圍是： 3600判斷點與多邊形位置關系的判斷點與多邊形位置關系的鉛垂線內(nèi)點算法鉛垂線內(nèi)點算法(適用于帶孔多邊形適用于帶孔多邊形)基本思想基本思想: :從待判別點引鉛垂線，由該鉛垂線從待判別點引鉛垂線，由該鉛垂線（注意：是一條射線）（注意：是一條射線）與多邊形交點個數(shù)的與多邊形交點個數(shù)的奇奇偶性偶性來判斷點是否在多邊形內(nèi)。來判斷點是否在多邊形內(nèi)。 若交點個數(shù)為奇數(shù)，點在多邊形內(nèi)；若交點個數(shù)為奇數(shù)，點在多邊形內(nèi)； 若交點個數(shù)為偶數(shù)，

10、則該點在多邊形外。若交點個數(shù)為偶數(shù)，則該點在多邊形外。 A1A2P1P2P3P4P5圖圖2-11 2-11 由交點數(shù)奇偶性判斷點面包含關系由交點數(shù)奇偶性判斷點面包含關系鉛垂線內(nèi)點算法鉛垂線內(nèi)點算法 : :第一步第一步，計算多邊形最小投影矩形，若點在最小投影矩形，計算多邊形最小投影矩形，若點在最小投影矩形外，則點一定在多邊形外，算法結(jié)束；否則執(zhí)行第二步。外，則點一定在多邊形外，算法結(jié)束；否則執(zhí)行第二步。第二步第二步，設置記錄交點個數(shù)的計數(shù)器，設置記錄交點個數(shù)的計數(shù)器NumNum=0=0。第三步第三步，從待判斷的點作鉛垂線，順次判斷該鉛垂線與多，從待判斷的點作鉛垂線，順次判斷該鉛垂線與多邊形各邊是

11、否相交，若相交，求出交點并記錄下來。每有邊形各邊是否相交，若相交，求出交點并記錄下來。每有一次相交，把一次相交，把NumNum數(shù)值增加數(shù)值增加1 1。第四步第四步，若，若NumNum為偶數(shù)，則該點在多邊形外；否則，該點為偶數(shù)，則該點在多邊形外；否則，該點在多邊形內(nèi)。算法結(jié)束。在多邊形內(nèi)。算法結(jié)束。（a）圖圖2-12 鉛垂線交于多邊形的頂點鉛垂線交于多邊形的頂點（b）AAP1P2P3P4P1P2P3P4（a）（b）圖圖2-13 2-13 鉛垂線與多邊形的一邊相重合鉛垂線與多邊形的一邊相重合P1P2P3P4P5P6AP1P2AP3P4P5特殊情況的考慮：特殊情況的考慮：1. 1. 交點位于多邊形頂

12、點交點位于多邊形頂點 建立鉛垂線的直線方程，判斷該頂點前、后相鄰建立鉛垂線的直線方程，判斷該頂點前、后相鄰的兩頂點是否在鉛垂線的同側(cè)，的兩頂點是否在鉛垂線的同側(cè)，若在同側(cè)，若在同側(cè)，NumNum不不變，否則變，否則NumNum加加1 1。 2. 2. 鉛垂線與多邊形的一條邊重合鉛垂線與多邊形的一條邊重合 建立鉛垂線的直線方程，判斷與該邊兩端點相鄰的建立鉛垂線的直線方程，判斷與該邊兩端點相鄰的前、后兩頂點是否在鉛垂線的同側(cè)，前、后兩頂點是否在鉛垂線的同側(cè)，若在同側(cè)，若在同側(cè)，NumNum不變，否則不變，否則NumNum加加1 1。 部分源代碼：部分源代碼：void CDraw1View:judg

13、e2(float x, float y) float xmax=PointXyz0.x; float xmin=PointXyz0.x; float ymin=PointXyz0.y; float fy; /fy為待判斷點與直線方程的交點的縱坐標為待判斷點與直線方程的交點的縱坐標 int num=0; /記錄待判斷點與直線方程的交點的數(shù)目記錄待判斷點與直線方程的交點的數(shù)目 PointXyza.x=PointXyz0.x; PointXyza.y=PointXyz0.y; PointXyza+1.x=PointXyz1.x;PointXyza+1.y=PointXyz1.y; PointXyza

14、+2.x=PointXyz2.x; PointXyza+2.y=PointXyz2.y; PointXyza+3.x=PointXyz3.x; PointXyza+3.y=PointXyz3.y;for(int j=0;j=y&(PointXyzj.xx&xPointXyzj+1.x)|(PointXyzj+1.xx&xPointXyzj.x) / 縱坐標越往下，值越大縱坐標越往下，值越大 num=num+1; continue; else if(x=PointXyzj+1.x&fy=PointXyzj+1.y) / 交于多邊形頂點時交于多邊形頂點時 if(Po

15、intXyzj.xx&xPointXyzj+2.x)|(PointXyzj+2.xx&xy) /若前后相鄰的兩頂點在該頂點所做鉛垂線分得異側(cè)，則若前后相鄰的兩頂點在該頂點所做鉛垂線分得異側(cè)，則num+ num=num+1; else if(x=PointXyzj+1.x&x=PointXyzj+2.x&PointXyzj+2.yy) /若鉛垂線與邊部分重合若鉛垂線與邊部分重合 if(PointXyzj+3.xx&xPointXyzj.x)|(PointXyzj.xx&xPointXyzj+3.x) num=num+1; if(num%2=1) M

16、essageBox(點在多邊形內(nèi)！點在多邊形內(nèi)！); elseif(num%2=0) MessageBox(點在多邊形外！點在多邊形外！);4. 4. 線面關系線面關系 線面關系研究的重點問題是線面關系研究的重點問題是求線與面的相交求線與面的相交。 線段與多邊形交線的算法線段與多邊形交線的算法 ：第一步第一步，求多邊形的最小投影矩形。，求多邊形的最小投影矩形。第二步第二步，判斷線段是否有端點在該最小投影矩形，判斷線段是否有端點在該最小投影矩形中。若不在，結(jié)論為中。若不在，結(jié)論為“線段與多邊形相離線段與多邊形相離”，算，算法結(jié)束；否則，執(zhí)行第三步。法結(jié)束；否則，執(zhí)行第三步。第三步第三步，順次判斷

17、線段與多邊形各邊是否有交點，順次判斷線段與多邊形各邊是否有交點，若有交點，則求出并保存交點坐標。若有交點，則求出并保存交點坐標。第四步第四步，對交點坐標排序：計算各交點與線段，對交點坐標排序：計算各交點與線段一一端點端點的距離，然后按照距離由小到大對交點編號的距離，然后按照距離由小到大對交點編號排序。排序。第五步，按規(guī)律第五步，按規(guī)律連接各個交點，得到位于多邊形內(nèi)部的連接各個交點，得到位于多邊形內(nèi)部的交線。交線。p1p6p3p4p5圖圖2-14 線段與多邊形相交時的交點連接規(guī)律線段與多邊形相交時的交點連接規(guī)律p2p7p8p9p10p11p12p13p14Qq1q2q4q3q5q6q8q7q9q

18、10Kk2k3k1HM5. 5. 面面關系面面關系 任意兩多邊形求交問題解決的基礎是兩個簡任意兩多邊形求交問題解決的基礎是兩個簡單多邊形單多邊形求交求交、求差求差和和求并求并的算法。的算法。 5.1 5.1 計算簡單多邊形交集的算法計算簡單多邊形交集的算法 設有兩個簡單多邊形：設有兩個簡單多邊形：P=P1,P2,Pm，Q=q1,q2,qn，各多邊形頂點各多邊形頂點Pi、qj逆時針排列，逆時針排列，確定它們的確定它們的交交：F = PQ =k|kPkQ。例：例：p1p2p3p4p5p6q1q2q3q4q5q6q7k1k8k2k4k5k6圖圖2-15 2-15 簡單多邊形求交簡單多邊形求交k3k7

19、5.2 5.2 計算任意多邊形交集的算法計算任意多邊形交集的算法 例：例：平面上給定兩個多邊形平面上給定兩個多邊形P、Q（它們可以是簡（它們可以是簡單多邊形，也可以是復雜多邊形），單多邊形，也可以是復雜多邊形），P的外圍的外圍多邊形為多邊形為P0,內(nèi)嵌內(nèi)嵌m（m0 0）個島嶼多邊形為）個島嶼多邊形為P1、P2、Pm，Q的外圍多邊形為的外圍多邊形為Q0，內(nèi)嵌，內(nèi)嵌n（n0）個島嶼多邊形為個島嶼多邊形為Q1、Q2、Qn，各多邊形頂，各多邊形頂點逆時針排列，確定它們的交點逆時針排列，確定它們的交F = PQ =q|qPqQ 圖圖2-17 2-17 兩復雜多邊形求交兩復雜多邊形求交PQQ0Q1P1P0

20、P22.2 2.2 圖論圖論（后面介紹）（后面介紹）1 1、圖論的起源與發(fā)展、圖論的起源與發(fā)展 圖論創(chuàng)立的標志：哥尼斯堡七橋問題的提出圖論創(chuàng)立的標志：哥尼斯堡七橋問題的提出 圖圖2-18 2-18 哥尼斯堡七橋問題圖示哥尼斯堡七橋問題圖示ABCD問題：問題：“你能經(jīng)你能經(jīng)過每橋當且盡當過每橋當且盡當一次再返回出發(fā)一次再返回出發(fā)點嗎？點嗎？” ” 哈密爾頓回路問題、貨郎哈密爾頓回路問題、貨郎擔問題、地圖印刷的四色擔問題、地圖印刷的四色問題、拉姆塞問題問題、拉姆塞問題 2.2.圖的概念圖的概念 有向圖示例有向圖示例記為記為D Dv1v2v3e3e1e2有向邊有向邊端點端點起點起點終點終點v1v2v

21、3e3e1e2無向圖示例無向圖示例記為記為G G頂點頂點邊邊v3v1v2v4v5v6e1e2e3e4e5e7e8e6非簡單有向圖示例非簡單有向圖示例環(huán)環(huán)平行邊平行邊對稱邊對稱邊孤立頂點孤立頂點3. 3. 圖的矩陣表示圖的矩陣表示 鄰接矩陣鄰接矩陣(A)(A)是圖的一種有效表示方法，圖在計算機是圖的一種有效表示方法，圖在計算機中經(jīng)常用其對應鄰接矩陣來保存。所謂圖的鄰接矩中經(jīng)常用其對應鄰接矩陣來保存。所謂圖的鄰接矩陣，是指一個陣，是指一個v v v v階矩陣。階矩陣。 其中元素為其中元素為u(eu(ei i,e,ej j),),對對G G為為e ei i和和e ej j之間的邊數(shù)；對之間的邊數(shù)；對

22、D D為從為從e ei i和和e ej j之間的邊數(shù)。之間的邊數(shù)。所謂圖的所謂圖的關聯(lián)矩陣關聯(lián)矩陣(M)(M) ，是指一個，是指一個v v e e階矩陣。其中階矩陣。其中元素，對元素，對G G取取1 1，0 0；對；對D D取取1 1，-1-1，0 0。圖的圖的矩陣表示矩陣表示在矩陣論與圖論之間架起了一座橋梁。在矩陣論與圖論之間架起了一座橋梁。v1v2v3v4e1e2e3e4e5e6e7v11101v11110000v21021v21001011v30201v30000111v41110v40101100鄰接矩陣A(G)關聯(lián)矩陣M(G)v1v2v3v4e1e2e3e4e5e6e7無向圖矩陣無向

23、圖矩陣v1v2v3v4e1e2e3e4e5e6e7v11101v11110000v20021v2-1001011v30000v30000-1-1-1v40010v40-10-1100鄰接矩陣A(D)關聯(lián)矩陣M(D)v1v2v3v4e1e2e3e4e5e6e7有向圖矩陣有向圖矩陣（a）794532243（b）-7945-32-243圖圖2-23 2-23 加權(quán)圖加權(quán)圖. . （a a）加權(quán)無向圖；）加權(quán)無向圖； （b b）加權(quán)有向圖）加權(quán)有向圖2.3 2.3 計算幾何計算幾何 計算幾何（計算幾何（Computational GeometryComputational Geometry）是由）是由

24、函數(shù)逼近論、微分幾何、代數(shù)幾何、計算數(shù)學等形函數(shù)逼近論、微分幾何、代數(shù)幾何、計算數(shù)學等形成的一門邊緣學科，研究幾何信息的計算機表示、成的一門邊緣學科，研究幾何信息的計算機表示、分析和綜合等。分析和綜合等。計算幾何在計算機輔助設計（計算幾何在計算機輔助設計（CADCAD：Computer-Aided DesignComputer-Aided Design）、計算機輔助制造（）、計算機輔助制造（CAMCAM：Computer-Aided ManufactureComputer-Aided Manufacture）、計算機輔助地圖）、計算機輔助地圖制圖（制圖（CACCAC：Computer-Aide

25、d CartographyComputer-Aided Cartography）、圖）、圖形學、機器人技術、超大規(guī)模集成電路設計等諸多形學、機器人技術、超大規(guī)模集成電路設計等諸多領域有著十分重要的應用。領域有著十分重要的應用。 1. 1. 曲線擬合曲線擬合 定義：定義： 找出一條通過一組給定點的曲線是一個找出一條通過一組給定點的曲線是一個插插值問題值問題； 找出一條近似地通過一組給定點的曲線則找出一條近似地通過一組給定點的曲線則是是逼近問題逼近問題。兩者統(tǒng)稱曲線擬合。兩者統(tǒng)稱曲線擬合。 分段多項式插值法分段多項式插值法和和樣條曲線插值法樣條曲線插值法 2. 2. 凸殼凸殼 平面點集平面點集S

26、S的凸殼（的凸殼（Convex HullConvex Hull）或凸）或凸包或曰凸多邊形是指包含包或曰凸多邊形是指包含S S的最小凸集，通的最小凸集，通常用常用CHCH（S S）來表示。）來表示。 從幾何的直觀上判斷，從幾何的直觀上判斷，S S的凸殼表現(xiàn)為的凸殼表現(xiàn)為S S中任意兩點所連的線段全部位于中任意兩點所連的線段全部位于S S中。平面中。平面點集點集S S的凸殼邊界的凸殼邊界BCH(S)BCH(S)是一個凸多邊形，是一個凸多邊形，多邊形的頂點必定為多邊形的頂點必定為S S中的點。中的點。 凸殼是計算幾何中最普遍、最基本的一凸殼是計算幾何中最普遍、最基本的一種結(jié)構(gòu)，在種結(jié)構(gòu)，在CACCA

27、C中使用頻繁。中使用頻繁。 定義：定義：凸多邊形直徑凸多邊形直徑 又稱為平面點集的直徑或平面點集凸殼又稱為平面點集的直徑或平面點集凸殼的直徑，定義為凸多邊形頂點序列中的直徑，定義為凸多邊形頂點序列中距離最距離最大大的點對的連線。的點對的連線。 2.1 2.1 求解平面點集凸殼的算法求解平面點集凸殼的算法 圖圖2-26 2-26 格雷厄姆算法格雷厄姆算法求解群點凸殼的過程求解群點凸殼的過程x圖圖2-27 2-27 夾角序列夾角序列算法算法2.2 2.2 求凸多邊形直徑的算法求凸多邊形直徑的算法 3.Voronoi3.Voronoi圖圖 3.1 Voronoi3.1 Voronoi圖的定義圖的定義

28、 圖圖2-28 2-28 平面兩點的平面兩點的VoronoiVoronoi圖圖Lpjpip1p2L1LrV (p1)V (p2)設設P P1 1，P P2 2是平面上兩點，是平面上兩點，L L是是P P1 1P P2 2的的垂直平分線，垂直平分線，L L將平面分成兩部分將平面分成兩部分Lr和和Ll。位于。位于Ll內(nèi)的點具有特性：內(nèi)的點具有特性：d d( (P Pi i，P P1)1)d d( (P Pi，P P2 2) )，其中，其中d d( (Pi，Pl) )表示表示P Pi i，P Pl l間的間的歐幾里德距離歐幾里德距離。位于位于Ll內(nèi)的點比平面上的其它點更內(nèi)的點比平面上的其它點更接近點

29、接近點P Pl l。換句話說，。換句話說，Ll內(nèi)的點是內(nèi)的點是比平面上其它點更接近比平面上其它點更接近P Pl l的點的軌的點的軌跡，記為跡，記為V(P1)。同理，同理，Lr內(nèi)的點內(nèi)的點是比平面上其它點更接近是比平面上其它點更接近P P2 2的點的的點的軌跡，記為軌跡，記為V(P2)。給定平面上給定平面上n個點的點集個點的點集S= P1, P2, Pn。把上面的定義推廣，定義。把上面的定義推廣，定義V(Pi)為比其為比其它點更接近它點更接近Pi的點的軌跡，是的點的軌跡，是n-1個半平面的個半平面的交，它是一個不多于交，它是一個不多于n-1條邊的凸多邊形域，條邊的凸多邊形域，稱為關聯(lián)于稱為關聯(lián)于

30、Pi的的Voronoi多邊形多邊形或或關聯(lián)于關聯(lián)于Pi的的Voronoi域域。P1P2P3P4P5L1L2L3L4L5圖圖2-29 平面點集的平面點集的Voronoi和和Delaunay三角網(wǎng)三角網(wǎng)Voronoi頂點頂點 Voronoi邊邊 對于對于S S中的每一個中的每一個點都可以作一個點都可以作一個VoronoiVoronoi多邊形，多邊形，這樣的這樣的n n個個VoronoiVoronoi多邊形組成的圖稱多邊形組成的圖稱為為VoronoiVoronoi圖圖，記，記為為Vor(SVor(S) )。Voronoi圖的實質(zhì)圖的實質(zhì)Voronoi圖可以理解為對空間的一種分割方式圖可以理解為對空間

31、的一種分割方式（一個（一個Voronoi多邊形內(nèi)的任意一點到本多邊形內(nèi)的任意一點到本Voronoi多邊形中心點的距離都小于其到其它多邊形中心點的距離都小于其到其它Voronoi多邊形中心點的距離）多邊形中心點的距離），也可以理解，也可以理解為對空間的一種內(nèi)插方式（空間中的任何一為對空間的一種內(nèi)插方式（空間中的任何一個未知點的值都可以由距離它最近的已知點，個未知點的值都可以由距離它最近的已知點，即采樣點的值來替代）。即采樣點的值來替代）。4. Delaunay三角網(wǎng)三角網(wǎng) 4.1 Delaunay三角網(wǎng)的定義三角網(wǎng)的定義 有公共邊的有公共邊的Voronoi多邊形稱為相鄰的多邊形稱為相鄰的Voro

32、noi多邊形，多邊形，連連接所有相鄰接所有相鄰Voronoi多邊形的生長中心所多邊形的生長中心所形成的三角網(wǎng)稱為形成的三角網(wǎng)稱為Delaunay三角網(wǎng)三角網(wǎng)。 4.2 Delaunay三角網(wǎng)的性質(zhì)三角網(wǎng)的性質(zhì) （1）它是）它是唯一唯一的；的；（2）三角形的外圍邊界構(gòu)成群點的）三角形的外圍邊界構(gòu)成群點的凸殼凸殼；（3）任意三角形的外接圓中沒有其它點）任意三角形的外接圓中沒有其它點外接外接圓規(guī)則圓規(guī)則；（4）三角形最大限度地保持均衡，避免狹長三角）三角形最大限度地保持均衡，避免狹長三角形出現(xiàn)形出現(xiàn)最大最小角規(guī)則最大最小角規(guī)則；（5） Delaunay三角網(wǎng)是平面圖，遵守平面圖形三角網(wǎng)是平面圖，遵守

33、平面圖形的歐拉定理；的歐拉定理；（6）Delaunay三角網(wǎng)最多有三角網(wǎng)最多有3n-6條邊和條邊和2n-5個三個三角形，這里角形，這里n是點數(shù)；是點數(shù)；（7）Delaunay三角網(wǎng)和三角網(wǎng)和Voronoi圖是圖是對偶對偶，得到，得到一個就很容易得到另一個。一個就很容易得到另一個。4.3 Delaunay三角網(wǎng)常見算法三角網(wǎng)常見算法 靜態(tài)算法靜態(tài)算法動態(tài)算法動態(tài)算法射線掃描算法（Radial sweeP）遞歸分割算法（Recursive sPlit）分治算法（Divided-and-conquer）漸次算法（SteP-by-steP）層次式修改算法（Modified hierarchical）生

34、長算法（Incremental）生長式刪除重建算法（Incremental delete-and-build）2.4 2.4 圖像處理的基本方法圖像處理的基本方法1. 1. 灰度值變換灰度值變換 45分割型非線性線性分線段性臨界值操作原始灰度值新灰度值反轉(zhuǎn)型255255100100200200圖圖2-32 2-32 灰度值變換的不同傳遞函數(shù)曲線灰度值變換的不同傳遞函數(shù)曲線圖圖2-33 2-33 在灰度值在灰度值1010上作臨界值操作上作臨界值操作2. 2. 兩個柵格圖像的算術組合運算兩個柵格圖像的算術組合運算 3. 3. 擴張擴張 2.5 2.5 數(shù)字地面模型數(shù)字地面模型2.5.1 DEM2.

35、5.1 DEM概述概述2.5.2 DEM2.5.2 DEM建立建立DEMDEM的數(shù)據(jù)獲取的數(shù)據(jù)獲取DEMDEM的建立方法的建立方法2.5.3 DEM2.5.3 DEM應用應用2.5.1 DEM2.5.1 DEM概述概述DEMDEM，(Digital Elevation Models)(Digital Elevation Models)，是國家基，是國家基礎空間數(shù)據(jù)的重要組成部分，它表示地表區(qū)域礎空間數(shù)據(jù)的重要組成部分，它表示地表區(qū)域上地形的上地形的三維向量三維向量的的有限有限序列，即地表單元上序列，即地表單元上高程的集合高程的集合，數(shù)學表達為：，數(shù)學表達為：z=f(xz=f(x，y)y)。 D

36、TMDTM：當：當z z為其它二維表面上為其它二維表面上連續(xù)變化連續(xù)變化的的地理特地理特征征，如地面溫度、降雨、地球磁力、重力、土，如地面溫度、降雨、地球磁力、重力、土地利用、土壤類型等其他地面諸特征，此時的地利用、土壤類型等其他地面諸特征，此時的DEMDEM成為成為DTM(Digital Terrain Models)DTM(Digital Terrain Models)。 概述：概述：DEM 與與 DTM的區(qū)分的區(qū)分數(shù)字高程模型數(shù)字高程模型( (Digital Elevation Digital Elevation ModelModel，DEMDEM) )：研究地面起伏。：研究地面起伏。數(shù)

37、字地形模型數(shù)字地形模型( (Digital Terrain Digital Terrain ModelModel，DTMDTM) )：含有地面起伏和屬：含有地面起伏和屬性性( (如坡度、坡向等如坡度、坡向等) )兩個含義，是兩個含義，是DEMDEM的進一步分析。的進一步分析。概述：概述：DEM的表示方法的表示方法概述：概述：DEM的的線模式線模式表示表示描述高程曲線的描述高程曲線的等高線等高線；數(shù)字化現(xiàn)有等高線地圖產(chǎn)生的數(shù)字化現(xiàn)有等高線地圖產(chǎn)生的DEMDEM比比直接直接利用航空攝影測量方法產(chǎn)生的利用航空攝影測量方法產(chǎn)生的DEMDEM質(zhì)量要差；質(zhì)量要差；數(shù)字化的等高線對于計算坡度或生成著色數(shù)字化

38、的等高線對于計算坡度或生成著色地形圖不十分適用。地形圖不十分適用。概述：等高線模式概述：等高線模式 等高線通常被存儲成一個等高線通常被存儲成一個有序有序的的坐標點序列坐標點序列，可，可以認為是一條帶有高程值屬性的以認為是一條帶有高程值屬性的簡單多邊形簡單多邊形或多邊形或多邊形弧段。由于等高線模型只是表達了區(qū)域的弧段。由于等高線模型只是表達了區(qū)域的部分高程值部分高程值，往往需要一種往往需要一種插值方法插值方法來計算落在來計算落在等高線以外等高線以外的的其他其他點點的高程，又因為這些點是落在兩條等高線包圍的區(qū)的高程，又因為這些點是落在兩條等高線包圍的區(qū)域內(nèi)，所以，通常只要使用域內(nèi)，所以，通常只要使

39、用外包的外包的兩條等高線的高程兩條等高線的高程進行進行插值插值。 概述：概述：DEM的的點模式點模式表示表示高程矩陣高程矩陣( (規(guī)則矩形格網(wǎng)規(guī)則矩形格網(wǎng)) )，與柵格地圖相同。，與柵格地圖相同。表示方法：將區(qū)域劃分成網(wǎng)格，記錄每個網(wǎng)格的表示方法：將區(qū)域劃分成網(wǎng)格，記錄每個網(wǎng)格的高程；高程；線模型到高程矩陣的轉(zhuǎn)換。線模型到高程矩陣的轉(zhuǎn)換。優(yōu)點：計算機處理以柵格為基礎的矩陣很方便，優(yōu)點：計算機處理以柵格為基礎的矩陣很方便，使高程矩陣成為最常見的使高程矩陣成為最常見的DEMDEM；缺點：在平坦地區(qū)出現(xiàn)大量數(shù)據(jù)冗余；若不改變?nèi)秉c：在平坦地區(qū)出現(xiàn)大量數(shù)據(jù)冗余；若不改變格網(wǎng)大小，就不能適應不同的地形條件

40、；在視線計格網(wǎng)大小，就不能適應不同的地形條件；在視線計算中過分依賴格網(wǎng)軸線。算中過分依賴格網(wǎng)軸線。概述：概述：GRID模式模式 規(guī)則格網(wǎng)法是把規(guī)則格網(wǎng)法是把DEMDEM表示成表示成高程矩陣高程矩陣，此時，此時，DEMDEM來源于直接規(guī)則矩形格網(wǎng)采樣點或由不規(guī)則離散數(shù)據(jù)來源于直接規(guī)則矩形格網(wǎng)采樣點或由不規(guī)則離散數(shù)據(jù)點內(nèi)插產(chǎn)生。點內(nèi)插產(chǎn)生。 結(jié)構(gòu)簡單結(jié)構(gòu)簡單，計算機對矩陣的，計算機對矩陣的處理處理比較比較方便方便，高程，高程矩陣已成為矩陣已成為DEMDEM最通用最通用的形式。高程矩陣特別的形式。高程矩陣特別有利于有利于各各種應用。種應用。 概述：概述：GRID模式的缺點模式的缺點GridGrid系

41、統(tǒng)有下列系統(tǒng)有下列缺點缺點：1 1、地形簡單的地區(qū)存在、地形簡單的地區(qū)存在大量冗余數(shù)據(jù)大量冗余數(shù)據(jù)；2 2、如不改變?nèi)绮桓淖兏窬W(wǎng)大小格網(wǎng)大小, ,則則無法適用無法適用于起于起伏程度不同的地區(qū)；伏程度不同的地區(qū)；3 3、對于某些特殊計算如、對于某些特殊計算如視線視線計算時，格計算時，格網(wǎng)的網(wǎng)的軸線方向被夸大軸線方向被夸大；4 4、由于柵格過于粗略，、由于柵格過于粗略，不能精確不能精確表示地表示地形的關鍵特征形的關鍵特征, ,如山峰、洼坑、山脊等；如山峰、洼坑、山脊等； 概述：不規(guī)則三角網(wǎng)概述：不規(guī)則三角網(wǎng)( (TINTIN) ) TINTIN（Triangulated Irregular Net

42、workTriangulated Irregular Network) )表示法利表示法利用所有采樣點取得的離散數(shù)據(jù)，按照用所有采樣點取得的離散數(shù)據(jù)，按照優(yōu)化組合優(yōu)化組合的原則，的原則，把這些離散點把這些離散點( (各三角形的頂點各三角形的頂點) )連接成相互連續(xù)的連接成相互連續(xù)的三三角面角面( (在連接時，盡可能地確保每個三角形都是在連接時，盡可能地確保每個三角形都是銳角銳角三角形三角形或是三邊的或是三邊的長度近似長度近似相等相等DelaunayDelaunay) )。 因為因為TINTIN可根據(jù)地形的可根據(jù)地形的復雜程度復雜程度來確定采樣點的來確定采樣點的密密度度和和位置位置，能，能充分表

43、示充分表示地形特征點和線，從而地形特征點和線，從而減少了減少了地形較平坦地區(qū)的地形較平坦地區(qū)的數(shù)據(jù)冗余數(shù)據(jù)冗余。 概述：概述：TINTIN的三角剖分的三角剖分概述：概述：TINTIN模型的存儲方式模型的存儲方式NoXYZ190.010.043.5250.710.067.3367.223.962.6:1010.090.081.0概述：概述：TINTIN模型的表現(xiàn)模型的表現(xiàn)概述：概述：TINTIN小結(jié)小結(jié)表示方法：表示方法：將區(qū)域劃分為相鄰的三角面網(wǎng)絡，區(qū)將區(qū)域劃分為相鄰的三角面網(wǎng)絡，區(qū)域中任意點都將落在三角面頂點、線或三角形內(nèi)。域中任意點都將落在三角面頂點、線或三角形內(nèi)。落落在頂點上在頂點上其高

44、程與頂點相同；落其高程與頂點相同；落在線上在線上則由兩個則由兩個頂點線性插值得到；落頂點線性插值得到；落在三角形內(nèi)在三角形內(nèi)則由三個頂點插則由三個頂點插值得到。值得到。生成方法：生成方法：由不規(guī)則點、矩形格網(wǎng)或等高線轉(zhuǎn)換由不規(guī)則點、矩形格網(wǎng)或等高線轉(zhuǎn)換而得到。而得到。TINTIN允許在地形復雜地區(qū)收集較多的信息，而在允許在地形復雜地區(qū)收集較多的信息，而在簡單的地區(qū)收集少量信息，避免數(shù)據(jù)冗余。簡單的地區(qū)收集少量信息，避免數(shù)據(jù)冗余。對于某些類型的運算比建立在數(shù)字等高線基礎上對于某些類型的運算比建立在數(shù)字等高線基礎上的系統(tǒng)更有效，如坡度、坡向等的計算。的系統(tǒng)更有效，如坡度、坡向等的計算。概述：概述：

45、建立建立DEMDEM的目的的目的 1 1）作為國家地理信息的基礎數(shù)據(jù)；）作為國家地理信息的基礎數(shù)據(jù)； 2 2）土木工程、景觀建筑與礦山工程規(guī)劃與設計；）土木工程、景觀建筑與礦山工程規(guī)劃與設計； 3 3）為軍事目的而進行的三維顯示；）為軍事目的而進行的三維顯示； 4 4）景觀設計與城市規(guī)劃；）景觀設計與城市規(guī)劃； 5 5）流水線分析、可視性分析；）流水線分析、可視性分析； 6 6）交通路線的規(guī)劃與大壩選址；）交通路線的規(guī)劃與大壩選址； 7 7）不同地表的統(tǒng)計分析與比較；）不同地表的統(tǒng)計分析與比較； 8 8）生成坡度圖、坡向圖、剖面圖、輔助地貌分析、估計侵蝕和徑流等；）生成坡度圖、坡向圖、剖面圖、

46、輔助地貌分析、估計侵蝕和徑流等； 9 9）作為背景疊加各種專題信息如土壤、土地利用及植被覆蓋數(shù)據(jù)等，以）作為背景疊加各種專題信息如土壤、土地利用及植被覆蓋數(shù)據(jù)等，以進行顯示與分析；進行顯示與分析； 1010）與）與GISGIS聯(lián)合進行空間分析；聯(lián)合進行空間分析； 1111）虛擬現(xiàn)實）虛擬現(xiàn)實(Virtual Reality)(Virtual Reality)； 此外，從此外，從DEMDEM還能派生以下主要產(chǎn)品：平面等高線圖、立體等高線圖、等還能派生以下主要產(chǎn)品：平面等高線圖、立體等高線圖、等坡度圖、暈渲圖、通視圖、縱橫斷面圖、三維立體透視圖、三維立體彩色圖坡度圖、暈渲圖、通視圖、縱橫斷面圖、三

47、維立體透視圖、三維立體彩色圖等。等。 DEMDEM數(shù)據(jù)來源數(shù)據(jù)來源DEMDEM數(shù)據(jù)采集數(shù)據(jù)采集數(shù)字攝影測量：數(shù)字攝影測量：利用帶自動記錄裝置的立體測利用帶自動記錄裝置的立體測圖儀或立體坐標儀、解析測圖儀及數(shù)字攝影測量圖儀或立體坐標儀、解析測圖儀及數(shù)字攝影測量系統(tǒng)，進行人工、半自動或全自動的量測。其原系統(tǒng)，進行人工、半自動或全自動的量測。其原理是在攝影圖的基礎上利用測圖儀進行測量。理是在攝影圖的基礎上利用測圖儀進行測量?，F(xiàn)有地圖數(shù)字化：現(xiàn)有地圖數(shù)字化：對已有地圖上的信息對已有地圖上的信息( (如等如等高線高線) )進行數(shù)字化。進行數(shù)字化。地面測量：地面測量：利用自動記錄的測距經(jīng)緯儀在野外利用自動

48、記錄的測距經(jīng)緯儀在野外實地測量。實地測量?？臻g傳感器：空間傳感器：利用利用GPSGPS，結(jié)合雷達和激光測高，結(jié)合雷達和激光測高儀采集數(shù)據(jù)。儀采集數(shù)據(jù)。數(shù)字攝影測量采樣點的選取數(shù)字攝影測量采樣點的選取沿等高線采樣：沿等高線采樣：主要用于山區(qū)采樣。主要用于山區(qū)采樣。規(guī)則網(wǎng)格采樣：規(guī)則網(wǎng)格采樣：按規(guī)則矩形網(wǎng)格進行采樣，按規(guī)則矩形網(wǎng)格進行采樣，可直接生成規(guī)則矩形格網(wǎng)的可直接生成規(guī)則矩形格網(wǎng)的DEMDEM數(shù)據(jù)。數(shù)據(jù)。漸進采樣：漸進采樣：根據(jù)地形使采樣點合理分布，根據(jù)地形使采樣點合理分布，即平坦地區(qū)采樣點少，地形復雜區(qū)采樣點多。即平坦地區(qū)采樣點少，地形復雜區(qū)采樣點多。選擇采樣：選擇采樣：根據(jù)地形特征進行采

49、樣，如沿根據(jù)地形特征進行采樣，如沿山脊線、山谷線等進行采集。山脊線、山谷線等進行采集?；旌喜蓸??；旌喜蓸?。注意：所有采集的數(shù)據(jù)都要按一定注意：所有采集的數(shù)據(jù)都要按一定的空間插值方法轉(zhuǎn)換成點模式格式的空間插值方法轉(zhuǎn)換成點模式格式數(shù)據(jù)。數(shù)據(jù)。2.5.2 2.5.2 DEMDEM的生成的生成方法：方法：1 1、人工格網(wǎng)法、人工格網(wǎng)法2 2、三角網(wǎng)法、三角網(wǎng)法3 3、立體像對法、立體像對法4 4、曲面擬合法、曲面擬合法5 5、等值線插值法、等值線插值法人工格網(wǎng)法人工格網(wǎng)法在地形圖上蒙上格網(wǎng)，在地形圖上蒙上格網(wǎng)，逐格逐格讀取讀取中心點中心點或或交點交點的高程值。的高程值。三角網(wǎng)法三角網(wǎng)法 對有限個離散點

50、，對有限個離散點，每三個每三個鄰近點鄰近點聯(lián)結(jié)成聯(lián)結(jié)成三角形，三角形，每個三角形代表一個每個三角形代表一個局部平面局部平面，再根據(jù)每個平面方，再根據(jù)每個平面方程，可計算程，可計算各格網(wǎng)點各格網(wǎng)點高程，生成高程，生成DEMDEM。 構(gòu)三角網(wǎng)的要求構(gòu)三角網(wǎng)的要求應盡可能保證每個三角形是銳角三角應盡可能保證每個三角形是銳角三角形或三邊的長度近似相等，避免出現(xiàn)形或三邊的長度近似相等，避免出現(xiàn)過大的鈍角和過小的銳角。過大的鈍角和過小的銳角。 角度判斷法建立角度判斷法建立TINTIN當已知三角形的兩個頂點后，利用當已知三角形的兩個頂點后，利用余余弦定理弦定理計算備選第三頂點的三角形內(nèi)計算備選第三頂點的三角

51、形內(nèi)角的大小，選擇最大者對應的點為該角的大小，選擇最大者對應的點為該三角形的第三頂點。三角形的第三頂點。 將原始數(shù)據(jù)分塊將原始數(shù)據(jù)分塊 檢索所處理三角形鄰近點檢索所處理三角形鄰近點C1C2C3確定第一個三角形確定第一個三角形iCCmax則C為該三角形第三頂點 AB構(gòu)網(wǎng)示意圖構(gòu)網(wǎng)示意圖與與A A點距離點距離最近的點最近的點哪個內(nèi)哪個內(nèi)角最大角最大iiiiibacbaC2cos222三角形的擴展三角形的擴展對每一個已生成的三角形的新增加的兩對每一個已生成的三角形的新增加的兩邊，按角度最大的原則向外進行擴展，邊，按角度最大的原則向外進行擴展，并進行是否重復的檢測。并進行是否重復的檢測。向外擴展的處理

52、：若從頂點為向外擴展的處理：若從頂點為P P1 1(X(X1 1,Y,Y1 1), ), P P2 2(X(X2 2,Y,Y2 2), P), P3 3(X(X3 3,Y,Y3 3) )的三角形之的三角形之P P1 1P P2 2邊向外擴邊向外擴展，應取位于直線展，應取位于直線P P1 1P P2 2與與P P3 3異側(cè)的點異側(cè)的點 異則判斷異則判斷0)()(),(1212112YYXXXXYYYXFp3p2若備選點P之坐標為（X，Y）重復與交叉的檢測：任意一邊最多只能是兩個三角形的公共邊。p1立體像對法立體像對法資料來源于張超主編的資料來源于張超主編的地理信息系統(tǒng)教程地理信息系統(tǒng)教程所配光盤

53、所配光盤曲面擬合法曲面擬合法 根據(jù)根據(jù)有限個有限個離散點的高程，采用離散點的高程，采用多項式多項式或或樣條函數(shù)樣條函數(shù)求得求得擬合公式擬合公式，再逐個計算各點的高程，得到擬合的再逐個計算各點的高程，得到擬合的DEMDEM?？煞从??？煞从晨偟牡貏菘偟牡貏?，但，但局部局部誤誤差差較大較大?？煞譃椋??？煞譃椋赫w擬合：根據(jù)研究區(qū)域內(nèi)整體擬合：根據(jù)研究區(qū)域內(nèi)所有采樣點所有采樣點的觀測值建立的觀測值建立趨勢面模型趨勢面模型。特。特點是不能反映內(nèi)插區(qū)域內(nèi)的局部特征。點是不能反映內(nèi)插區(qū)域內(nèi)的局部特征。局部擬合：利用局部擬合：利用鄰近的鄰近的數(shù)據(jù)點數(shù)據(jù)點估計估計未知點的值，能未知點的值，能反映局部反映局部特征

54、。特征。等高線插值法等高線插值法2.5.3 DEM2.5.3 DEM的應用的應用1 1、基于、基于DEMDEM的信息提取的信息提取2 2、等高線的繪制、等高線的繪制3 3、基于、基于DEMDEM的可視化分析的可視化分析1 1、三維景觀、三維景觀2 2、數(shù)碼城市和虛擬現(xiàn)實、數(shù)碼城市和虛擬現(xiàn)實3 3、DEMDEM在工程上的應用在工程上的應用概述應用：概述應用：應用算法：應用算法：三維景觀三維景觀數(shù)碼城市和虛擬現(xiàn)實數(shù)碼城市和虛擬現(xiàn)實City ModelDOMDEMDLGAttribute RDB數(shù)碼深圳數(shù)碼深圳3D 3D 建筑建筑DEM+DOM+DLG交通行業(yè)：數(shù)字公路交通行業(yè)：數(shù)字公路DEMDEM的土石方計算的土石方計算立體計算線路挖土、石方量立體計算線路挖土、石方量坡度的計算坡度的計算YZZZZXZZZZYX22t