周鑫鑫，吳長彬，孫在宏，丁 遠(yuǎn)，賀 濤

南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210046

小規(guī)模地理場景中點(diǎn)要素三維注記優(yōu)化配置算法

周鑫鑫，吳長彬，孫在宏，丁 遠(yuǎn)，賀 濤

南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210046

地理場景中點(diǎn)要素三維注記配置規(guī)則多為“遮擋則不顯示”和“遮擋直接顯示”，該類規(guī)則的缺陷是注記信息丟失或存在大量遮擋，普適性不強(qiáng)，尤其不適用于小規(guī)模地理場景點(diǎn)要素三維注記配置。本文首先歸納了三維注記繪制的內(nèi)容、位置及方法，并針對小規(guī)模地理場景點(diǎn)要素三維注記配置問題，以“信息不丟失、注記盡可能少的遮擋”為配置目標(biāo)，配置規(guī)則為“遮擋后優(yōu)化并顯示”。算法以透視變換矩陣、逆透視變換矩陣及GRID算法為基礎(chǔ)，以遺傳算法為核心，以三維注記質(zhì)量評價(jià)函數(shù)為遺傳算法適應(yīng)度評價(jià)函數(shù)，實(shí)現(xiàn)點(diǎn)要素三維注記的可行最優(yōu)解求解。經(jīng)多視角、多平臺對照試驗(yàn)可知，本算法適用于多視角三維注記優(yōu)化配置，具備普適性；與主流GIS平臺(SuperMap Desktop、ArcScene)的三維注記配置效果作對比，本算法三維注記質(zhì)量值分別相對提升144%、232%，符合配置目標(biāo)。

地理場景；三維注記；三維注記配置；遺傳算法；注記質(zhì)量評價(jià)函數(shù)；GRID算法

三維注記配置屬于三維地理環(huán)境圖形化表達(dá)中的語義信息表達(dá)研究范疇[1]。語義信息表達(dá)是采用文字、符號直觀展現(xiàn)地物屬性值，如：道路名稱、建筑物名稱等。注記(annotation)，或稱標(biāo)注(label)，是語義信息表達(dá)的直接方式，也是地圖語言的重要組成部分[2]。以數(shù)據(jù)維度為標(biāo)準(zhǔn)，注記配置分為二維注記配置、三維注記配置。目前，二維注記配置研究較多，根據(jù)要素維度劃分為0維、一維、二維，其中，0維地理要素的二維注記配置以優(yōu)化算法研究為主，如：物理松弛法[3]、遺傳算法[4]、聚類搜索算法[5]，一維、二維地理要素的二維注記配置以注記候選位置計(jì)算研究為主，如：熵心定位[6]、散列式定位[7]，此外，地圖注記引擎[8]、地圖注記規(guī)則庫[9]、影像的注記配置[10]也得到了廣泛研究。三維注記配置是對二維注記配置的維度拓展，二維的研究理論適用于三維，但三維注記配置更為復(fù)雜，表現(xiàn)為：渲染量大、顯示呈現(xiàn)“近大遠(yuǎn)小”、多視角等。三維注記配置處于研究發(fā)展期，以研究注記生成過程、注記優(yōu)化方法、GPU加速計(jì)算為重[11-16]。

不同數(shù)據(jù)體量的地理場景，其加載機(jī)制、渲染機(jī)制、內(nèi)存控制、語義信息表達(dá)機(jī)制有本質(zhì)差異。大規(guī)模地理場景數(shù)據(jù)多采用分塊索引加載渲染機(jī)制，按需加載，避免內(nèi)存超負(fù)荷，如數(shù)據(jù)調(diào)度流水線方法[17]，軟件平臺如ArcGlobe平臺；小規(guī)模地理場景數(shù)據(jù)一般采用直接加載渲染機(jī)制，避免頻繁的調(diào)用數(shù)據(jù)進(jìn)入內(nèi)存，軟件平臺如ArcScene平臺。不同規(guī)模地理場景的注記渲染方式和優(yōu)化方式不同，大規(guī)模地理場景多采用屏幕空間的注記(screen space annotation)，小規(guī)模地理場景一般采用基于對象空間的注記(object space annotation)[12]。

1 小規(guī)模地理場景中的注記

小規(guī)模地理場景中點(diǎn)要素三維注記配置需解決3個(gè)問題：繪制內(nèi)容、繪制位置及如何繪制。綜述，三維注記配置研究處于發(fā)展期，其優(yōu)化方法簡單。將二維注記的優(yōu)化配置算法推廣至三維注記配置研究中，成為本文研究內(nèi)容。

