基于漸進迭代逼近的矢量地圖曲線化簡方法

周 晨，陳 偉,2，劉 淵,2

基于漸進迭代逼近的矢量地圖曲線化簡方法

周 晨1，陳 偉1,2，劉 淵1,2

(1. 江南大學人工智能與計算機學院，江蘇 無錫 214122； 2.江蘇省媒體設計與軟件技術重點實驗室(江南大學)，江蘇 無錫 214122)

矢量地圖化簡在地形仿真、制圖綜合等研究中具有重要應用。針對已有算法難以兼顧化簡曲線的整體形態(tài)和局部特征點精度的問題，提出一種基于B樣條曲線漸進迭代逼近(PIA)的矢量地圖曲線化簡方法。首先篩選出能保持曲線輪廓、具有最大信息量的特征點列，將其作為初始控制點列，得到相應的非均勻3次B樣條擬合曲線；然后根據擬合曲線與特征點的誤差進行迭代調整控制點，逐步得到一系列逼近曲線，直至最終滿足精度要求。實驗表明，PIA方法不僅保持了化簡曲線的整體幾何形態(tài)，而且能在滿足全局誤差要求的情況下，實現特征點處的高精度逼近。

地圖綜合；曲線；樣條；漸進迭代逼近；化簡

在地理信息系統(tǒng)(geographic information system，GIS)中，地圖要素按照其對應地圖符號的幾何屬性可以分為點、線、面3類，其中線狀要素所占比例最大，如地形等高線、區(qū)域分界線、道路、河系等多種類型。對于面狀要素，比如湖泊、島嶼、植被、居民地、行政區(qū)等，在內部勻質的情況下，人們也往往更關注其外圍輪廓線[1]。在GIS矢量空間數據中，一條曲線是經過數字化采樣得到一個有序點列，線狀要素具有數據量大、形態(tài)復雜的特點。根據地圖制圖學的要求，曲線化簡是在盡量保持曲線關鍵位置精度及幾何形態(tài)結構的前提下，盡可能多地剔除曲線上冗余或次要的點，以達到減少數據量及適應小比例尺地圖顯示的需求[2]。因此，位置精度和形態(tài)結構保持是矢量地圖曲線化簡中需要考慮的重要因素。所謂關鍵位置，是指曲線上能夠反映地理特性的點或有特殊含義的地理位置，幾何上一般對應為曲線上的特征點。

矢量地圖曲線化簡是地圖自動綜合領域的研究熱點，也是地圖學與地理信息科學界公認的一個難題[1]。國內外學者提出了多種不同的矢量曲線化簡方法，主要歸納為2類：基于空間幾何化簡的算法和基于頻域濾波的算法。

基于空間幾何化簡算法中，絕大部分通過對曲線上點的取舍使曲線得到簡化，同時保持曲線的整體形態(tài)。1973年，DOUGLAS和PEUCKER[3]提出的一種矢量地圖數據的折線簡化法，即DP算法，具有保留最大信息量點的特征[4]。幾乎同時，RAMER[5]于1972年、DUDA和HART[6]于1973年分別獨立提出同樣的算法。另外，也有文獻提出基于曲線上彎曲結構的取舍的化簡算法[7-9]，但目前在彎曲的定義與處理上還不能協(xié)調一致[4]。文獻[10]對常見的化簡算法進行性能比較后發(fā)現，DP算法具有最優(yōu)的整體形態(tài)和關鍵點保持能力，不足之處是不能得到光滑彎曲的化簡曲線，給人以生硬的視覺效果。

