線對象的慣性函數(shù)描述與三角剖分方法

吳明光，鄭培蓓，閭國年

1. 南京師范大學(xué)虛擬地理環(huán)境教育部重點實驗室，江蘇 南京210023； 2. 江蘇省地理信息資源開發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京 210023

?

線對象的慣性函數(shù)描述與三角剖分方法

吳明光1,2，鄭培蓓1，閭國年1,2

1. 南京師范大學(xué)虛擬地理環(huán)境教育部重點實驗室，江蘇 南京210023； 2. 江蘇省地理信息資源開發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京 210023

Foundation support： The National Natural Science Foundation of China (No. 41271446)；The Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions

摘要：現(xiàn)有線對象三角剖分算法沒有顧及線對象的整體結(jié)構(gòu)特征，導(dǎo)致三角剖分質(zhì)量不高，難以支持大數(shù)據(jù)量的矢量制圖和高更新率的動態(tài)制圖。本文提出線對象的慣性函數(shù)，設(shè)計了一種線對象的單調(diào)分解與三角剖分方法。慣性函數(shù)的單調(diào)遞增區(qū)間作為線對象的漸變區(qū)間，連續(xù)剖分為一個優(yōu)化的三角形條帶；慣性函數(shù)的單調(diào)遞減區(qū)間作為線對象的突變區(qū)間，離散剖分為一個優(yōu)化的三角形扇。試驗表明：本文方法三角剖分的頂點、三角形、圖元的個數(shù)均優(yōu)于基于頂點和基于線段的三角剖分方法，能夠顯著提升線對象的繪制效率。本文方法也適用于封閉線型、寬度漸變線型與光滑線型。

關(guān)鍵詞：線對象；符號化；單調(diào)分解；三角剖分；線光滑

硬件加速的地圖繪制方法不僅引起了學(xué)術(shù)界的廣泛討論[1-2]，還得到了商業(yè)界和開源社區(qū)的積極響應(yīng)。谷歌公司推出基于硬件加速的WebGL地圖測試版以及MapServer發(fā)布支持OpenGL繪制的地圖服務(wù)就是其中的典型。與純軟件繪制方法不同的是，硬件加速繪制的基本單元主要是三角形、四邊形以及它們構(gòu)成的條帶(stripe)或扇(fan)[3]。如何對線對象實施高質(zhì)量三角剖分成為線對象硬件加速繪制的關(guān)鍵問題。

線對象分解方法包括：Minkowski和分解[4]、頂點分解[5]、線段分解[6]、V分解[7]與梯形分解[8]。Minkowski和分解方法屬于基于點集理論的分解方法，具有嚴(yán)密的數(shù)學(xué)基礎(chǔ)，但是算法復(fù)雜度較高且無法支持寬度漸變、顏色漸變的線型。頂點分解方法首先逐個計算頂點的法向量，然后基于線段的寬度，順、逆法線方向，構(gòu)造三角形條帶。該方法沒有考慮張角較大和頂點比較接近這兩種情況，僅適用于繪制光滑曲線。線段分解方法以線對象兩個相鄰頂點為單位，獨立進(jìn)行三角剖分，線段相交的地方疊加繪制一個彌補視覺缺陷的圓形。該方法繪制效率高，但僅能滿足視覺要求，適用于純色填充的線型繪制，不支持紋理線型和漸變線型。V分解方法對于任意線對象，沿坐標(biāo)點的順序，除首末點外，計算任意相鄰兩個頂點的中點(內(nèi)插點)，內(nèi)插點—頂點—內(nèi)插點構(gòu)成一個V型的折線。該算法以V作為基本單位，V單元之間彼此獨立，存在頂點冗余，三角剖分后三角形過多，三角形條帶數(shù)量大，繪制效率不高。梯形分解方法將擴展多邊形的頂點按照y坐標(biāo)由小到大排序，在不同y坐標(biāo)處引一條平行于x軸的平行線，所有的平行線將擴展多邊形分解為一系列梯形(梯形可退化為三角形)。梯形分解時，需要涉及內(nèi)外判別、排序等算法，算法復(fù)雜度高，三角形條帶個數(shù)較多，繪制效率不高。綜合來看，Minkowski和與梯形分解方法屬于全局的分解方法，沒有借助頂點本身的順序信息來輔助三角剖分，導(dǎo)致分解質(zhì)量不高。頂點分解、線段分解、V分解方法屬于局部的分解方法，均是針對線對象的局部幾何特征來設(shè)計的，三角剖分的質(zhì)量不高且適應(yīng)性不強。

