地圖綜合線目標的綜合算法研究-畢業(yè)論文

1、<p>　　地圖綜合線目標的綜合算法研究</p><p><b>　　目錄</b></p><p><b>　　目錄I</b></p><p><b>　　圖表目錄III</b></p><p><b>　　摘要1</b></p>

2、;<p>　　ABSTRACT2</p><p><b>　　第一章 緒論3</b></p><p><b>　　1.1引言3</b></p><p><b>　　1.2研究背景4</b></p><p>　　1.3論文的組織5</p>&

3、lt;p>　　第二章 線目標綜合的基本理論和評價方法6</p><p>　　2.1線目標綜合的基本原理6</p><p>　　2.2線目標綜合的基本方法7</p><p>　　2.2.1 角度法8</p><p>　　2.2.2 面積法9</p><p>　　2.2.3 垂比弦算法9</p>

4、;<p>　　2.2.4 弧比弦算法10</p><p>　　2.3線目標綜合基本方法的不足11</p><p>　　2.4算法評價的基本原理及指標介紹12</p><p>　　2.5本章小結13</p><p>　　第三章 弧比弦算法的設計及改進14</p><p>　　3.1弧比弦算法的基本

5、原理14</p><p>　　3.2弧比弦算法的改進18</p><p>　　3.2.1增強支撐域的自適應性改進18</p><p>　　3.2.2 增強算法的迭代性更優(yōu)化其性能22</p><p>　　3.3本章小結26</p><p>　　第四章 在Visual Studio 2008平臺上用Arc En

6、gine 9.3二次開發(fā)實現(xiàn)算法27</p><p>　　4.1開發(fā)平臺介紹27</p><p>　　4.1.1、Arc Engine 9.3介紹27</p><p>　　4.1.2、Visual Studio 2008 C#.NET介紹27</p><p>　　4.2算法的實現(xiàn)28</p><p>　　4.

7、2.1、MainForm窗體28</p><p>　　4.2.2、CArcDivideDistance類31</p><p>　　4.2.3、CNewArcDDistance類32</p><p>　　4.2.4、CNewDDis1類33</p><p>　　4.2.5、CEvalution類34</p><p&

8、gt;　　4.3 本章小結35</p><p>　　第五章 總結及展望36</p><p><b>　　主要參考文獻37</b></p><p><b>　　致謝38</b></p><p><b>　　圖表目錄</b></p><p>　　圖1

9、 曲線簡化算法示例6</p><p>　　圖2 線目標綜合算法的分類8</p><p><b>　　圖3 角度法8</b></p><p><b>　　圖4 面積法9</b></p><p>　　圖5 垂比弦算法10</p><p>　　圖6 弧比弦算法10<

10、;/p><p>　　圖7 曲線簡化法生成自相交11</p><p>　　圖8 連續(xù)剔除節(jié)點造成曲線大的失真11</p><p>　　圖9 曲線簡化算法的性能評價——矢量和面的位移12</p><p>　　圖10 Nakos–Mitropoulos算法14</p><p>　　圖11 原始曲線圖15</p&g

11、t;<p>　　圖12 用弧比弦算法簡化線目標16</p><p>　　圖13 用弧比弦算法簡化線目標17</p><p>　　圖14 增強支撐域的自適應性改進18</p><p>　　圖15 增強支撐域的自適應性改進結果圖119</p><p>　　圖16 增強支撐域的自適應性改進結果圖220</p>

12、<p>　　圖17 兩種算法的每個點的弧比弦值22</p><p>　　圖18 增強算法的迭代性改進算法2結果圖123</p><p>　　圖19 增強算法的迭代性改進算法2結果圖224</p><p>　　圖20 程序主界面28</p><p>　　表1 弧比弦算法保留點不同的評價指標16</p><

13、p>　　表2 弧比弦算法保留點不同的評價指標17</p><p>　　表3 增強支撐域的自適應性改進評價結果表121</p><p>　　表4 增強支撐域的自適應性改進評價結果表221</p><p>　　表5 增強算法的迭代性改進算法2評價結果表125</p><p>　　表6 增強算法的迭代性改進算法2評價結果表225&l

14、t;/p><p><b>　　摘要</b></p><p>　　地圖綜合是地理信息科學界、地圖制圖科學界的重要研究課題之一。其中線目標的綜合算法研究是一個關鍵的問題。現(xiàn)有線目標綜合算法大多是考慮線目標的節(jié)點曲率，通過確定節(jié)點的重要性程度來進行節(jié)點剔除，以實現(xiàn)線目標的簡化。然而，現(xiàn)有算法在算法效率、簡化錯誤率、表達效果等方面都存在不足。為此，本文試圖解決這些問題，提出一種迭

15、代的自適應弧比弦算法。首先，本文簡要地回顧了國內(nèi)外地圖綜合的發(fā)展現(xiàn)狀，闡述了線目標綜合的基本理論和方法；然后，結合弧比弦算法的優(yōu)缺點，提出了一種自適應弧比弦算法，降低了曲線簡化的錯誤率，優(yōu)化了算法結果。在此基礎上，使用迭代法對改進算法進行了進一步優(yōu)化，在不追求算法效率的前提下得到了更優(yōu)的效果。進而，通過在Visual Studio 2008平臺中用C#.NET + Arc Engine 9.3二次開發(fā)實現(xiàn)原弧比弦算法及其改進算法，進一步

16、驗證了本文改進算法的可行性、有效性和健壯性。最后，總結了本文的研究成果，并展望了該方向進一步研究的若干問題。</p><p>　　關鍵字： 地圖綜合；線目標簡化；弧比弦；算法改進</p><p><b>　　ABSTRACT</b></p><p>　　In the map generalization, generalization of t