1.1 注記繪制內(nèi)容

影響三維注記內(nèi)容展示的因素有：注記文字內(nèi)容、注記視覺變量、場景視覺變量。注記文字內(nèi)容是指顯示的屬性內(nèi)容，分為說明注記和名稱注記兩種。注記視覺變量指注記元素本身的各項(xiàng)屬性設(shè)置，總結(jié)為9種：字體、字號、字色、字型、字列、字隔、字向、外框、圖標(biāo)，其樣式如圖1所示。場景視覺變量包括：光源、地圖背景、垂直夸張度、觀察視野等。觀測視野的設(shè)置包括觀測點(diǎn)坐標(biāo)設(shè)置、目標(biāo)點(diǎn)坐標(biāo)設(shè)置、視距設(shè)置、視角設(shè)置、相機(jī)的方位角(azimuth angle)、傾角(inclination angle)設(shè)置等。

圖1 三維注記視覺變量樣式圖Fig.1 Visual variables pattern of 3D annotation

1.2 注記繪制位置

三維注記因繪制位置的差異，可分為：①貼于三維模型表面柵格紋理，見圖2(a)；②觸發(fā)后彈出框式，見圖2(b)；③貼于地表的柵格紋理，見圖2(c)；④朝屏幕方向的廣告牌，見圖2(d)；⑤朝固定面方向的廣告牌，見圖2(e)。其中，以③、④為常見樣式。此外，三維注記繪制位置受待選注記方位影響。二維注記待選方位常見有四方位、八方位等，三維注記待選方位可沿用二維注記待選方位，但隨著三維注記所處空間的維度提升，三維注記的待選方位多樣性也增加。三維注記待選方位示意如圖3所示。

圖2 三維注記分類示意圖Fig.2 Classification schematic diagram of 3D annotation

圖3 三維注記待選方位示意圖Fig.3 Schematic diagram of propositions of 3D annotation

1.3 注記繪制方法

從三維注記發(fā)生視覺上遮擋則的優(yōu)化策略進(jìn)

行劃分，分為遮擋則直接顯示、遮擋則優(yōu)化并顯示及遮擋則不顯示，3種情況各有優(yōu)缺點(diǎn)且其適用的范疇各不相同。舉例示意，圖4(a)為遮擋則直接顯示，圖4(b)為遮擋則優(yōu)化并顯示，圖4(c)為遮擋則不顯示。

遮擋則直接顯示，缺點(diǎn)明顯，要素增多后傳遞的語義信息急劇下降。遮擋則優(yōu)化，采用注記優(yōu)化配置算法計(jì)算，得到該視角下可行解，其與PFCLP問題中的MNCFLP[18]和MNCP[3]兩種策略相一致，其優(yōu)點(diǎn)是信息無丟失，語義信息完整，適用于小規(guī)模的地理場景。遮擋則不顯示，采用深度檢測剔除該視角下深度大且被壓蓋的注記，其與PFCLP問題的MISP策略[19]相一致，其優(yōu)點(diǎn)是簡潔，但缺點(diǎn)是信息丟失。表1對3種方式的概念、優(yōu)化策略、優(yōu)缺點(diǎn)、適用范疇進(jìn)行了總結(jié)。

圖4 注記遮擋后優(yōu)化策略示意圖Fig.4 Schematic diagram of the optimal strategies for post annotation occlusion

表1 注記遮擋后優(yōu)化策略對比表Tab.1 Comparison of the optimal strategies for post annotation occlusion

2 注記配置規(guī)則

小規(guī)模地理場景中點(diǎn)要素三維注記配置采用基于對象空間的注記，注記遮擋后的優(yōu)化策略為遮擋則優(yōu)化，從而確?！白⒂浶畔⒉粊G失、視線方向上注記遮擋盡量少”。

2.1 三維注記待選方位

小規(guī)模地理場景中點(diǎn)要素的注記待選方位選用三維空間中的與視線方向垂直面上的四方位待選注記方案。假設(shè)觀察者的方位角和傾角為(θ,φ)，三維點(diǎn)要素P(x,y,z)，三維注記尺寸為(w,h)，如圖5所示，則四方位三位注記框中心點(diǎn)Pi的計(jì)算見式(1)

(1)