文獻(xiàn)[9]發(fā)現(xiàn)線對象上某些點的信息要比其他點豐富，關(guān)鍵點對于線對象的幾何、結(jié)構(gòu)特征描述具有決定性的作用。此后，線對象特征點的提取問題引起了廣泛的研究，相繼提出了張角探測、多邊形擬合、濾波以及混合型的方法[10-12]。特征點分析已經(jīng)在曲線形態(tài)結(jié)構(gòu)化表達(dá)、曲線綜合等方面展開應(yīng)用。但是，尚沒有針對線對象三角剖分的特征點提取與應(yīng)用方法。

從上述線對象三角解剖算法的效率、質(zhì)量和適應(yīng)性來看，線對象本身形態(tài)復(fù)雜，線型較多?，F(xiàn)有三角剖分算法沒有顧及到線對象的整體結(jié)構(gòu)特征，導(dǎo)致三角剖分質(zhì)量不高，繪制效率低，影響矢量地圖操作體驗，難以支持?jǐn)?shù)據(jù)量大的矢量制圖和高更新率的動態(tài)制圖[13]。本文在分析線對象漸變與突變特征的基礎(chǔ)上提出一種線對象的單調(diào)分解與三角剖分方法。

1線對象單調(diào)分解與三角剖分方法

1.1線對象的單調(diào)分解

在客觀地理世界中，地理對象和地理現(xiàn)象的漸變和突變現(xiàn)象廣泛存在。線對象鄰近頂點構(gòu)成的張角作為決定三角剖分的關(guān)鍵因素，也存在漸變與突變現(xiàn)象。圖1(a)為某地區(qū)一段河流，包含37個頂點。若Pi、Pi-1構(gòu)成的向量記為a，Pi、Pi+1構(gòu)成的向量記為b，則

(1)