17、he line feature was very important. For the generalization of the line feature, point-reduction is one of the most important issues. In the process of the curve simplification, a most basic issue is how to measure the im

18、portance of all vertices in the curve. This article briefly retrospect the development status of the map generalization both abroad and at home, elaborates the basic principle and method on the local length ratio algorit

19、hm, compares i</p><p>　　Key words：map generalization; measure of the importance of vertices in the curve; local length ratio algorithm; improvement of the algorithm</p><p><b>　　第一章 緒論</

20、b></p><p><b>　　1.1引言</b></p><p>　　隨著地理信息系統(tǒng)應用領域和需求層次的不斷擴展和多樣化,地圖綜合問題成了當前地理信息科學研究的熱點問題[1]。地圖綜合中的一個重要內(nèi)容是單個線目標的綜合，其核心問題是曲線的簡化。這一問題作為地圖綜合的重要組成部分被許多學者所研究,并廣泛應用于地理信息科學、計算機視覺、計算機圖形學、模式識別等

21、諸多領域[2]。例如，在地理信息科學領域，曲線簡化應用于地圖綜合、數(shù)據(jù)壓縮等方面；在模式識別與計算機圖形學領域，曲線簡化則用于目標提取，節(jié)點的壓縮編碼等方面。</p><p>　　在曲線簡化的過程中，一個最基本的問題是如何確定曲線上節(jié)點的重要性程度。Attneave發(fā)現(xiàn)在曲線上，一部分節(jié)點比另一部分節(jié)點有著更豐富的信息，保留那些有著豐富信息的節(jié)點可以在曲線簡化后盡可能保持曲線的形狀不變和曲線的信息不丟失[3]。即

22、在曲線簡化中剔除部分含信息較少的節(jié)點不會導致曲線大的變形和信息的丟失，從而很好的實現(xiàn)曲線的簡化。于是，怎樣找出這些含有較多信息的節(jié)點就是曲線簡化的一個重要問題。而本文的主題就是討論如何找出曲線上那些含有豐富信息的節(jié)點，即曲線簡化方法優(yōu)化的問題。</p><p>　　目前，許多學者都在研究如何度量曲線上節(jié)點的重要性程度并簡化曲線，他們提出的方法大致有以下兩個方向：無支撐域的曲線簡化方法和有支撐域的曲線簡化方法。其中

23、無支撐域的曲線簡化方法主要包括角度法[4-6]、面積法[7]等；有支撐域的曲線簡化方法則主要包括弧比弦算法[8]、垂比弦算法[9]等。現(xiàn)在又有許多綜合性算法，比如弧比弦算法與角度法的結合、垂比弦算法與角度法的結合等[1]。地圖綜合中著名的道格拉斯——普克算法就是無支撐域的曲線簡化方法的一種[10]。這些算法都在地圖綜合中廣泛使用，其中角度法、面積法在地圖綜合中使用較早，但效果沒有后幾種方法好，所以現(xiàn)在普遍使用后幾種算法實現(xiàn)地圖綜合。&l

24、t;/p><p>　　本文從弧比弦算法入手，先介紹該算法的工作原理，對其進行分析，總結出它的優(yōu)點和不足，并對其不足進行自適應的改進。在此基礎上，使用迭代法對自適應改進算法進行進一步優(yōu)化，在不追求算法效率的前提下得到了更優(yōu)的效果。繼而采用當下流行的Visual Studio 2008平臺用C#.NET + Arc Engine 9.3二次開發(fā)實現(xiàn)弧比弦算法及其改進算法，并用給出的曲線簡化評價指標對其進行評價，最后得出結

25、論。</p><p><b>　　1.2研究背景</b></p><p>　　地圖綜合是傳統(tǒng)制圖學和自然地理學的課題，和所有其他地理學課題一樣，現(xiàn)在它也成為地理信息科學界的重要課題之一。從表現(xiàn)形式上看，地圖綜合是指地圖信息隨顯示范圍的變化而具有不同詳細程度。這種變化主要是由于地圖的縮放操作而引起的。在實際中，地圖的綜合包含兩層含義：一是顯示具有單一比例尺數(shù)據(jù)的某一地圖

26、時，在不同的縮放比率下地圖呈現(xiàn)出具有不同詳細程度的外觀;二是當?shù)貓D有多級比例尺時，當?shù)貓D的縮放比率達到一定程度時，可以自動調(diào)閱該圖上一級或下一級比例尺的地圖[11]。最理想的綜合應是地圖自動逐級抽象，這也是自動綜合的研究目標，但目前實現(xiàn)起來仍較為困難。</p><p>　　在以往地圖綜合的研究中，4個人先后出現(xiàn)提出了線目標的綜合，他們分別是：Tobler (1966)、Töpfer(1966)、Pill

27、ewizer (1966) 和Perkal (1966)。在20世紀70年代，線目標綜合算法得到了飛速發(fā)展，到20世紀80年代，學者們對這些線目標綜合算法進行了評價，并展開了面目標的綜合算法研究。</p><p>　　20世紀90年代以來，地圖綜合一直是熱門的研究課題。國際制圖協(xié)會（ICA）于1991年成立自動制圖綜合小組。國際攝影測量與遙感（ISPRS）協(xié)會于2000年專門設立了一個地圖綜合工作組。目前關于這一

28、主題的特別會議已經(jīng)舉辦了多次，并且都取得了巨大的成果。</p><p>　　線目標的綜合從地圖綜合的研究出現(xiàn)至今，一直經(jīng)歷著快速的發(fā)展。從Attneave發(fā)現(xiàn)線目標上的一些點比另一些點包含更加豐富的信息，學者們就相繼發(fā)現(xiàn)了曲線簡化的一系列方法，例如角度法，面積法，垂比弦算法，弧比弦算法等。后來又提出了一系列曲線簡化算法的評價標準，實現(xiàn)了算法效能的評價?，F(xiàn)在學者們又開始了算法的融合和該進[12]，想進一步優(yōu)化算法的