而基于頻域濾波的曲線化簡算法，是將原始曲線經Fourier和小波變換等操作，在頻域空間中保留曲線的重要特征系數，再通過反變換得到化簡后的曲線。文獻[11-12]將閉型地圖曲線經Fourier變換轉換到頻率空間，從而實現了從粗糙到精細地重構原始曲線。為了兼容開型地圖曲線的化簡，文獻中首先對原始曲線作鏡像對稱復制，得到封閉曲線后再作Fourier變換。文獻[12-17]將小波分析理論應用到地圖矢量曲線的化簡及壓縮中。需要指出的是，雖然小波具有多分辨率分析的內在屬性，可以生成信號的多尺度表達模型。但是在地圖曲線化簡的特定應用中，曲線上的特征點一般具有特殊含義，在對原始曲線化簡或壓縮過程中，要求這些點不產生移位，即保證這些位置處的擬合精度[11]。而根據時頻變換理論可知，將地圖曲線經時頻變換后，空間特征點的信息已經被散播在各頻段系數中，若要精確重構特征點位置，則需大量增加頻域重構項數，而這又與曲線化簡的目標發(fā)生內在矛盾。文獻[13-14]通過多種后處理的方法進行特征點誤差修正，但同時又帶來算法復雜，適應性不強等問題。

綜上所述，在地圖矢量曲線化簡問題中，已有方法很難兼顧化簡結果的全局形態(tài)與局部精度。因此，可將地圖矢量曲線的化簡看作一個B樣條曲線擬合問題，引入近年來在計算機輔助設計(computer aided geometric design，CAGD)領域流行的漸進迭代逼近方法，使化簡曲線既能保持原始地圖曲線的整體形態(tài)，又能滿足局部擬合精度的要求。

1 相關工作

1.1 Douglas-Peucker(DP)算法

DP算法是比較經典且廣為引用的算法，本文對該算法做簡要介紹。

對于開型曲線(圖1)，起點0和終點P為地理目標的起訖點，其具有重要的地理意義和結構意義，因此是不可移動的特征點。首先將0和P連成直線段，其是該曲線的極限化簡狀態(tài)。計算所有中間點到該直線段的距離，找到最大距離max對應的點P，其對于確保曲線的特征有不可替代的重要性。也就是說，相比其他中間點而言，保留P將使曲線變形最小。

圖1 Douglas-Peucker算法

若max小于預設限差，則該曲線用該段基線代替；否則，P作為新的特征點將原曲線作進一步的劃分，直到所有子曲線段的最大偏移量均小于為止。將保留下來的所有特征點按序連成折線即為最終的化簡結果。通過DP算法保留下來的特征點，均是為確保相應子曲線段的輪廓特征具有最大貢獻的點，這是DP算法具有最大信息量的主要原因，從而被廣泛地應用[18-22]。

對于閉型曲線，首先用恰當的方法對其一分為二，然后再分別用上述算法進行化簡，不再贅述。

1.2 漸進迭代逼近(PIA)算法

漸進迭代逼近(progressive-iterative approximation，PIA)，又稱為幾何迭代法，是一種具有明顯幾何意義的曲線曲面逼近方法。從一條初始混合曲線開始，迭代地調整其控制頂點位置，即可使這條曲線收斂到一條插值給定數據點列的曲線。PIA方法肇始于1975年由齊東旭等[23]提出的均勻3次B樣條曲線擬合的盈虧修正算法；1979年，DE BOOR[24]也獨立提出了這一算法；近年來，國內學者對PIA方法做了深入的理論推廣及廣泛地應用研究[25-29]。

本文對插值型PIA方法做簡要介紹。

給定空間中的一個有序型值點列{Q，=0,1,···,}，其中每個型值點Q賦予一個參數值{t，=0,1,···,}，滿足

以該型值點列為初始控制多邊形頂點，構造一組初始混合曲線

為了生成第+1次迭代后的曲線，首先計算每個型值點Q與(k)()上對應參數點的差向量

然后，將()加到曲線(k)()的相應的控制頂點上，得到第+1次迭代生成曲線的控制頂點

從而得到第+1次迭代后生成的曲線

由此可見，這個迭代過程將產生一個曲線序列

文獻[25]證明了，只要調配基函數是全正基函數，那么這個曲線序列就收斂到一條插值給定型值點列{Q，=0,1,···,}的曲線，即