式中，n為頂點個數(shù)；k(i)描述第i個頂點的張角θ(a<θ

圖1　線對象的慣性函數(shù)示意圖Fig.1　Momentum function diagram for polyline

本文通過定義慣性函數(shù)對線對象實施單調(diào)分解，以單調(diào)區(qū)間為單位實施三角剖分。

1.2基于單調(diào)區(qū)間的三角剖分方法

頂點、三角形、圖元個數(shù)是三角剖分的3個重點評價指標(biāo)。下文以這3個指標(biāo)作為定量分析的依據(jù)，從線對象單個頂點和鄰近頂點兩個角度來論述本文思路。

1.2.1線對象單個頂點的優(yōu)化剖分

文獻(xiàn)[14—16]將線對象頂點分為miter、bevel、round、triangular4種類型，分別如圖2中(a)、(b)、(c)、(d)所示。現(xiàn)有的三角剖分方法中，Minkowski和分解、頂點分解、線段分解與梯形分解方法均忽略頂點間的順序關(guān)系，剖分時需要內(nèi)插輔助點，頂點、三角形和三角形條帶數(shù)據(jù)均較大，剖分質(zhì)量較低。V分解方法利用頂點的順序關(guān)系，剖分質(zhì)量最高。綜合來看，miter類型的最優(yōu)分解方案是分解為如圖2中(e)所示的一個完整的三角形條帶，bevel、round、triangular類型的最優(yōu)分解方案是如圖2(f)、(g)、(h)所示的一個完整三角形扇。文獻(xiàn)[2]更進(jìn)一步認(rèn)為當(dāng)張角接近于平角，后3種情況可退化為第1種情況。

圖2　線對象的優(yōu)化三角剖分示意圖Fig.2　Optimized tessellation for polyline

1.2.2線對象鄰近頂點的優(yōu)化剖分

從三角形條帶和三角形扇的數(shù)據(jù)結(jié)構(gòu)容易看出，相鄰的兩個三角形條帶是可以合并的，即：位置相同的兩個頂點可以合并，兩個三角形條帶可以合并為一個三角形條帶。如果兩個三角形扇的起始點不一致，則無法合并。如果一個包含4個頂點的三角形條帶和一個三角形扇鄰近，則該三角形條帶可以合并到三角形扇中。V分解方法雖然能夠保證頂點類型的最優(yōu)剖分，但忽略了分解單元之間連續(xù)性，導(dǎo)致整體剖分質(zhì)量不高。

由上述兩方面的分析來看，單調(diào)遞增區(qū)間內(nèi)的頂點可優(yōu)化剖分為一個連續(xù)的三角形條帶；單調(diào)遞減區(qū)間內(nèi)的頂點，可優(yōu)化剖分為一個三角形扇。如果單增區(qū)間僅包含兩個頂點，則該單增區(qū)間對應(yīng)的三角形條帶并入鄰近的三角形扇中。這種剖分方法不管在整體還是局部上均優(yōu)于前文所述5種方法。

1.3基于單調(diào)區(qū)間的三角剖分算法描述

圖3　頂點內(nèi)推線、外推線示意圖Fig.3　Interpolated line and extrapolated line of vertex

本文采用逐點推進(jìn)、一次遍歷的方法同時完成三角形的單調(diào)分解和三角剖分，完整的算法流程如下。

(6) 算法結(jié)束。清空全局頂點對緩存。

算法步驟(2)—(4)中，建立頂點對緩存對應(yīng)于一個單增區(qū)間開始。頂點對緩存并不立即清空，而是等單增區(qū)間結(jié)束(下一個頂點為扇形頂點)時才將頂點對緩存變?yōu)橐粋€連續(xù)的三角形條帶。如圖4(a)中，Pn-1、Pn為V型頂點，Pn+1為扇形頂點。Pn-1、Pn對應(yīng)的三角形條帶延遲到Pn+1才封閉。步驟(4)中，需要判斷頂點對緩存是否為1，其目的是為了處理單增區(qū)間僅包含一個頂點的情況。如圖4(b)所示，當(dāng)線對象開始于Pn-1，而Pn為扇形頂點，則頂點Pn-1對應(yīng)的三角形條帶可并入Pn對應(yīng)的Triangle_Fan中。步驟(4)中的Triangle_Fan也不立即封閉的主要原因是，若下一個頂點為V型頂點，則該條帶頂點的兩個點可并入上一個Triangle_Fan中；如果下下個頂點為扇形頂點，則可減少一個三角形條帶。如圖4(c)所示，如果線對象在Pn結(jié)束，也可減少一個三角形條帶。本文將上述策略稱之為三角形條帶的延遲封閉。

圖4　三角形條帶延遲封閉的3種情況Fig.4　Three kinds of delayed closure for triangle strip

由圖1(b)可知，線對象慣性函數(shù)的單調(diào)遞增區(qū)間廣泛存在且覆蓋范圍較大。本文算法中的三角形條帶的延遲封閉策略，可以將單增區(qū)間內(nèi)的頂點優(yōu)化剖分為一個連續(xù)的三角形條帶。單調(diào)遞增區(qū)間中，還包含一些僅包含兩個頂點的區(qū)間，本文算法中的三角形條帶的延遲封閉還可將僅包含一個頂點的區(qū)間對應(yīng)的三角形條帶并入到鄰近的三角形扇中，可進(jìn)一步優(yōu)化三角剖分質(zhì)量。