圖5 三維點(diǎn)要素四方位待選注記方案示意圖Fig.5 The 4 propositions annotation scheme of 3D point feature

2.2 三維注記質(zhì)量評價(jià)函數(shù)

實(shí)現(xiàn)“注記信息不丟失、視線方向上注記遮擋盡量少”的配置目標(biāo)，需定量化為三維注記質(zhì)量評價(jià)函數(shù)，評價(jià)函數(shù)的設(shè)計(jì)直接影響注記的質(zhì)量[20]。注記質(zhì)量評價(jià)函數(shù)需符合：注記丟失個(gè)數(shù)越少函數(shù)值越大；注記遮擋越少函數(shù)值越大的設(shè)計(jì)原則；當(dāng)注記發(fā)生丟失時(shí)，則丟失注記不會發(fā)生注記遮擋，兩者具備互斥性。本文提出小規(guī)模地理場景三維注記質(zhì)量評價(jià)函數(shù)E，E是E(i)的總和，見式(2)，E(i)表示第i個(gè)注記的質(zhì)量值。E(i)由評價(jià)子函數(shù)組成，如式(3)所示。顧及三維點(diǎn)要素四方位待選注記方案中，各方位與要素關(guān)聯(lián)性相同、優(yōu)先級視為一致，故E(i)未將注記與要素關(guān)聯(lián)性、注記方位優(yōu)先級納入子函數(shù)范疇

(2)

E(i)=200/(?Ef(i)+ηEa(i)+lEd(i)+2)

(3)

3 算法設(shè)計(jì)

三維點(diǎn)要素注記優(yōu)化配置算法是一種三維注記在視線方向上發(fā)生遮擋后進(jìn)行優(yōu)化后重新配置注記位置的算法。該算法由二三維坐標(biāo)系變換、GRID算法、遺傳算法(geneticalgorithm，GA)、注記質(zhì)量評價(jià)函數(shù)組成，相互關(guān)系是：二三維坐標(biāo)系變換和GRID算法是計(jì)算基礎(chǔ)；用于求解的遺傳算法是核心；三維注記質(zhì)量評價(jià)函數(shù)是遺傳算法適應(yīng)度計(jì)算公式，各模塊組合關(guān)系如圖6所示。

3.1 整體流程

三維點(diǎn)要素注記優(yōu)化配置算法的設(shè)計(jì)流程由6步組成，具體流程如下。

第1步：輸入三維要素點(diǎn)集、三維待選注記框中心點(diǎn)集矩陣，記為Vwcs。

第2步：透視變換。透視變換是獲得透視圖像的方法，可以運(yùn)用于要素、待選注記框的透視后坐標(biāo)集合Vdcs計(jì)算，透視變換矩陣如式(4)所示。Mmv為模型視點(diǎn)矩陣，變換后得到相機(jī)坐標(biāo)系；Mp為投影矩陣，得到投影坐標(biāo)系；Mw窗口變換矩陣，得到設(shè)備坐標(biāo)系

Vdcs=Vwcs×Mmv×Mp×Mw

(4)

注:R為Camera視點(diǎn)到世界坐標(biāo)系原點(diǎn)距離；θ為方位角(azimuth)，θ∈[0°，360°]；φ為傾斜角(inclination)，φ∈[-90°，360°]；D表示Camera視點(diǎn)到屏幕坐標(biāo)系原點(diǎn)的距離；w表示設(shè)備寬度；h表示設(shè)備的高度。

圖6 三維注記優(yōu)化配置算法結(jié)構(gòu)圖Fig.6 The structure of 3D annotation optimal placement algorithm

第3步：采用GRID算法進(jìn)行基礎(chǔ)網(wǎng)格構(gòu)建?；A(chǔ)網(wǎng)格是判別注記間壓蓋、注記與要素間沖突的快速方式。GRID算法包括：網(wǎng)格初始化、網(wǎng)格更新、網(wǎng)格讀取3個(gè)算子。其中，網(wǎng)格初始化算子是實(shí)現(xiàn)要素網(wǎng)格化的方法集合，點(diǎn)要素直接網(wǎng)格化，線要素可采用Bresenham算法[21]等，面要素可采用點(diǎn)在面內(nèi)算法[22]進(jìn)行網(wǎng)格化，完成初始化，得到要素網(wǎng)格(GRIDFea)，樣式如圖7所示。網(wǎng)格更新算子，涉及已知坐標(biāo)點(diǎn)(x,y)，求解網(wǎng)格行列號(row,col)，計(jì)算見式(5)。網(wǎng)格讀取算子，已知網(wǎng)格行列號(row,col)，求解坐標(biāo)點(diǎn)(x,y)，計(jì)算公式見式(6)。