29、性能，這就是當前線目標綜合的研究方向。</p><p>　　40多年過去了，隨著地理信息科學的發(fā)展，地圖綜合和曲線簡化經(jīng)過40年余年的發(fā)展已經(jīng)相對比較成熟。一門學科經(jīng)過40多年的發(fā)展而確立，學科越來越完善，這標志著它的逐漸成熟。</p><p><b>　　1.3論文的組織</b></p><p>　　本文共分為五章，分別從論文背景及問題的提出

30、；線目標綜合的基本理論、方法和弧比弦算法的分析和評價；弧比弦算法的不足及其改進以及改進算法的評價；在Visual Studio 2008平臺上用Arc Engine 9.3二次開發(fā)實現(xiàn)弧比弦算法及其改進算法這五個方面進行闡述，下面對其分別進行介紹：</p><p>　　第一章為概論，首先闡述了論文的基本情況，介紹了地圖綜合的研究背景，以及論文研究問題的提出，說明了章節(jié)的安排情況。</p><p

31、>　　第二章為線目標綜合的基本理論和方法，介紹了線目標綜合的基本原理和方法，闡述了線目標綜合算法的一些不足及改進方向，并對線目標綜合算法的評價給出了基本的原理及指標。</p><p>　　第三章為弧比弦算法的設計及改進，首先介紹了弧比弦算法的基本原理，然后指出弧比弦算法的一些不足，并結合曲線綜合的改進方向就兩個方面對其進行改進，逐步得出最終的改進算法，最后給出算法的評價，得出自己的結論。</p>

32、<p>　　第四章為在 Visual Studio 2008平臺上用Arc Engine 9.3二次開發(fā)實現(xiàn)算法，首先介紹了開發(fā)的基本平臺，然后分別講述了原弧比弦算法及其改進算法的實現(xiàn)方法。</p><p>　　第五章為總結及展望，主要總結了我在論文完成中遇到的一些問題及以后對該課題的后續(xù)研究方向。</p><p>　　最后為主要參考文獻及致謝。</p><

33、;p>　　第二章 線目標綜合的基本理論和評價方法</p><p>　　2.1線目標綜合的基本原理</p><p>　　線目標綜合算法，顧名思義，是減少曲線上不必要的點的數(shù)量，用較少的含有豐富信息的點來表達這條曲線的算法，我們也稱這種算法為曲線簡化算法。在早期，減少曲線上的點的數(shù)量是一個十分重要的課題，因為在當時而言，存儲曲線的大量數(shù)據(jù)是一個很大的開銷。于是就有許多學者開始研究如何用較

34、少的含有豐富信息的點來代替原始曲線以達到曲線簡化的目的。圖1說明了曲線簡化算法的基本思想。圖1a是一條曲線，它有許多點組成，但其中只有少數(shù)被選擇用來代表原來的線目標。圖1b則顯示了許多曲線簡化的可能結果之一，它用五個點來代表原始曲線。</p><p>　　圖1 曲線簡化算法示例</p><p>　　我們利用曲線簡化算法進行線目標綜合的原理如下：通常情況下，通過刪除一些點，線的形狀可以簡化。

35、所以許多學者用這種算法實現(xiàn)線目標的綜合。曲線簡化算法的目標是盡量用最少的點去擬合原始曲線。必須強調(diào)的是，在這些算法中應該盡量避免尺度的變化。這樣就可以實現(xiàn)線目標的綜合了。</p><p>　　曲線簡化算法的最初思想，是由Attneave在1954年發(fā)現(xiàn)的，他發(fā)現(xiàn)線目標上的一些點比其他一些點有著更豐富的信息，這些有著豐富信息的較少的點足以表達線目標的形狀。換言之，大量的信息較少的點，可以被除去而不會造成線目標大的變

36、形。在這種思想中，那些有著豐富信息的點，在計算機圖形學和模式識別學我們稱之為支配點；而在空間信息科學中則被我們稱作關鍵點。</p><p>　　關鍵點在許多學科中都是一個重要的概念，如計算機視覺、圖像處理、模式識別、計算機圖形學和地理空間科學等。例如，在地理空間科學中，關鍵點的概念可應用于數(shù)據(jù)壓縮，線的夸張表達，以及線的綜合等；在計算機視覺和模式識別中，則可應用于特征提取，形狀識別，基于點的運動的評價和編碼的算法

37、等。</p><p>　　而我們知道，在經(jīng)典的幾何學中，曲線的關鍵點通常是：</p><p><b>　　極大值點</b></p><p><b>　　極小值點</b></p><p><b>　　曲率極小值點</b></p><p><b>

38、　　曲率極大值點</b></p><p>　　而Freeman1978年在上述列表中增加了以下新的內(nèi)容[1]：</p><p><b>　　曲率不連續(xù)點</b></p><p><b>　　終點</b></p><p><b>　　交點</b></p>

39、<p><b>　　切點</b></p><p>　　由于這些點都擁有明確的定義，他們的特征不會受到曲線縮放（擴大或減少），旋轉或平移的影響，所以它們十分適合被當作曲線的關鍵點。</p><p>　　而怎樣找出這些關鍵點并用它來表示原始曲線，就成為線目標綜合算法研究的主要問題。</p><p>　　2.2線目標綜合的基本方法<