需要指出的是，雖然選擇3次非均勻B樣條基函數作為調配基函數，從理論上保證了曲線序列收斂到型值點列。但是在地圖曲線化簡應用中，并不過分強調化簡曲線的插值性。實驗結果表明，一般情況下，只需作較少次數迭代(3次左右)即可滿足實際化簡要求，與PIA方法在某些高精度曲線逼近應用領域(如等距線逼近、工業(yè)產品設計等)具有不同之處。

2 矢量地圖曲線化簡的PIA方法

以DP算法獲取的地圖曲線特征點為基礎，通過引入B樣條曲線擬合中的漸進迭代逼近方法，得到一種兼顧全局形態(tài)與局部精度的曲線化簡方法。

設原始矢量地圖曲線由有序點列{P，=0,1,···,}組成，當0=時為閉型曲線，如等高線、區(qū)域輪廓線等地圖實體；否則，當0≠時為開型曲線，如河流、道路等地圖實體。在運用PIA方法之前，首先需要從原始曲線點列中提取特征點，能較好地反映原始曲線的形狀信息。盡管在CAGD領域中已提出多種方法用于數字曲線特征點的檢測及提取[30-31]，一般可通過計算數字曲線上各點處的曲率來判斷其重要性，從而篩選出特征點。但是在數字地圖領域，地圖曲線具有復雜程度高、在多個尺度上具有振蕩性的特點。因此，基于局部信息的曲率估計方法很難有效地提取地圖曲線上的特征點。如前所述，DP算法在數字地圖綜合領域具有持久的生命力，一個重要的原因是其能夠有效篩選出各種地形曲線的特征點。因此，本文將利用DP算法獲取地圖曲線上的特征點。

當0=Q時，取延拓型值點-1=Q1，Q1=1；當0≠Q時，取延拓型值點-1=0，Q1=Q。于是得到以{Q，=-1,0,1,···,+1}為控制點的3次非均勻B樣條初始曲線

其中，B()為3次非均勻B樣條基函數。

一般說來，由式(8)得到的初始曲線(0)()能夠刻畫出原地圖曲線的整體形態(tài)。但由于{Q，=0,1,···,}為原曲線的特征點，往往位于曲線變化比較大的地方，此時初始曲線(0)()與型值的誤差較大。為了保持特征點在地圖曲線化簡過程中的精度，運用漸進迭代逼近方法，通過有限次迭代，得到新的3次非均勻B樣條曲線

當滿足逼近精度要求時，(k)()即可作為最終的化簡曲線。關于迭代次數與逼近誤差的關系，將在下節(jié)內容中討論。

3 實驗與分析

3.1 實驗1：地圖曲線化簡

實驗采用圖2(a)所示的一條由1 577個點構成的地圖曲線數據，圖2(b)為通過DP算法得到的包含85個特征點({Q，=0,1,···,84}，其中0=84)的化簡曲線?？梢钥闯?，DP算法結果保留了曲線的特征點，一定程度上保持了原曲線的形狀，但未經光滑處理，看上去比較生硬。

圖3為分別通過Fourier變換和小波變換得到的化簡結果。圖4分別為彎曲取舍[32-33]和Li-Openshaw算法[34-35]的化簡結果。通過Fourier和小波變換得到曲線較為光滑。但化簡曲線在某些特征點的誤差較大，即產生特征位移現象。而彎曲取舍和Li-Openshaw算法得到的曲線可以保持曲線輪廓的基本特征，但光滑度較差并不能保證化簡曲線在特征點處的精度。

圖5為PIA方法在不同迭代次數(0次、1次、3次及5次)得到的化簡曲線?？芍?次B樣條曲線進行擬合時，其可以反映出原始曲線的整體形態(tài)且具有良好的光滑性，但對于特征點的保持能力較差。但通過PIA方法很少的迭代次數，擬合曲線就會逼近特征點，當迭代次數達到5次時，對應的3次B樣條曲線(5)()非常接近特征點，幾乎達到插值的效果。