23種特殊線型的三角剖分

本文將具有寬度、顏色等符號信息的線稱之為線型。綜合文獻(xiàn)[17—19]的討論，符號化過程中還包括寬度變化的線型、封閉的線型以及光滑的線型等。本文方法適用于封閉線型、變寬線型和光滑線型的繪制。

2.1封閉線型

在1.3節(jié)描述的三角剖分流程中，起點作為V形頂點處理。如圖5(a)所示，對于封閉的線對象，起點的類型將依據(jù)下一頂點P1和最后一個點Pn構(gòu)成的張角來判斷。若為V形頂點，則按照1.3節(jié)描述的單調(diào)三角剖分流程執(zhí)行結(jié)束后，增加判斷Pn的頂點類型：若Pn為V形頂點，則Pn派生的三角形條帶和P0派生的三角形條帶合并；若為扇形頂點，則跳過P0，判斷P1的頂點類型，直到搜索到第一個V形頂點。將中間跳過的扇形頂點，順序追加到Pn后面。執(zhí)行單調(diào)剖分，完成封閉線型的三角剖分。

圖5　封閉線、變寬線三角剖分示意圖Fig.5　Tessellation for closed and mutative width line style

2.2寬度漸變線型

本文方法支持等寬線型與變寬線型的繪制。如圖5(b)所示，在頂點進(jìn)行內(nèi)推線、外推線的計算時，線對象的每個頂點均可以獨立賦寬度值。若所有頂點的寬度相同，則為等寬線型。若頂點寬度不同，即為變寬線型。

2.3光滑線型

連續(xù)參數(shù)曲線在柵格化的過程中必須離散化。在連續(xù)曲線的柵格化過程中，離散化本身涉及導(dǎo)數(shù)、三角函數(shù)等計算，為保證離散后參數(shù)曲線的光滑特征，離散后數(shù)據(jù)量顯著增大，這兩個方面的原因均會降低光滑曲線的繪制效率。本文方法中離散后的線段存在較強的連續(xù)性。一段包含39個頂點的等高線數(shù)據(jù)，對其進(jìn)行3次B樣條曲線擬合，得到257個點，分別繪制離散前后慣性函數(shù)，如圖6(a)、(b)所示。由圖可知，擬合為光滑曲線后慣性函數(shù)表現(xiàn)出的單調(diào)遞增區(qū)間更大，單調(diào)遞增區(qū)間的個數(shù)更多。因此，本文算法有利于形成更為連續(xù)的三角形條帶，得到質(zhì)量更高的三角剖分結(jié)果。

圖6　等高線光滑前后慣性函數(shù)對比Fig.6　Contrast of momentum function before and after contour smoothing

3試驗驗證

如圖7所示，選擇OpenStreetMap數(shù)據(jù)集(http:∥www.openstreetmap.org/)中的海岸線、河流、境界線、鐵路、城市道路和GPS軌跡6組數(shù)據(jù)進(jìn)行對比測試。采用頂點分解和線段分解兩類算法與本文算法進(jìn)行效率與質(zhì)量對比。頂點分解

采用VaseRender(VR)算法(https:∥github.com/tyt2y3/vaserenderer)。線段分解采用MapServer6.0.0中線符號繪制代碼算法(簡寫為MS)(http:∥mapserver.org/zh_cn/download.html)。試驗采用C++語言實現(xiàn)本文算法，采用OpenGL作為圖形繪制接口。試驗中采用開源空間數(shù)據(jù)讀寫軟件包GDAL1.4(GeospatialDataAbstractionLibrary)實現(xiàn)對試驗數(shù)據(jù)的讀取。測試環(huán)境：IBMThinkPadT410s,Inter(R)core(TM)i5CPU,3GB內(nèi)存，Windows7，32位操作系統(tǒng)。每次繪制100次。運行10次，取平均值作為測試結(jié)果。試驗結(jié)果如表1所示。