40、/p><p>　　線目標綜合主要有兩種基本方法：無支撐域的綜合方法和有支撐域的綜合方法。無支撐域的綜合方法主要包括角度法、面積法等；而有支撐域的綜合方法主要包括弧比弦算法和垂比弦算法等。而現(xiàn)在又產(chǎn)生了許多綜合性算法，比如弧比弦算法與角度法的結合、垂比弦算法與角度法的結合等。圖2顯示了這樣的分類。</p><p>　　通過分析可以發(fā)現(xiàn)，用作無支撐域的曲線綜合算法的標準通常主要是原始的幾何參數(shù)（如

41、距離，角度，面積等），而用作有支撐域的曲線綜合的標準則主要是幾何參數(shù)的運算結果（如垂比弦值和弧比弦值等）。下面將分別介紹這幾種算法，見圖2。</p><p>　　圖2 線目標綜合算法的分類</p><p><b>　　2.2.1 角度法</b></p><p>　　一條曲線如果刪除其中某個點,將會引起一個角度的變化。因此，可以根據(jù)這一角度變化的

42、大小來度量這個點的重要性，當然端點應該除外。我們不妨設曲線上的點依次為P0，P1，P2，?，Pn(P0和Pn為曲線的兩個端點) ,那么刪除任一點Pi所引起的角度變化可以表達為：</p><p><b>　?。?）</b></p><p>　　圖3的曲線有5個節(jié)點,分別記為P0、P1、P2、P3和P4。根據(jù)式(1)可依次計算得到P1、P2和P3的角度度量值。我們可以知道

43、，角度變化越大,點的重要性程度越高，其值也就越大。</p><p><b>　　圖3 角度法</b></p><p><b>　　2.2.2 面積法</b></p><p>　　一條曲線如果刪除其中某個點將會產(chǎn)生一個局部變形。因此，可以利用新曲線與原始曲線圍成的變形的面積來度量這個點的重要性(圖4)。這一方法稱為面積法。刪

44、除每個點(端點除外)所引起的面積變化可以表達為：</p><p><b>　　(2)</b></p><p>　　圖4的曲線有5個節(jié)點,分別記為P0、P1、P2、P3和P4。根據(jù)式(2) ,可以得到圖中每個節(jié)點的面積變形值。面積變形值越大,節(jié)點重要性程度越高。相反，面積變形值越小,節(jié)點重要性程度則越低。</p><p><b>　　圖

45、4 面積法</b></p><p>　　2.2.3 垂比弦算法</p><p>　　曲線上的節(jié)點Pi ,其重要性可以根據(jù)該點到其鄰近點Pi-k、Pi+k連接弦長的垂直距離Di,k,與弦長Ci,k的比值來度量,該種度量方法稱之為垂比弦算法,其表達式可以表達為：</p><p><b>　　(3)</b></p><

46、p>　　式中k的取值從1開始,直到滿足如下條件結束:</p><p><b>　　(4)</b></p><p>　　如圖5 ,對于點P4,k取值為2。不難發(fā)現(xiàn)，該方法是一種自適應度量方法,它沒有固定的支撐域。而這里支撐域可以理解為一種約束,即式(4)。</p><p><b>　　圖5 垂比弦算法</b></

47、p><p>　　2.2.4 弧比弦算法</p><p>　　弧比弦算法是曲線簡化算法中較為成熟高效的一種算法，見圖6，Teh和Chin用兩點之間的弧長和相應的弦長的比值來度量節(jié)點的重要性，不同于用垂直距離Di,k,與相應弦長Ci,k的比值來度量節(jié)點的重要性的垂比弦算法，弧比弦算法的表達式可以表達為：</p><p><b>　　(5)</b><

48、;/p><p>　　一種特殊的情況是支撐域的圓與曲線只有一個交點,這種情況下,我們把圓心到這一交點的直線距離作為弦長Ci,k,即弦長Ci,k等于半徑R。</p><p><b>　　圖6 弧比弦算法</b></p><p>　　2.3線目標綜合基本方法的不足</p><p>　　大多數(shù)曲線簡化算法可能有以下幾個不足：<

49、/p><p>　　1、算法得到的解可能不是最優(yōu)的。</p><p>　　這一問題正是我算法改進所參考的主要因素，提高算法的效率及性能，達到算法的優(yōu)化是所有算法改進工作的最終目標，我此次改進也是從這方面入手的。</p><p>　　2、不能保證生成曲線之間的自相交。</p><p>　　自相交的問題見圖7，產(chǎn)生曲線的自相交將嚴重破壞曲線的拓撲關系，

50、極端的時候可能會產(chǎn)生致命的缺陷，所以優(yōu)秀的綜合算法必須盡可能的避免產(chǎn)生曲線的自相交問題。</p><p>　　圖7 曲線簡化法生成自相交</p><p>　　3、可能連續(xù)剔除節(jié)點而造成新生成曲線大的失真。</p><p>　　算法可能造成節(jié)點的連續(xù)剔除而導致曲線產(chǎn)生較大的變形，如圖，曲線簡化時由于節(jié)點的連續(xù)剔除而出現(xiàn)曲線的嚴重變形。</p><p

51、>　　圖8 連續(xù)剔除節(jié)點造成曲線大的失真</p><p>　　4、保留的節(jié)點并不一定對曲線的表達是必須的。</p><p>　　這一問題是現(xiàn)在綜合算法的前沿研究方向，怎樣確定曲線上點的重要性程度成為許多學者研究的方向，即曲線上節(jié)點的信息量的度量方法，我在今后的研究中將進一步的研究這個方向。</p><p>　　以上所說的這些問題往往會造成算法的效果不盡如人意，

52、所以許多學者提出了許多針對以上問題的算法改進方法，在下一章中我也將針對這些問題對弧比弦算法進行一些改進，并提出一種新的改進弧比弦算法。</p><p>　　2.4算法評價的基本原理及指標介紹</p><p>　　White(1985)和McMaster(1986)提出了一些指標來評價曲線簡化算法的性能：即矢量位移和面位移[13]。這兩個參數(shù)是見圖9，圖9a是由原始曲線和保留點組成的新曲線所