圖2 地圖曲線及其DP算法化簡結果((a)原始曲線(1 577個點)；(b)化簡曲線(85個點))

為定量分析特征點的逼近誤差，定義化簡曲線在特征點Q處的逼近誤差為

圖3 基于Fourier變換或小波變換(db4)的化簡結果及局部放大((a) Fourier重構(50項)；(b) Fourier重構(100項)；(c)小波重構(56項)；(d)小波重構(105項))

Fig. 3 Simplification result and local magnification based on Fourier or wavelet transform (db4) ((a)Reconstruction of Fourier (50 items); (b) Reconstruction of Fourier (100 items); (c) Reconstruction of wavelet (56 items); (d) Reconstruction of wavelet (105 items) )

圖4 基于彎曲取舍或Li-Openshaw算法的化簡結果及其局部放大((a)彎曲取舍(70個點)；(b)彎曲取舍(192個點)；(c) Li-Openshaw(54個點)；(d) Li-Openshaw (90個點))

圖5 基于PIA方法的化簡結果及其局部放大((a)迭代0次；(b)迭代1次；(c)迭代3次；(d)迭代5次)

分別計算以下3種誤差：

(1) 平均誤差為

(2) 最大誤差為

(3) 標準差為

表1列出了上述化簡方法特征點處的誤差數據。可以看出，PIA方法在提高化簡曲線在特征點處的精度是有效的。每迭代1次，便可使逼近精度大幅提高，同時保持了化簡曲線的整體形態(tài)。但隨著迭代次數的增加，逼近誤差明顯減小，且特征點數目始終保持不變。在濾波、彎曲取舍及Li-Openshaw方法中，若要減小其誤差，則必須增加重構系數或綜合后點的數量，與地圖曲線化簡的初衷有內在矛盾。

此外，表2分別計算了在已知特征點的情況下，PIA方法及傳統(tǒng)方法對圖2所示等高線化簡所需時間結果(相同環(huán)境下運行1 000次取平均值)。

3.2 實驗2：PIA迭代次數及全局誤差分析

為進一步分析PIA迭代次數對化簡曲線局部及全局誤差的關系，選擇典型的116條等高線數據作化簡實驗。表3顯示了6條等高線及其相應的化簡結果，可以看出，PIA方法能夠得到保持原等高線整體形態(tài)的光滑曲線。接下來將定量分析使用PIA方法所得化簡曲線的局部及全局誤差。

表1 不同方法的逼近誤差(×0.01)

表2 不同化簡算法重構所需時間(ms)

表3 116條等高線中6條等高線及PIA方法化簡結果

首先計算PIA方法在不同迭代次數(1～10次)下全部等高線化簡結果在特征點處的平均誤差(表4)。可以看出，隨著迭代次數的增加，化簡曲線在特征點處的誤差逐漸減小，其局部保持能力不斷增強。圖6為迭代次數與誤差之間的關系?？梢钥闯?，3次迭代后特征點的各逼近誤差僅為初始誤差的10%左右，繼續(xù)增加迭代次數，誤差將繼續(xù)減少。因此，在實際化簡應用中，若無特殊要求，迭代次數設為3次即可，或根據精度要求選擇迭代次數。

進一步計算化簡曲線的全局誤差，定義平均全局誤差為

圖7為116條等高線分別利用5種方法得到化簡曲線的全局平均誤差?？梢钥闯?，利用PIA方法得到的所有化簡曲線的全局平均誤差中，僅有2條略大于小波變換，其余均小于其他方法。因此，PIA方法在保證局部特征點精度的前提下，并未犧牲化簡曲線的全局精度。

表4 116條等高線在PIA方法各迭代次數下的誤差(×0.01)

圖6 PIA方法迭代次數與誤差的關系

圖7 等高線化簡曲線的平均全局誤差

4 結 論