圖7　6組試驗數(shù)據(jù)Fig.7　Six groups of experimental data

數(shù)據(jù)集名稱頂點數(shù)頂點,三角形,圖元數(shù)繪制1000次效率/(10-3s)MS法VR法本文算法MS法VR法本文算法鐵路127(3298,2919,253)(417,748,125)(260,258,5)1659615城市道路321(8342,7381,641)(899,1911,319)(813,811,83)40125546海岸線410(10656,9428,819)(3011,4379,408)(2182,2180,319)503409122GPS軌跡730(18976,16788,1459)(3284,4654,728)(2012,2010,231)858595119河流995(25866,22883,1989)(5321,6867,993)(4045,4043,823)1172807263境界1563(40634,35947,3125)(6504,10719,1561)(5163,5161,766)18151222314

3.1效率分析

由表1可知，本文三角剖分方法所得頂點、三角形、圖元個數(shù)明顯小于V分解方法和線段分解方法。其主要原因是：V分解算法中，對于任意線對象，沿著坐標(biāo)點的順序，除首末點外，計算任意相鄰兩個頂點的中點(內(nèi)插點)，按內(nèi)插點—頂點—內(nèi)插點順序構(gòu)成一個V型的折線，由n個頂點構(gòu)成的線對象可以分解為n-2個V對象。V對象之間彼此獨立，存在頂點冗余，三角剖分后，三角形過多，三角形條帶數(shù)量大，導(dǎo)致繪制效率不高。線段分解方法以線對象兩個相鄰頂點為單位，分解為由兩個相鄰頂點構(gòu)成的線段，將線段進(jìn)行內(nèi)、外推，得到一個矩形，一個矩形分解為一個三角形條帶。線段相交的地方疊加繪制一個半徑為r的圓形。由于線段之間彼此獨立，三角形條帶數(shù)量大，不考慮Bevel、Round、Triangular 3種情況，任意張角均繪制一個半徑為r的圓，也增加了頂點、三角形條帶、扇的個數(shù)，導(dǎo)致繪制效率不高。本文方法直接以單調(diào)鏈為三角剖分的基本單位，分解中由于避免了中間內(nèi)插頂點的外推，擴展多邊形的頂點數(shù)據(jù)、三角形的個數(shù)、三角形條帶的個數(shù)均小于V分解和線段分解。因此，繪制效率明顯優(yōu)于V分解方法和線段分解方法

3.2適應(yīng)性分析

疊加兩個不同寬度的線型和一個虛線線型，繪制了封閉的高速公路，如圖8(a)；采用寬度漸變填充，繪制了漸變線型的河流，如圖8(b)。其對應(yīng)的三角剖分結(jié)果分別如圖8(c)、(d)所示。

圖8　算法對線型的支持Fig.8　Algorithm support for different line styles

采用數(shù)據(jù)量不等的3組等高線數(shù)據(jù)來驗證本文算法對光滑線型繪制的支持。選擇MS方法作為比較對象，采用直接繪制和三次B樣條光滑曲線繪制。統(tǒng)計本文方法對MS方法的加速比(倍率)。表2所示的試驗結(jié)果中，加速比由直接繪制時平均8.6倍增長為光滑繪制時的平均9.4倍。其主要原因是：光滑曲線繪制過程中，本文算法能夠充分利用線對象的連續(xù)性，得到質(zhì)量更高的剖分結(jié)果，從而提高繪制效率。因此，本文算法針對光滑線型繪制的加速比要高于折線繪制的加速比。

表2　等高線光滑曲線繪制效率測試結(jié)果

4結(jié)論與展望