53、形成的矢量位移，圖9b則是由原始曲線和保留點組成的新曲線所形成的面位移。顯然，矢量位移和面位移越小，算法的性能就越好。在矢量位移上，最大誤差、中位數(shù)、平均誤差均可作為其指標。</p><p>　　圖9 曲線簡化算法的性能評價——矢量和面的位移</p><p>　　而我在后文中將采用偏移平均值，偏移中值和面積變形值作為評價指標，這三種指標主要是通過對刪除曲線上一些重要性程度較低的節(jié)點進行評價

54、,在很大程度上可以視為對破壞原始曲線的穩(wěn)定性的評價。對于向量偏移,我計算其中值和平均值，即偏移平均值和偏移中值;對于面積變形,我通過簡化后的曲線與原始曲線進行疊加,然后計算產(chǎn)生的一系列區(qū)域單元的面積總和即可。</p><p><b>　　2.5本章小結</b></p><p>　　本章開始闡述了線目標綜合的基本方法，重點介紹了角度法、面積法、垂比弦算法以及弧比弦算法，

55、并且指出了這些算法的一些共同不足，例如算法得到的解可能不是最優(yōu)的；可能不能保證生成曲線之間的自相交問題；可能連續(xù)剔除節(jié)點而造成新生成曲線大的失真；曲線保留的節(jié)點可能并不一定對曲線的表達是必須的。最后指出了評價這些算法的一個標準，即矢量位移和面位移，給出了本文評價這些算法的標準，即采用偏移平均值，偏移中值和面積變形值作為評價指標。</p><p>　　第三章 弧比弦算法的設計及改進</p><p

56、>　　3.1弧比弦算法的基本原理</p><p>　　弧比弦算法是曲線簡化算法中性能較好算法，它用兩點之間的弧長和相應的弦長的比值為標準來度量曲線上節(jié)點的重要性?；”认宜惴ǖ倪@個比值可以表示為：</p><p><b>　?。?）</b></p><p>　　對每一個節(jié)點，都有它自身的一個支撐域，節(jié)點的支撐域可以理解為一種范圍，即在不同的

57、范圍內(nèi)節(jié)點有不同的重要性。例如在中國全圖上，長沙很重要，但在全球地圖上，長沙的重要性也許就有所下降了，這個范圍即可以理解為支撐域。根據(jù)文獻[8],支撐域半徑R 的取值由曲線的總長度(L0) 和曲線的節(jié)點數(shù)V (其中端點除外)計算得到，其表達式為:</p><p><b>　?。?）</b></p><p>　　由式（6），稱為曲線上節(jié)點的弧比弦值（也譯為局部長度比），

58、圖10以第6點為例來說明，其弧的長度是兩部分的和，即A6和第6點的距離加上B6和第6點的距離。這里A6是的圓6（即點6的支撐域）和點5、點6連線段的交叉點。B6是的圓6和點6、點7連線段的交叉點。這種算法最初被Nakos和Mitropoulos發(fā)現(xiàn)，所以也稱為Nakos–Mitropoulos算法[8]。</p><p>　　圖10 Nakos–Mitropoulos算法</p><p>

59、　　Nako–Mitropoulos算法流程如下：</p><p>　　1、確定了支撐域的半徑值。</p><p><b>　　2、計算每個點的。</b></p><p>　　3、構建函數(shù)，并找到函數(shù)的極大值，以此最大值為關鍵點。</p><p>　　4、循環(huán)以上步驟2、3，直到選中的關鍵點個數(shù)滿足給定的閾值。</

60、p><p>　　本文采用Visual Studio 2008 C#.NET + Arc Engine 9.3二次開發(fā)來實現(xiàn)該算法的程序（具體見后面章節(jié)）。為了更好地對比算法，我采用兩條曲線作為實驗曲線，其一為91個點的一條點分布密度較大的曲線，其二為一條40個點分布密度較小的曲線，它們的坐標系均為WGS-84坐標系，如下圖：</p><p><b>　　圖11 原始曲線圖</b

61、></p><p>　　對實驗曲線1，用弧比弦算法進行曲線簡化，分別保留60、50、40、30個點，所得簡化結果見下圖：</p><p>　　圖12 用弧比弦算法簡化線目標</p><p>　　所得評價指標見下表：</p><p>　　表1 弧比弦算法保留點不同的評價指標</p><p>　　對實驗曲線2，用弧比

62、弦算法進行曲線簡化，分別保留35、30、25、20個點，所得簡化結果見下圖：</p><p>　　圖13 用弧比弦算法簡化線目標</p><p>　　所得評價指標如下表：</p><p>　　表2 弧比弦算法保留點不同的評價指標</p><p>　　由上述兩個實驗，我們可以看出弧比弦算法隨著保留點的逐漸減少而變形逐漸變大。在曲線節(jié)點密集的情況

63、下效果較好，而在曲線節(jié)點稀疏的情況下效果有所下降，并產(chǎn)生了明顯的自相交，如圖13（d）。由此，結合上文中曲線綜合算法的可能不足，發(fā)現(xiàn)弧比弦算法有以下三個不足：</p><p>　　1、算法精度有待提高；</p><p>　　2、可能產(chǎn)生連續(xù)的減點而使曲線有較大的變形；</p><p>　　3、生成的曲線可能產(chǎn)生自相交；</p><p>　　不

64、難看出弧比弦算法有自己的一些獨特的缺點。結合這些不足，下文中我將分兩步提出一種弧比弦算法的改進算法，對弧比弦算法進行一些改進，改善上述不足。</p><p>　　3.2弧比弦算法的改進</p><p>　　3.2.1增強支撐域的自適應性改進 </p><p>　　原弧比弦算法的支撐域R是整條曲線為相同的一個數(shù)值，這樣如果曲線的密度不均勻或者曲線太稀疏，很可能產(chǎn)生連續(xù)