本文將漸進迭代逼近理論首次引入到地圖曲線化簡領域。針對地圖曲線化簡的應用需求，本文提出的算法和實驗結果表明，漸進迭代逼近理論能夠有效地解決化簡曲線的整體幾何形態(tài)和局部特征精度之間的矛盾。

作為一項探索性研究工作，為了將本文提出的方法有效應用到地圖數據的表達、分析及處理中，仍有許多問題需要解決。包括海量地圖數據的高效處理、地圖曲線的拓撲結構保持等問題，尚需進行更深入理論及應用研究。

[1] 閆浩文, 王家耀. 地圖群(組)目標描述與自動綜合[M]. 北京: 科學出版社, 2009: 1-37.

YAN H W, WANG J Y. Target description and automatic synthesis of map groups (groups)[M]. Beijing: Science Press, 2009: 1-37 (in Chinese).

[2] 王家耀, 李志林, 武芳. 數字地圖綜合進展[M]. 北京: 科學出版社, 2011: 12-21.

WANG J Y, LI Z L, WU F. Advances in digital map generalization[M]. Beijing: Science Press, 2011: 12-21 (in Chinese).

[3] DOUGLAS D H, PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122.

[4] 毋河海. GIS與地圖信息綜合基本模型與算法[M]. 武漢: 武漢大學出版社, 2012: 431-442.

WU H H. Basic models and algorithms in GIS and map generalization[M]. Wuhan: Wuhan University Press, 2012: 431-442 (in Chinese).

[5] RAMER U. An iterative procedure for the polygonal approximation of plane curves[J]. Computer Graphics and Image Processing, 1972, 1(3): 244-256.

[6] DUDA R, HART P. Pattern classification and scene analysis[M]. New York: John Wiley & Sons, 1973: 462-463.

[7] 毋河海. 數字曲線拐點的自動確定[J]. 武漢大學學報·信息科學版, 2003, 28(3): 330-335.

WU H H. Automatic determination of inflection point and its applications[J]. Geomatics and Information Science of Wuhan University, 2003, 28(3): 330-335 (in Chinese).

[8] 郭慶勝, 黃遠林, 章莉萍. 曲線的彎曲識別方法研究[J]. 武漢大學學報·信息科學版, 2008, 33(6): 596-599.

GUO Q S, HUANG Y L, ZHANG L P. The method of curve bend recognition[J]. Geomatics and Information Science of Wuhan University, 2008, 33(6): 596-599 (in Chinese).

[9] 杜佳威, 武芳, 李靖涵, 等. 采用多元彎曲組劃分的線要素化簡方法[J]. 計算機輔助設計與圖形學學報, 2017, 29(12): 2189-2196.