圖7 要素網(wǎng)格化效果圖Fig.7 Effect scheme of feature meshed

(5)

(6)

式中，cellsize為網(wǎng)格單元尺寸；ymax是指所有要素的最大外包絡(luò)框的y最大值；xmin為所有二維屏幕要素的最大外包絡(luò)框的x最小值。

第4步：GA算法進(jìn)行最優(yōu)組合解計(jì)算。GA算法是啟發(fā)式算法的一種，以廣泛運(yùn)用于二維注記配置、TSP問題求解。其中，GA算法選擇算子的適應(yīng)度評價(jià)方法采用注記質(zhì)量評價(jià)函數(shù)(E)。經(jīng)初始化、選擇算子、交叉算子及變異算子計(jì)算后，得到結(jié)果解。

第5步：逆透視變換。逆透視變換是將計(jì)算得到的二維注記結(jié)果解轉(zhuǎn)換為三維注記，是透視變換的逆過程。逆透視變換公式如式(7)所示

(7)

第6步：輸出注記結(jié)果。將注記結(jié)果繪制于地理場景中。

3.2 核心算法

GA算法是模擬生物遺傳機(jī)制而形成的解決復(fù)雜組合優(yōu)化問題的算法[23]?；具z傳算法實(shí)現(xiàn)步驟是：①初始化形成初始種群；②基于適應(yīng)度函數(shù)對個(gè)體符號串進(jìn)行評價(jià)；③執(zhí)行遺傳操作生成一個(gè)新的符號串群體；重復(fù)第②、③步直到算法終止。遺傳操作包括：選擇算子、交叉算子及變異算子，遺傳算法的關(guān)鍵在于染色體個(gè)體符號串的表示和遺傳操作算子的設(shè)計(jì)。三維點(diǎn)要素注記配置的GA算法具體步驟如下：

步驟1：設(shè)置GA算法的基本參數(shù)和經(jīng)透視變換后的待選注記框集合(ListProAnno)輸入、要素網(wǎng)格基礎(chǔ)(GRIDFea)輸入。GA算法的基本參數(shù)設(shè)定：交叉概率(PC)、變異概率(PM)、種群規(guī)模(Popsize)、進(jìn)化代數(shù)(Iteration)、染色體基因座數(shù)量(CountFea)、注記質(zhì)量評價(jià)函數(shù)閾值(EValue)、基因上限值(MaxGene)、基因下限值(MinGene)。

步驟2：生成初始種群。當(dāng)前代數(shù)(Pop)等于1，種群中染色體數(shù)量為Popsize，每個(gè)染色體的基因座數(shù)量CountFea。每個(gè)基因座基因值(ValueGene)確定為隨機(jī)時(shí)間種子數(shù)，要求ValueGene∈{N*∩[MinGene,MaxGene]}。初始種群總體產(chǎn)生隨機(jī)數(shù)的次數(shù)為Popsize*CountFea。

步驟3：評價(jià)種群各染色體的適應(yīng)度值(E)。復(fù)制GRIDFea得到當(dāng)前代的GRIDTemp，根據(jù)該染色體上各ValueGene找出對應(yīng)的待選注記框集合中各要素的待選注記框(ProAnno)。在GRIDTemp基礎(chǔ)上，對ProAnno進(jìn)行網(wǎng)格化，網(wǎng)格信息記錄于GRIDTemp中。各基因的適應(yīng)度計(jì)算等價(jià)于E(Li)，染色體整體適應(yīng)度計(jì)算等價(jià)于E。

步驟4：最優(yōu)染色體選擇與終止條件判別。保留種群中最優(yōu)染色體及其適應(yīng)度值，判別終止條件((E≥EValue)Or(Pop>Iteration))，符合則停止執(zhí)行，該最優(yōu)染色體為注記解；否則，執(zhí)行步驟5。

步驟5：新一代種群生成。Pop自增1。調(diào)用賭輪盤算子進(jìn)行父代的染色體選擇。針對選擇出得父本染色體與父本最優(yōu)染色體進(jìn)行交叉算子，選擇對應(yīng)基因位，采用單點(diǎn)交叉，若隨機(jī)算子的概率值小于PC，即認(rèn)為符合交叉條件，執(zhí)行交叉。針對選擇出得父本染色體進(jìn)行變異算子，選擇有沖突的基因位，若隨機(jī)算子的概率值小于PM，則認(rèn)為符合變異條件，執(zhí)行變異。