線對象符號化的效率與質(zhì)量成為當(dāng)前地圖制圖與發(fā)布的關(guān)鍵因素[20]。硬件加速繪制成為當(dāng)前的研究熱點。本文認(rèn)為，現(xiàn)有三角剖分算法中，不管是頂點分解、線段分解還是V分解，均是從線對象的局部幾何特征出發(fā)來設(shè)計的，忽略了線對象的整體形態(tài)特征。整體分解方法沒有利用線對象本身的結(jié)構(gòu)特征，算法復(fù)雜度較高且分解質(zhì)量差。

本文給出了線對象的慣性函數(shù)，提出了一種基于單調(diào)區(qū)間的三角剖分方法。慣性函數(shù)的單調(diào)遞增區(qū)間是線對象張角的漸變區(qū)間，可連續(xù)剖分為一個優(yōu)化的三角形條帶；慣性函數(shù)的單調(diào)遞減區(qū)間是線對象張角的突變區(qū)間，可離散剖分為一個優(yōu)化的三角形扇。本文采用真實數(shù)據(jù)對本文算法進(jìn)行了試驗，結(jié)果表明本文方法的三角剖分質(zhì)量和繪制效率均優(yōu)于基于頂點、基于線段的三角剖分方法，能夠顯著提高線對象的符號化效率。

參考文獻(xiàn)：

[1]RENHART Y. Fast Map Rendering for Mobile Devices[D]. Gothenburg: University of Gothenburg, 2009.

[2]R?SSLER L. Rendering Interactive Maps on Mobile Devices Using Graphics Hardware[D]. Vienna: Vienna University of Technology, 2012.

[3]ROUGIER N. Shader-based Antialiased Dashed Stroked Polylines[J]. Journal of Computer Graphics Techniques, 2013, 2(2): 91-107.

[4]Category System. A Realistic 2D Drawing System[EB/OL].[2003-06-19]. http:∥www.keithp.com/.

[5]HERTZMANN A. A Survey of Stroke-based Rendering[J]. IEEE Computer Graphics and Applications, 2003, 23(4): 70-81.

[6]WANG Jiechen, CUI Can, PUYingxia, et al. A Novel Algorithm of Buffer Construction Based on Run-length Encoding[J]. The Cartographic Journal, 2010, 47(3): 198-210.

[7]TSANG C. Vase Renderer is a Polyline and Curve Renderer on Open GL[EB/OL].[2014-09-18]. https:∥github.com/tyt2y3/vaserenderer.

[8]KILGARD M J, BOLZ J. GPU-accelerated Path Rendering[J]. ACM Transactions on Graphics (TOG), 2012, 31(6): 172.

[9]LI Zhilin. An Examination of Algorithms for the Detection of Critical Points on Digital Cartographic Lines[J]. The Cartographic Journal, 1995, 32(2): 121-125.

[10]GUILBERT E, SAUX E. Cartographic Generalisation of Lines Based on a B-spline Snake Model[J]. International Journal of Geographical Information Science, 2008, 22(8): 847-870.

[11]艾廷華, 郭仁忠, 劉耀林. 曲線彎曲深度層次結(jié)構(gòu)的二叉樹表達(dá)[J]. 測繪學(xué)報, 2001, 30(4): 343-348.