DU J W, WU F, LI J H, et al. Line simplification method based on multi-bends groups division[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(12): 2189-2196 (in Chinese).

[10] 鄧敏, 樊子德, 劉慧敏. 層次信息量的線要素化簡算法評價研究[J]. 測繪學報, 2013, 42(5): 767-773, 781.

DENG M, FAN Z D, LIU H M. Performance evaluation of line simplification algorithms based on hierarchical information content[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(5): 767-773, 781 (in Chinese).

[11] LIU P C, LI X G, LIU W B, et al. Fourier-based multi-scale representation and progressive transmission of cartographic curves on the internet[J]. Cartography and Geographic Information Science, 2016, 43(5): 454-468.

[12] IOUP J W, GENDRON M L, LOHRENZ M C. Vector map data compression with wavelets[J]. Journal of Navigation, 2000, 53(3): 437-449.

[13] 朱長青, 王玉海, 李清泉, 等. 基于小波分析的等高線數據壓縮模型[J]. 中國圖象圖形學報, 2004, 9(7): 841-845.

ZHU C Q, WANG Y H, LI Q Q, et al. A model to compress contour data based on wavelet analysis[J]. Journal of Image and Graphics, 2004, 9(7): 841-845 (in Chinese).

[14] 馬伯寧, 冷志光, 湯曉安, 等. 具有誤差修正的線矢量數據小波變換[J]. 計算機輔助設計與圖形學學報, 2011, 23(11): 1825-1829, 1837.

MA B N, LENG Z G, TANG X A, et al. Wavelet transform with error correction for line vector data[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(11): 1825-1829, 1837 (in Chinese).

[15] SAUX E. B-spline functions and wavelets for cartographic line generalization[J]. Cartography and Geographic Information Science, 2003, 30(1): 33-50.

[16] 吳紀桃, 王橋. 小波分析在GIS線狀數據圖形簡化中的應用研究[J]. 測繪學報, 2000, 29(1): 71-75.

WU J T, WANG Q. A study on automatic cartographic generalization using wavelet analysis in GIS[J]. Acta Geodaetica et Cartographic Sinica, 2000, 29(1): 71-75 (in Chinese).

[17] 陳偉, 齊東旭. 基于Franklin函數的數字曲線多邊形逼近[J]. 計算機輔助設計與圖形學學報, 2013, 25(7): 980-987.

CHEN W, QI D X. Polygonal approximation of digital curves based on franklin function[J]. Journal of Computer-Aided Design & Computer Graphics, 2013, 25(7): 980-987 (in Chinese).

[18] PALLERO J L G. Robust line simplification on the plane[J]. Computers & Geosciences, 2013, 61: 152-159.

[19] LIU J X, LI H H, YANG Z L, et al. Adaptive Douglas-peucker algorithm with automatic thresholding for AIS-based vessel trajectory compression[J]. IEEE Access, 2019, 7: 150677-150692.

[20] ZHANG S K, LIU Z J, CAI Y, et al. AIS trajectories simplification and threshold determination[J]. Journal of Navigation, 2016, 69(4): 729-744.

[21] ZAREI R, HE J, SIULY S, et al. Exploring Douglas-peucker algorithm in the detection of epileptic seizure from multicategory EEG signals[J]. BioMed Research International, 2019, 2019: 5173589.

[22] ZHAO L B, SHI G Y. A method for simplifying ship trajectory based on improved Douglas-Peucker algorithm[J]. Ocean Engineering, 2018, 166: 37-46.

[23] 齊東旭, 田自賢, 張玉心, 等. 曲線擬合的數值磨光方法[J].數學學報, 1975, 18(3): 173-184.

QI D X, TIAN Z X, ZHANG Y X, et al. Numerical polishing method for curve fitting[J]. Acta Mathematica Sinica, 1975, 18(3): 173-184 (in Chinese).

[24] DE BOOR C. How does agee’s smoothing method work: 79-3[R]. Washingdon D C: Army Research Office, 1979: 299-302.

[25] LIN H W, BAO H J, WANG G J. Totally positive bases and progressive iteration approximation[J]. Computers & Mathematics with Applications, 2005, 50(3-4): 575-586.

[26] 藺宏偉. 幾何迭代法及其應用綜述[J]. 計算機輔助設計與圖形學學報, 2015, 27(4): 582-589.

LIN H W. Survey on geometric iterative methods with applications[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(4): 582-589 (in Chinese).

[27] LIN H W, MAEKAWA T, DENG C Y. Survey on geometric iterative methods and their applications[J]. Computer-Aided Design, 2018, 95: 40-51.

[28] 鄧少輝, 汪國昭. 漸進迭代逼近方法的數值分析[J]. 計算機輔助設計與圖形學學報, 2012, 24(7): 879-884.

DENG S H, WANG G Z. Numerical analysis of the progressive iterative approximation method[J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(7): 879-884 (in Chinese).

[29] DENG C Y, LIN H W. Progressive and iterative approximation for least squares B-spline curve and surface fitting[J]. Computer-Aided Design, 2014, 47: 32-44.

[30] LIU G H, WONG Y S, ZHANG Y F, et al. Adaptive fairing of digitized point data with discrete curvature[J]. Computer-Aided Design, 2002, 34(4): 309-320.

[31] PARK H, LEE J H. B-spline curve fitting based on adaptive curve refinement using dominant points[J]. Computer-Aided Design, 2007, 39(6): 439-451.

[32] 羅廣祥, 祝國瑞, 毋河海, 等. 坐標單調性分析下地圖曲線彎曲識別模型的研究[J]. 測繪通報, 2005(10): 21-24.

LUO G X, ZHU G R, WU H H, et al. The study of the model of identifying bends for cartographic linear features based on analysing coordinate monotony[J]. Bulletin of Surveying and Mapping, 2005(10): 21-24 (in Chinese).

[33] 黃博華, 武芳, 翟仁健, 等. 保持彎曲特征的線要素化簡算法[J]. 測繪科學技術學報, 2014, 31(5): 533-537.

HUANG B H, WU F, ZHAI R J, et al. The line feature simplification algorithm preserving curve bend feature[J]. Journal of Geomatics Science and Technology, 2014, 31(5): 533-537 (in Chinese).

[34] LI Z L, OPENSHAW S. 基于客觀綜合自然規(guī)律的線狀要素自動綜合的算法[J]. 武測譯文, 1994, (1): 49-58.

LI Z L, OPENSHAW S. Linear feature’s self-adapted generalization algorithm based on impersonality generalized natural law[J]. Translation of Wuhan Technical University of Surveying and Mapping, 1994, (1): 49-58 (in Chinese).

[35] 朱鯤鵬, 武芳, 王輝連, 等. Li-Openshaw算法的改進與評價[J]. 測繪學報, 2007, 36(4): 450-456.

ZHU K P, WU F, WANG H L, et al. Improvement and assessment of Li-openshaw algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4): 450-456 (in Chinese).

Vector map curve simplification algorithm based on progressive-iterative approximation

ZHOU Chen1, CHEN Wei1,2, LIU Yuan1,2

(1. School of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi Jiangsu 214122, China; 2. Jiangsu Key Laboratory of Media Design and Software Technology, Jiangnan University, Wuxi Jiangsu 214122, China)

Vector map simplification plays an important role in the research on terrain simulation, cartographic generalization, and so on. As it is difficult to balance the overall shape and local feature point accuracy of the simplified curve with the existing algorithms, a vector map simplification method based on progressive iterative approximation (PIA) with B-spline curve was proposed. First, select the feature point sequence that can maintain the contour of the curve with the largest amount of information, and use it as the initial control point sequence to obtain the corresponding nonuniform cubic B-spline curve. Secondly, it obtained a series of curves that were gradually fitting the real one by iteratively adjusting the control points according to the bias between the fitted curve and the feature points until the accuracy requirements were met. The experiments result show that the PIA method can not only keep the overall geometry of the map curve, but also achieve high-precision approximation at feature points while meeting the global bias requirements.

map synthesis; curve; spline; progressive-iterative approximation; simplification

TP 391

10.11996/JG.j.2095-302X.2021060979

A

2095-302X(2021)06-0979-08

2021-01-31；

2021-03-10

國家自然科學基金項目(61602213，61772013)；國家重點研發(fā)計劃項目(2017YFB0202303)

周 晨(1994-)，男，安徽宿州人，碩士研究生。主要研究方向為計算機圖形學。E-mail：6181611034@stu.jiangnan.edu.cn

陳 偉(1986–)，男，江蘇寶應人，副教授，博士。主要研究方向為計算機輔助幾何設計、計算機圖形學等。E-mail：wchen_jdsm@163.com

31 January，2021；

10March，2021

National Natural Science Foundation of China (61602213，61772013); TheNational Key R&D Program of China (2017YFB0202303)

ZHOU Chen (1994-), male, master student. His main research interest covers computer graphics. E-mail：6181611034@stu.jiangnan.edu.cn

CHEN Wei (1986–), male, associate professor, Ph.D. His main research interests cover computer aided geometric design, computer graphics, etc. E-mail：wchen_jdsm@163.com