步驟6：重新執(zhí)行步驟3，直至符合步驟4的終止條件。

4 算法試驗(yàn)

4.1 試驗(yàn)環(huán)境與試驗(yàn)數(shù)據(jù)

系統(tǒng)硬件環(huán)境：CPU：Intel(R)Core(TM)i5-4590，內(nèi)存：8GB，GPU：NVIDIA GeForce GT730；系統(tǒng)軟件環(huán)境：操作系統(tǒng)：操作系統(tǒng)：Windows10 64Bit，編程環(huán)境：Visual Studio 2010，編程語言：C#，GIS平臺：ESRI ArcObjects 10.2、SuperMap Desktop 8C。試驗(yàn)系統(tǒng)基于ArcScene Control實(shí)現(xiàn)各功能，ArcScene Control用于展示小規(guī)模三維不動(dòng)產(chǎn)場景數(shù)據(jù)。主要功能包括：試驗(yàn)數(shù)據(jù)加載、三維坐標(biāo)軸繪制、直接注記配置、注記優(yōu)化算法配置、試驗(yàn)參數(shù)設(shè)置等。試驗(yàn)數(shù)據(jù)采用三維地籍產(chǎn)權(quán)體[24]中的三維宗地體作為試驗(yàn)數(shù)據(jù)，試驗(yàn)數(shù)據(jù)如圖8所示。

圖8 三維宗地體示意圖Fig.8 Schematic diagram of 3D parcel

參數(shù)設(shè)置包括注記參數(shù)、網(wǎng)格參數(shù)、注記質(zhì)量評價(jià)函數(shù)參數(shù)、遺傳算法參數(shù)。注記參數(shù)： 8號、宋體。待選注記方位取四方位。網(wǎng)格參數(shù)：CellSize=0.1，CellValuePoint=1，CellValueLine= 10，CellValuePolygon=100， CellValueAnno= 1000。注記質(zhì)量評價(jià)函數(shù)參數(shù)：?=0.1、η=0.45、l=0.45，即認(rèn)同在小規(guī)模地理場景中，注記丟失與注記遮擋其他注記的影響程度一致，次之是注記遮擋其他要素。遺傳算法參數(shù)：Popsize=30，Iteration=50，PC=0.7，PM=0.1，EValue=30，MaxGene=4，MinGene=1，CountFea為三維點(diǎn)要素個(gè)數(shù)。

4.2 多視角、多平臺對照試驗(yàn)

為驗(yàn)證算法在多視角、多平臺上具備普適性和優(yōu)化性，試驗(yàn)方法采用宗地體對象圖8(a)，選具備代表性的GIS平臺(ESRI的ArcScene平臺、超圖的SuperMap Desktop平臺)作為對照組，設(shè)置多視角，進(jìn)行三維界址點(diǎn)三維注記配置，對比配置效果。對照結(jié)果如圖9所示，其中，1序列(1-a、1-b、1-c)視角參數(shù)為θ=90°，φ=10°；2序列(2-a、2-b、2-c)視角參數(shù)為θ=185°，φ=17°；3序列(3-a、3-b、3-c)視角參數(shù)為θ=163°，φ=79°；a序列(1-a、2-a、3-a)為SuperMap Desktop的效果圖、b序列(1-b、2-b、3-b)為直接配置注記的ArcScene的效果圖；c序列(1-c、2-c、3-c)為經(jīng)本算法優(yōu)化配置注記的效果圖。

圖9 多視角、多平臺三維注記配置對照效果圖Fig.9 Multi-views, multi-platforms 3D annotation placement contrast effect chart

經(jīng)統(tǒng)計(jì)各對照組的注記信息丟失數(shù)量(T1)、視線方向上三維注記遮擋其他三維注記數(shù)量(T2)、視線方向上三維注記遮擋要素?cái)?shù)量(T3)，調(diào)用式(2)計(jì)算得注記質(zhì)量評價(jià)值(E)，如表2所示。結(jié)合表2，以視角場景為橫軸、E為縱軸，繪制各平臺在多視角下的質(zhì)量值變化折線圖，如圖10所示。