65、的節(jié)點剔除而使曲線產(chǎn)生大的形變，因此曲線簡化效果不是很好。我們可以總結為算法的自適應性不強，所以下文中我將提出一種增加自適應性的改進。如圖14：</p><p>　　圖14 增強支撐域的自適應性改進</p><p>　　計算P3點的弧比弦度量值，用P3到P2的距離L3加上P3到P4的距離L4之和（即弧的長度之和）與P2與P4的距離L24（即弦的長度）之比，這樣就相當于其支撐域為過P2、P4

66、并且包含P3的一個圓，這樣就使得算法更具有自適應性，提高了其效能。具體算法如下：</p><p>　　1、從第二點到倒數(shù)第二點，計算每個點的改進弧比弦值，即一點的弧比弦值等于這點到相鄰兩點的弧長之和比上相鄰兩點間的弦長（端點除外）。</p><p>　　2、找出其中的最大值點</p><p>　　3、直到找到的點的數(shù)量滿足閾值為止</p><p&

67、gt;　　這樣就實現(xiàn)了算法的自適應性改進，對節(jié)點密度不均勻或節(jié)點較為稀疏的曲線有很好的效果，實驗依然采用上一章中的實驗曲線1和2，實驗結果圖如下，對于實驗曲線1：</p><p>　　圖15 增強支撐域的自適應性改進結果圖1</p><p><b>　　對于實驗曲線2：</b></p><p>　　圖16 增強支撐域的自適應性改進結果圖2<

68、;/p><p>　　對于實驗曲線1，其評價指標見下表：</p><p>　　表3 增強支撐域的自適應性改進評價結果表1</p><p>　　對于實驗曲線2，其評價指標見下表：</p><p>　　表4 增強支撐域的自適應性改進評價結果表2</p><p>　　由上述實驗結果可得到結論，改進算法相比原弧比弦算法，無論從直觀的

69、曲線簡化視覺效果，還是從算法的評價指標對比，效果都有明顯的提高。尤其是在曲線節(jié)點稀疏的情況下，效果較原始算法更好，并且可以有效避免產(chǎn)生曲線的自相交。</p><p>　　下面以第二條實驗曲線為例，對比兩種算法中每個節(jié)點的弧比弦值，如圖：</p><p>　　圖17 兩種算法的每個點的弧比弦值</p><p>　　對比發(fā)現(xiàn)，改進后的算法對一些較小的值進行了放大，例如3

70、點、25點、35點等，所以優(yōu)化了算法的效果，提升了算法的性能。</p><p>　　3.2.2 增強算法的迭代性更優(yōu)化其性能</p><p>　　線要素化簡的基本要求是：保持彎曲形狀或輪廓圖形的基本特征，即總的圖形的相似性；保持彎曲的特征轉折點的精確性；保持不同地段彎曲程度的對比。對4.2.1中弧比弦算法的改進，雖然優(yōu)化了其性能，但在計算機硬件快速發(fā)展的今天,這算法的運算量和速度已不是主要

71、問題?，F(xiàn)在所關心的關鍵是化簡前后線要素的形狀逼近程度以及是否存在錯誤(如自相交問題等)。所以我們可以采用迭代算法進一步提高算法的效率，因此我在這一節(jié)中我將提出最終的弧比弦改進算法如下：</p><p>　　1、從第二點到倒數(shù)第二點，計算每個點的改進弧比弦值（計算方法同4.2.1中的改進算法1），即：一點的弧比弦值等于這點到相鄰兩點的弧長之和比上相鄰兩點間的弦長（端點除外）。</p><p>

72、;　　2、找出其中值最小的點，將其從曲線中剔除并生成新曲線</p><p>　　3、對新的曲線再進行此算法。</p><p>　　4、直到曲線還有規(guī)定數(shù)量閾值的點為止。</p><p>　　這樣就實現(xiàn)了算法的迭代性，它可以有效的避免連續(xù)的節(jié)點剔除，使得曲線簡化的效果更好。實驗效果見下圖，對于曲線1：</p><p>　　圖18 增強算法的迭代

73、性改進算法2結果圖1</p><p><b>　　對于曲線2：</b></p><p>　　圖19 增強算法的迭代性改進算法2結果圖2</p><p>　　實驗的評價指標見下表，對于曲線1：</p><p>　　表5 增強算法的迭代性改進算法2評價結果表1</p><p><b>　　對

74、于曲線2：</b></p><p>　　表6 增強算法的迭代性改進算法2評價結果表2</p><p>　　由以上實驗圖示及評價指標表可見，改進算法經(jīng)過迭代后效果明顯改善，得到的曲線更加吻合原始曲線，并且有效的改善了可能連續(xù)剔除節(jié)點帶來的曲線大的變形，尤其在剔除節(jié)點較多的情況下，這種改善更為明顯。</p><p><b>　　3.3本章小結<

75、;/b></p><p>　　本章首先介紹了弧比弦算法的基本原理，然后指出它的一些不足，并針對這些不足對弧比弦算法進行了兩次改進，得到了一種新的具有自適應性的迭代弧比弦算法。得到的改進算法可以有效的提高算法的性能，并且很好的解決了弧比弦算法的三個不足：即改善了算法的性能；有效的減少了生成曲線的自相交可能性；并且最大程度的抑制了可能的連續(xù)節(jié)點剔除，使得生成的曲線更加吻合原始曲線，算法的效果得到了明顯改善。&l