AI Tinghua, GUO Renzhong, LIU Yaolin. A Binary Tree Representation of Curve Hierarchical Structure in Depth[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(4): 343-348.

[12]彭東亮, 鄧敏, 劉慧敏. 更充分利用獨立彎曲結(jié)構(gòu)的線狀要素Morphing變換方法[J]. 測繪學(xué)報, 2014, 43(6): 637-644, 652. DOI: 10.13485/j.cnki.11-2089.2014.0100.

PENG Dongliang, DENG Min, LIU Huimin. Morphing Transformation of Linear Features by Using Independent Bend Structures More Sufficiently[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(6): 637-644, 652. DOI: 10.13485/j.cnki.11-2089.2014,0100.

[13]SWIENTY O, ZHANG M, REICHENBACHER T, et al. Establishing a Neurocognition-based Taxonomy of Graphical Variables for Attention-guiding Geovisualisation[C]∥International Society for Optics and Photonics.Nanjing: SPIE, 2007: 675109.

[14]W3C Recommendation. Scalable Vector Graphics (SVG) Full 1.2 Specification[EB/OL].[2010-07-11]. http:∥www.w3.org/TR/SVG12.

[15]Adobe Systems Incorporated.PDF Reference[EB/OL]. [2007-04-11]. http:∥www.images.adobe.com/content/dam/Adobe/en/devnet/pdf/pdfs/pdf_reference_1-7.pdf.

[16]DANIEL R. Open VG Specification Version 1.0.1[EB/OL].[2005-05-13]. https:∥www.khronos.org/registry/vg/specs/openvg_1_0_1.pdf.

[17]OGC 02-070. Styled Layer Descriptor Implementation Specification[S].Open GIS Consortium Inc.,2002.

[18]李麗, 王結(jié)臣, 沈定濤, 等. 一種單線河流漸變符號的繪制方法[J]. 測繪通報, 2008(11): 64-67.

LI Li, WANG Jiechen, SHEN Dingtao, et al. A Method for Plotting Gradual Change Symbol of Single-line Stream[J]. Bulletin of Surveying and Mapping, 2008(11): 64-67.

[19]MACEACHREN A M.How Maps Work: Representation, Visualization, and Design[M]. New York: Guilford Press, 2004.

[20]NOGUERA J M, SEGURA R J, OGYAR C J, et al. A Scalable Architecture for 3D Map Navigation on Mobile Devices[J]. Personal and Ubiquitous Computing, 2013, 17(7): 1487-1502.

(責(zé)任編輯：張艷玲)

A Momentum Function Description and Tessellation Method for Polyline

WU Mingguang1,2，ZHENG Peibei1，Lü Guonian1,2

1. Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, Nanjing 210023, China; 2. Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023, China

Abstract：Without taking polyline global structure into consideration, current polyline tessellation methods tend to make low quality decomposition. It makes them difficult to support vector mapping with large dataset and dynamic mapping with high update rate. This paper proposed a polyline momentum function and designed a monotone decomposition and tessellation method. The monotonous increasing intervals of the momentum function, as the gradient intervals of polyline, are divided continuously into optimized triangle strips. The monotone decreasing intervals of the momentum function, as the mutational intervals of polyline, are divided discretely into optimized triangle fans. The experiment results show that the decomposition quality measured by the numbers of triangulation vertices, triangles and primitives using this method are better than that based on vertex and line segment and can significantly improve the drawing efficiency for polyline. This method is also applicable to closed, width gradient and smooth line style.

Key words：polyline; symbolization; monotone decomposition; tessellation; polyline smoothing

基金項目：國家自然科學(xué)基金(41271446)；江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助項目

中圖分類號：P208

文獻(xiàn)標(biāo)識碼：A

文章編號：1001-1595(2016)03-0372-07

作者簡介：第一 吳明光(1979—)，男，博士，副教授，研究方向為空間數(shù)據(jù)模型、空間信息可視化。E-mail： wmg@njnu.edu.cn

收稿日期：2014-10-27

引文格式：吳明光，鄭培蓓，閭國年.線對象的慣性函數(shù)描述與三角剖分方法[J].測繪學(xué)報，2016,45(3)：372-378.DOI:10.11947/j.AGCS.2016.20140545.

WU Mingguang, ZHENG Peibei, Lü Guonian.A Momentum Function Description and Tessellation Method for Polyline[J]. Acta Geodaetica et Cartographica Sinica,2016,45(3):372-378.DOI:10.11947/j.AGCS.2016.20140545.

修回日期： 2015-03-19

First author： WU Mingguang(1979—), male, PhD,associate professor， majors in spatial data model and spatial information visualization.