表2 多視角、多平臺對照組質(zhì)量統(tǒng)計(jì)表
Tab.2 Multi-views, multi-platforms contrast group quality statistics table

序號試驗(yàn)編號T1T2T3E11-a130424.2421-b0151918.7831-c021051.2842-a801030.3052-b0131820.7362-c021150.0073-a1801317.5483-b0242612.9993-c001262.50

對照組分析得，本算法(c)在各視角下的三維注記質(zhì)量值均優(yōu)于SuperMap Desktop(a)、ArcScene(b)的三維注記質(zhì)量值，說明本文算法具備普適性和優(yōu)化性。采用((value1-value2)/value2)100%計(jì)算質(zhì)量提升比重，在視角1下，本算法(c)相對SuperMap Desktop(a)、ArcScene(b)三維注記質(zhì)量分別提升111%、173%；在視角2下，本算法(c)相對SuperMap Desktop(a)、ArcScene(b)三維注記質(zhì)量分別提升65%、141%；在視角3下，本算法(c)相對SuperMap Desktop(a)、ArcScene(b)三維注記質(zhì)量分別提升256%、381%；綜合各視角，本算法(c)相對SuperMap Desktop(a)、ArcScene(b)三維注記質(zhì)量平均提升144%、232%。以視角2為例，在J671、J670處，2-a存在三維注記信息丟失，2-c無注記信息丟失；2-b存在密集的三維注記遮擋，2-c僅存在三維注記遮擋要素，三維注記信息仍清晰可辨。綜上試驗(yàn)對比可證，本文提出的三維點(diǎn)要素注記優(yōu)化配置算法符合“注記信息不丟失、視線方向上注記遮擋盡量少”的配置目標(biāo)，具備普適性和優(yōu)化性。

圖10 各平臺在多視角下的質(zhì)量值變化折線圖Fig.10 The variation of the quality value of each platform in the multi-views

5 結(jié) 論

本文歸納了三維注記配置的內(nèi)容、位置及方法，并依據(jù)三維注記配置目標(biāo)確立了三維注記質(zhì)量評價(jià)函數(shù)，設(shè)計(jì)的點(diǎn)要素三維注記優(yōu)化配置算法實(shí)現(xiàn)了在小規(guī)模地理場景中三維注記優(yōu)化配置，符合“信息不丟失，視線方向上注記遮擋盡量少”的配置目標(biāo)。算法的創(chuàng)新在于將啟發(fā)式組合優(yōu)化算法引入地理場景的三維注記配置中。經(jīng)試驗(yàn)對比，驗(yàn)證了算法具備多視角普適性，且算法在小規(guī)模地理場景配置三維注記的效果優(yōu)于現(xiàn)行的GIS平臺的效果。值得指出的是，本算法目前注重配置效果，但在大規(guī)模地理場景應(yīng)用上仍受限于啟發(fā)式組合優(yōu)化算法的求解效率，下一步研究動(dòng)向?yàn)椋翰捎肎PU進(jìn)行GA運(yùn)算，以加速算法求解，從而拓展算法至大規(guī)模地理場景，如： GRID算法并行、基于 “島”的GA算法。此外，三維注記質(zhì)量評價(jià)函數(shù)可引入遮擋嚴(yán)重程度評價(jià)指標(biāo)，以進(jìn)一步優(yōu)化評價(jià)效果。

[1] CHEN Chen, ZHANG Liqiang, MA Jingtao, et al. Adaptive Multi-resolution Labeling in Virtual Landscapes[J]. International Journal of Geographical Information Science, 2010, 24(6): 949-964.

[2] 喬占明, 閆浩文.地圖標(biāo)注和地圖注記的探討[J]. 測繪與空間地理信息, 2011, 34(1): 205-207. QIAO Zhanming, YAN Haowen. Discussion on Map Labeling and Map Annotation[J]. Geomatics and Spatial Information Technology, 2011, 34(1): 205-207.

[3] RIBEIRO G M, LORENA L A N. Lagrangean Relaxation with Clusters for Point-feature Cartographic Label Placement Problems[J]. Computers & Operations Research, 2008, 35(7): 2129-2140.

[4] PEREIRA G S, NOGUEIRA LORENA L A, MATTOS RIBEIRO G. A Constructive Genetic Algorithm for Discrete Dispersion on Point Feature Cartographic Label Placement Problems[J]. Geographical Analysis, 2016, 48(1): 43-58.