76、t;/p><p>　　但是算法改進的不足之處是尚未能解決弧比弦算法的最后一個缺點，即保留的節(jié)點并不一定對曲線的表達是必須的。這個問題涉及到曲線上節(jié)點的信息量的問題，我會在以后的研究中繼續(xù)就這個問題進一步優(yōu)化我的算法，達到更好的曲線簡化效果。</p><p>　　第四章 在Visual Studio 2008平臺上用Arc Engine 9.3二次開發(fā)實現(xiàn)算法</p><p&

77、gt;<b>　　4.1開發(fā)平臺介紹</b></p><p>　　我的整個算法程序開發(fā)采用Visual Studio 2008 C#.NET平臺，在其之上使用ESRI公司的Arc Engine 9.3開發(fā)包進行二次開發(fā)，下面分別介紹之：</p><p>　　4.1.1、Arc Engine 9.3介紹[14]</p><p>　　Arc Eng

78、ine是基于核心組件庫Arc Objects搭建的。Arc Objects組件庫有3000多個對象可供開發(fā)人員調(diào)用，為開發(fā)人員集成了大量的GIS功能，可以快速的幫助開發(fā)人員進行GIS項目的開發(fā)。ArcGIS可以在多種編程環(huán)境中進行開發(fā)，其中包括：C++、支持COM的編程語言、.NET、Java等。</p><p>　　2004年，美國ESRI發(fā)布Arc Engine 9.3，Arc Engine 9.3具有簡潔、

79、靈活、易用、可移植性強等特點。Arc Engine開發(fā)包提供了一系列可以在ArcGIS Desktop框架之外使用的GIS組件，Arc Engine 9.3的出現(xiàn)對于需要使用Arc Objects的開發(fā)人員來說是個福音，因為Arc Engine 9.3發(fā)布之前，基于Arc Objects的開發(fā)只能在龐大的ArcGIS Desktop框架下進行。</p><p>　　4.1.2、Visual Studio 2008

80、 C#.NET介紹[15]</p><p>　　C#是一種程序開發(fā)語言，它在.NET平臺上開發(fā)，.NET平臺上支持用C#或者VB進行開發(fā)。另外，C#不但可以開發(fā)基于.NET的應用程序，也可以開發(fā)基于WinForm的程序，而用Arc Engine9.3進行的二次開發(fā)就是基于WinForm的程序開發(fā)。</p><p>　　C#（讀做C-sharp）編程語言是由微軟公司的Anders Hejls

81、berg和 Scott Willamette領導的開發(fā)小組專門為.NET平臺設計的語言。C#是事件驅動的、完全面向對象的可視化編程語言，我們可以使用集成開發(fā)環(huán)境IDE來編寫C#程序。使用IDE后，程序員可以方便的建立，運行，測試和調(diào)試C#程序。</p><p><b>　　4.2算法的實現(xiàn)</b></p><p>　　我的程序的主界面如圖20，它繼承了ArcGIS的簡

82、潔易用的特點：</p><p><b>　　圖20 程序主界面</b></p><p>　　我的整個程序有一個主窗體MainForm以及四個類，四個類分別是實現(xiàn)弧比弦算法的CArcDivideDistance類，實現(xiàn)自適應改進算法的CNewArcDDistance類，實現(xiàn)迭代的自適應改進算法的CNewDDis1類，以及實現(xiàn)算法評價的CEvalution類，它們分別實現(xiàn)

83、三種算法以及對其評價的工作。</p><p>　　4.2.1、MainForm窗體</p><p>　　MainForm窗體采用Arc Engine 9.3插件式開發(fā)，保留了ArcGIS的基本界面風格，在其中主要實現(xiàn)了圖層的讀取以、進行算法以及圖形的現(xiàn)實等功能。</p><p>　　圖層的讀取分為點圖層、線圖層和面圖層，代碼的框架如下（示例為讀取線圖層）：</

84、p><p>　　圖層的顯示也分為點圖層、線圖層和面圖層，代碼的框架如下（示例為讀取線圖層）：</p><p>　　實現(xiàn)一個曲線簡化算法并評價有三個類似的函數(shù)，分別實現(xiàn)三種算法。下面以改進算法2為例展示，即迭代自適應弧比弦改進算法，程序實現(xiàn)點線的讀取，循環(huán)減點，顯示新的線并評價其算法，代碼示例如下：</p><p><b>　　接上頁：</b><

85、;/p><p>　　4.2.2、CArcDivideDistance類</p><p>　　CArcDivideDistance類為進行一次弧比弦算法，具體算法思路已經(jīng)在前文中說明，這里只給出代碼的簡要框架如下：</p><p>　　4.2.3、CNewArcDDistance類</p><p>　　CNewArcDDistance類為進行一次自

86、適應的改進算法，具體算法思路前文中已經(jīng)說明，這里只給出代碼的簡要框架如下：</p><p>　　4.2.4、CNewDDis1類</p><p>　　CNewDDis1類為進行一次迭代的自適應改進算法，具體算法思路上一章已經(jīng)說明，這里只給出代碼的簡要框架如下：</p><p>　　4.2.5、CEvalution類</p><p>　　CEv

87、alution類進行算法的評價，具體算法為分別計算新曲線和原始曲線的偏移量平均值，偏移量中值和面積變形值，下面給出代碼的簡要框架如下：</p><p><b>　　4.3 本章小結</b></p><p>　　本章中先介紹了程序的開發(fā)環(huán)境，分別對Visual Studio 2008 C#.NET平臺，及ESRI公司的Arc Engine 9.3開發(fā)包進行了介紹，然后闡