[5] RABELLO R L, MAURI G R, RIBEIRO G M, et al. A Clustering Search Metaheuristic for the Point-Feature Cartographic Label Placement Problem[J]. European Journal of Operational Research, 2014, 234(3): 802-808.

[6] 王昭, 吳中恒, 費(fèi)立凡, 等. 基于幾何信息熵的面狀要素注記配置[J]. 測繪學(xué)報(bào), 2009, 38(2): 183-188. DOI: 10.3321/j.issn:1001-1595.2009.02.015. WANG Zhao, WU Zhongheng, FEI Lifan, et al. Automatic Name Placement of Area Feature: A Metric Information Approach[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(2): 183-188. DOI: 10.3321/j.issn:1001-1595.2009.02.015.

[7] 張志軍, 李霖, 于忠海, 等. 散列式面狀注記自動(dòng)配置技術(shù)研究[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2011, 36(6): 739-742. ZHANG Zhijun, LI Lin, YU Zhonghai, et al. Auto-Labeling of Hash Anea Features[J]. Geomatics and Information Science of Wuhan University, 2011, 36(6): 739-742.

[8] 張志軍. 基于規(guī)則引擎的地圖注記自動(dòng)配置方法研究[D]. 武漢: 武漢大學(xué), 2011. ZHANG Zhijun. Research on Automatic Label Placement Based on Rules-Engine[D]. Wuhan: Wuhan University, 2011.

[9] 吳長彬, 閭國年, 劉昱君. 基于規(guī)則庫和網(wǎng)格算法的土地利用現(xiàn)狀圖自動(dòng)數(shù)字注記[J]. 測繪學(xué)報(bào), 2008, 37(2): 250-255. DOI: 10.3321/j.issn:1001-1595.2008.02.021. WU Changbin, LU Guonian, LIU Yujun. Automated Numeric Placement for Land Utilization Map Based on Rule Database and Grid Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2): 250-255. DOI: 10.3321/j.issn:1001-1595.2008.02.021.

[10] RYLOV M A,REIMER A W. Improving Label Placement Quality by Considering Basemap Detail with a Raster-based Approach[J]. Geoinformatica, 2015, 19(3): 463-486.

[11] MAASS S, D?LLNER J. Dynamic Annotation of Interactive Environments Using Object-integrated Billboards[C]∥Proceedings of the 14th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision. Plzen, Czech Republic: WSCG, 2006: 327-334.

[12] MAASS S, DüLLNER J. Embedded Labels for Line Features in Interactive 3D Virtual Environments[C]∥Proceedings of the 5th International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa. New York, NY, USA: ACM, 2007: 53-59.

[13] VAARANIEMI M, FREIDANK M, WESTERMANN R. Enhancing the Visibility of Labels in 3D Navigation Maps[M]∥POULIOT J, DANIEL S, HUBERT F, et al. Progress and New Trends in 3D Geoinformation Sciences. Berlin Heidelberg: Springer, 2013: 23-40.

[14] VAARANIEMI M,TREIB M, WESTERMANN R. Temporally Coherent Real-time Labeling of Dynamic Scenes[C]∥Proceedings of the 3rd International Conference on Computing for Geospatial Research and Applications. New York, NY, USA: ACM, 2012: 17.

[15] PRADO R D, RAPOSO A B. Real-time Label Visualization in Massive CAD Models[C]∥Proceedings of 2013 International Conference on Computer-aided Design and Computer Graphics. Guangzhou, China: IEEE, 2013: 337-344.

[16] 楊乃. 基于空間認(rèn)知的三維地圖設(shè)計(jì)若干問題的研究[D]. 武漢: 武漢大學(xué), 2010. YANG Nai. Study on Several Issues of 3D Map Design Based on Spatial Cognition[D]. Wuhan: Wuhan University, 2010.

[17] 胡斌, 江南, 鄒志強(qiáng), 等. 大規(guī)模室外動(dòng)態(tài)場景調(diào)度機(jī)制研究[J]. 地球信息科學(xué), 2007, 9(5): 8-13. HU Bin, JIANG Nan, ZOU Zhiqiang, et al. Research on Dispatch of Dynamic Scene in Large Scope Outdoor Environment[J]. Geo-information Science, 2007, 9(5): 8-13.

[18] RIBEIRO G M, LORENA L A N. Heuristics for Cartographic Label Placement Problems[J]. Computers & Geosciences, 2006, 32(6): 739-748.

[19] STRIJK T, VERWEIJ B, AARDAL K. Algorithms for Maximum Independent Set Applied to Map Labelling[J]. Utrecht: Department of Computer Science, Utrecht University, 2000.

[20] 樊紅, 張祖勛, 杜道生. 地圖注記質(zhì)量評價(jià)模型的研究[J]. 測繪學(xué)報(bào), 2004, 33(4): 362-366. DOI: 10.3321/j.issn:1001-1595.2004.04.016. FAN Hong, ZHANG Zuxun, DU Daosheng. The Study of the Evaluation Model for Map Labeling[J]. Acta Geodaetica et Cartographica Sinica, 2004, 33(4): 362-366. DOI: 10.3321/j.issn:1001-1595.2004.04.016.

[21] PITTEWAY M L V, WATKINSON D J. Bresenham’s Algorithm with Grey Scale[J]. Communications of the ACM, 1980, 23(11): 625-626.

[22] ?ALIK B, KOLINGEROVA I. A Cell-based Point-in-polygon Algorithm Suitable for Large Sets of Points[J]. Computers & Geosciences, 2001, 27(10): 1135-1145.

[23] CHRISTENSEN J,MARKS J, SHIEBER S. An Empirical Study of Algorithms for Point-feature Label Placement[J]. ACM Transactions on Graphics, 1995, 14(3): 203-232.

[24] 史云飛, 郭仁忠, 李霖, 等. 四維地籍的建立與分析[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2014, 39(3): 322-326. SHI Yunfei,GUO Renzhong, LI Lin, et al. Establishment and Analysis of 4D Cadastre[J]. Geomatics and Information Science of Wuhan University, 2014, 39(3): 322-326.

(責(zé)任編輯：宋啟凡)

A 3D Annotation Optimal Placement Algorithm for the Point Features in the Small Scale Geographic Scene

ZHOU Xinxin，WU Changbin，SUN Zaihong，DING Yuan，HE Tao

Key Laboratory of Virtual Geographic Environment, Ministry of Education,Nanjing Normal University, Nanjing 210046,China

The 3D annotations placement rules of point features in geographic scene are “obscured then not showing” and “obscured then directly showing” normally. The defects of those rules are annotation information lost or large numbers of occlusion, so their universalities are not strong and they are not suitable for the annotation placement of small-scaled geographic scene. This paper summarizes the contents, position and placement methods of 3D annotation and takes the aim at “not loss of annotation information and less annotation obscured as far as possible” of the research problem of the annotation placement of small-scaled geographic scene. The configuration rule of 3D annotation Identifies as “obscured then optimized to display”. The designed algorithm based on the perspective transformation matrix, the inverse perspective transformation matrix and the grid algorithm takes the genetic algorithm (GA) whose fitness evaluation function uses the 3D Annotation quality evaluation function as the core to realize the feasible optimal solution of 3D annotations of point features in geographic scene. By the multi-views, multi-platforms contrast experiment, this algorithm is applicable for multi-views 3D annotation placement widely. The 3D annotation effect is better than mainstream GIS platforms (such as SuperMap desktop, ArcScene), which assumes that the algorithm’s 3D annotation quality value is relatively increased 144%, 232%. The algorithm fits in with the target configuration.

geographic scene；3D annotation;3D annotation placement；genetic algorithm；3D annotation quality evaluation function；GRID algorithm

The National Natural Science Foundation of China (No. 41471318)

ZHOU Xinxin(1991—), male, master, majors in 3D cadastre and cartography.

WU Changbin

周鑫鑫，吳長彬，孫在宏，等.小規(guī)模地理場景中點(diǎn)要素三維注記優(yōu)化配置算法[J].測繪學(xué)報(bào)，2016,45(12)：1476-1484.

10.11947/j.AGCS.2016.20160210. ZHOU Xinxin，WU Changbin，SUN Zaihong，et al.A 3D Annotation Optimal Placement Algorithm for the Point Features in the Small Scale Geographic Scene[J]. Acta Geodaetica et Cartographica Sinica,2016,45(12):1476-1484. DOI:10.11947/j.AGCS.2016.20160210.

P208

A

1001-1595(2016)12-1476-09

國家自然科學(xué)基金(41471318)

2016-05-03

周鑫鑫(1991—)，男，碩士，研究方向?yàn)槿S地籍及地圖制圖。

E-mail：windofmay@foxmail.com

吳長彬

E-mail：wuchangbin@njnu.edu.cn

修回日期：2016-10-11