88、述程序整體的設計思路，介紹了程序的構架，給出程序中的相關類的介紹。然后分別就幾個不同功能的類闡述了程序的主體框架，最后分別給出了程序的主體結構代碼。</p><p><b>　　第五章 總結及展望</b></p><p>　　在曲線簡化中,曲線上各節(jié)點的重要性度量是一個基礎性工作,亦是節(jié)點選取的標準。本文通過分析現(xiàn)有的線目標綜合方法,提出了一種改進的弧比弦算法。該方法

89、綜合采用了自適應的支撐域定義方式及迭代的計算方式，改善了算法的性能；有效的減少了生成曲線的自相交可能；最大程度的減少了可能的連續(xù)節(jié)點剔除，使得生成的曲線與原始曲線更加附合，算法效果的到了明顯改進。</p><p>　　通過實驗例證和評價指標比較分析發(fā)現(xiàn),在曲線簡化過程中,利用改進后的弧比弦算法選取的節(jié)點相比于原始方法能夠更好地保持原始曲線的輪廓,一方面減少了點的數(shù)據(jù)量,另一方面也較好地保持了原始曲線的形狀(即引起

90、較小的曲線偏移) ,實現(xiàn)了曲線簡化的雙重目的。</p><p>　　但是算法改進的不足之處是尚未能解決保留的節(jié)點并不一定對曲線的表達是必需的。這個問題涉及到曲線上節(jié)點的信息量的問題,如何度量簡化前、后曲線之間的信息量并作為度量指標分析節(jié)點的重要性,是我未來的研究方向及重點。</p><p>　　目前，信息度量問題的研究還處于起步階段，有許多問題有待進一步的研究。此外，信息論在地理信息科學領

91、域有著廣闊的應用前景，隨著本文研究的深入開展，還有許多問題值得思考和研究，具體包括：</p><p>　　1、選取實際地圖中的一條河流，分別運用經(jīng)典算法，如Douglas-Peucker算法、間接法綜合算法、直接法綜合算法等綜合算法對其進行地圖綜合，并且對比本文中的改進算法，得出一個最優(yōu)的曲線綜合算法。</p><p>　　2、本文討論了單個線目標的空間綜合，下一步要擴展到多個線目標的空間

92、綜合，直到整個地圖的空間綜合。</p><p>　　3、深入研究信息論的編碼和譯碼理論，提出基于信息論的地圖綜合算法。從信息量的角度出發(fā)選取關鍵點。</p><p><b>　　主要參考文獻</b></p><p>　　LI Z L. Some observations on the issue of line generalization [

93、J].The Cartographic Journal, 1993, 30 (1): 68 - 71.</p><p>　　LI Z L. Algorithmic Foundation of Multi-Scale Spatial Representation [M]. CRC Press, 2007.</p><p>　　ATTNEAVE F. Some informational as

94、pects of visual perception [J]. Psychological Review, 1954, 61 (3):183 - 193.</p><p>　　MCMASTER R B. A statistical analysis of mathematical measures for line simplification [J]. The American Cartographer, 19

95、86, 13:103 - 116.</p><p>　　MCMASTER R B. Automated line generalization [J]. Cartographica, 1987, 24 (2):74 - 111.</p><p>　　LI Z L. An examination of algorithms for detection of critical points o

96、n digital lines [J]. The Cartographic Journal, 1995, 32 (2):121 - 125.</p><p>　　VISVALINGHAM M, WHYATT J. Line generalization by repeated elimination of points [J]. The Cartographic Journal, 1993, 30 (1):46

97、- 51.</p><p>　　NA KOS B, MITROPOULOS V. Local length ratio as a measure of critical point detection for line simplification [A]. Symposium of the 5th ICA Workshop on progress in Automated Map Generalization,

98、 2003.</p><p>　　TEH C H, CHIN R T. On the detection of dominant points on digital curves [J].IEEE Transactions on pattern Analysis and Machine Intelligence ,2004 ,11 (8) :859 - 872.</p><p>　　Dou

99、glas, D. H. and Peucker, T. K., Algorithms for the reduction of the number of points required to represent a digitized line or its caricature [J] .Canadian Cartographer, 10(2), 112–122, 1973.</p><p>　　鄧敏, 陳杰

100、, 李志林, 徐震. 曲線簡化中節(jié)點重要性度量方法比較及垂比弦法的改進[J]. 地理與地理信息科學, 2009, 25(1): 40-43.</p><p>　　賈奮勵 電子地圖綜合的理論與方法的研究[J] 解放軍信息工程大學碩士論文 2002.4 (1):1 – 5.</p><p>　　WHITE E. Assessment of line generalization algorit

101、hms using characteristics points [J]. The American Cartographer, 1985, 12 (1):17 - 27.</p><p>　　ESRI(中國)培訓中心. Arc Engine輕松入門[M] . ESRI(中國)出版社 ,2009,5(1) :1 - 10.</p><p>　　Herbert Schildt. C#2.0參

102、考完全手冊（第二版）[M] . 清華大學出版社 ,2007.5(1) :8 - 14.</p><p><b>　　致謝</b></p><p>　　行文至此，腦中閃過的已不是字母與數(shù)字，而是那些感人至深的話語和情景。回想自己從對地圖綜合的無知到這這篇文章的完成，這期間蘊含著多少人殷切的希望和無私的教導。而我只能用這一本論文和笨拙的筆觸表達我深深的謝意。</p&

103、gt;<p>　　師從鄧敏教授是我一生的幸運。幾個月來，鄧敏教授以極大的熱忱和耐心教會我探索問題的方法和解決問題的思路，使我能夠置身于一個廣闊的GIS世界。導師的言傳身教使我體會到做學問與做人一樣，需要踏踏實實的精神、老老實實的態(tài)度和精益求精的作風。而此時使我不安的是多少次聞其言卻不能會其意的笨拙。往事種種，我只能真心地說一句:“謝謝!”</p><p>　　感謝徐震碩士在問題研究中所給予的耐心教導