小规模地理场景中点要素三维注记优化配置算法

周鑫鑫，吴长彬，孙在宏，丁 远，贺 涛

南京师范大学虚拟地理环境教育部重点实验室，江苏 南京 210046

小规模地理场景中点要素三维注记优化配置算法

周鑫鑫，吴长彬，孙在宏，丁 远，贺 涛

南京师范大学虚拟地理环境教育部重点实验室，江苏 南京 210046

地理场景中点要素三维注记配置规则多为“遮挡则不显示”和“遮挡直接显示”，该类规则的缺陷是注记信息丢失或存在大量遮挡，普适性不强，尤其不适用于小规模地理场景点要素三维注记配置。本文首先归纳了三维注记绘制的内容、位置及方法，并针对小规模地理场景点要素三维注记配置问题，以“信息不丢失、注记尽可能少的遮挡”为配置目标，配置规则为“遮挡后优化并显示”。算法以透视变换矩阵、逆透视变换矩阵及GRID算法为基础，以遗传算法为核心，以三维注记质量评价函数为遗传算法适应度评价函数，实现点要素三维注记的可行最优解求解。经多视角、多平台对照试验可知，本算法适用于多视角三维注记优化配置，具备普适性；与主流GIS平台(SuperMap Desktop、ArcScene)的三维注记配置效果作对比，本算法三维注记质量值分别相对提升144%、232%，符合配置目标。

地理场景；三维注记；三维注记配置；遗传算法；注记质量评价函数；GRID算法

三维注记配置属于三维地理环境图形化表达中的语义信息表达研究范畴[1]。语义信息表达是采用文字、符号直观展现地物属性值，如：道路名称、建筑物名称等。注记(annotation)，或称标注(label)，是语义信息表达的直接方式，也是地图语言的重要组成部分[2]。以数据维度为标准，注记配置分为二维注记配置、三维注记配置。目前，二维注记配置研究较多，根据要素维度划分为0维、一维、二维，其中，0维地理要素的二维注记配置以优化算法研究为主，如：物理松弛法[3]、遗传算法[4]、聚类搜索算法[5]，一维、二维地理要素的二维注记配置以注记候选位置计算研究为主，如：熵心定位[6]、散列式定位[7]，此外，地图注记引擎[8]、地图注记规则库[9]、影像的注记配置[10]也得到了广泛研究。三维注记配置是对二维注记配置的维度拓展，二维的研究理论适用于三维，但三维注记配置更为复杂，表现为：渲染量大、显示呈现“近大远小”、多视角等。三维注记配置处于研究发展期，以研究注记生成过程、注记优化方法、GPU加速计算为重[11-16]。

不同数据体量的地理场景，其加载机制、渲染机制、内存控制、语义信息表达机制有本质差异。大规模地理场景数据多采用分块索引加载渲染机制，按需加载，避免内存超负荷，如数据调度流水线方法[17]，软件平台如ArcGlobe平台；小规模地理场景数据一般采用直接加载渲染机制，避免频繁的调用数据进入内存，软件平台如ArcScene平台。不同规模地理场景的注记渲染方式和优化方式不同，大规模地理场景多采用屏幕空间的注记(screen space annotation)，小规模地理场景一般采用基于对象空间的注记(object space annotation)[12]。

1 小规模地理场景中的注记

小规模地理场景中点要素三维注记配置需解决3个问题：绘制内容、绘制位置及如何绘制。综述，三维注记配置研究处于发展期，其优化方法简单。将二维注记的优化配置算法推广至三维注记配置研究中，成为本文研究内容。

1.1 注记绘制内容

影响三维注记内容展示的因素有：注记文字内容、注记视觉变量、场景视觉变量。注记文字内容是指显示的属性内容，分为说明注记和名称注记两种。注记视觉变量指注记元素本身的各项属性设置，总结为9种：字体、字号、字色、字型、字列、字隔、字向、外框、图标，其样式如图1所示。场景视觉变量包括：光源、地图背景、垂直夸张度、观察视野等。观测视野的设置包括观测点坐标设置、目标点坐标设置、视距设置、视角设置、相机的方位角(azimuth angle)、倾角(inclination angle)设置等。

图1 三维注记视觉变量样式图Fig.1 Visual variables pattern of 3D annotation

1.2 注记绘制位置

三维注记因绘制位置的差异，可分为：①贴于三维模型表面栅格纹理，见图2(a)；②触发后弹出框式，见图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 注记绘制方法

从三维注记发生视觉上遮挡则的优化策略进

行划分，分为遮挡则直接显示、遮挡则优化并显示及遮挡则不显示，3种情况各有优缺点且其适用的范畴各不相同。举例示意，图4(a)为遮挡则直接显示，图4(b)为遮挡则优化并显示，图4(c)为遮挡则不显示。

遮挡则直接显示，缺点明显，要素增多后传递的语义信息急剧下降。遮挡则优化，采用注记优化配置算法计算，得到该视角下可行解，其与PFCLP问题中的MNCFLP[18]和MNCP[3]两种策略相一致，其优点是信息无丢失，语义信息完整，适用于小规模的地理场景。遮挡则不显示，采用深度检测剔除该视角下深度大且被压盖的注记，其与PFCLP问题的MISP策略[19]相一致，其优点是简洁，但缺点是信息丢失。表1对3种方式的概念、优化策略、优缺点、适用范畴进行了总结。

图4 注记遮挡后优化策略示意图Fig.4 Schematic diagram of the optimal strategies for post annotation occlusion

表1 注记遮挡后优化策略对比表Tab.1 Comparison of the optimal strategies for post annotation occlusion

2 注记配置规则

小规模地理场景中点要素三维注记配置采用基于对象空间的注记，注记遮挡后的优化策略为遮挡则优化，从而确保“注记信息不丢失、视线方向上注记遮挡尽量少”。

2.1 三维注记待选方位

小规模地理场景中点要素的注记待选方位选用三维空间中的与视线方向垂直面上的四方位待选注记方案。假设观察者的方位角和倾角为(θ,φ)，三维点要素P(x,y,z)，三维注记尺寸为(w,h)，如图5所示，则四方位三位注记框中心点Pi的计算见式(1)

(1)

图5 三维点要素四方位待选注记方案示意图Fig.5 The 4 propositions annotation scheme of 3D point feature

2.2 三维注记质量评价函数

实现“注记信息不丢失、视线方向上注记遮挡尽量少”的配置目标，需定量化为三维注记质量评价函数，评价函数的设计直接影响注记的质量[20]。注记质量评价函数需符合：注记丢失个数越少函数值越大；注记遮挡越少函数值越大的设计原则；当注记发生丢失时，则丢失注记不会发生注记遮挡，两者具备互斥性。本文提出小规模地理场景三维注记质量评价函数E，E是E(i)的总和，见式(2)，E(i)表示第i个注记的质量值。E(i)由评价子函数组成，如式(3)所示。顾及三维点要素四方位待选注记方案中，各方位与要素关联性相同、优先级视为一致，故E(i)未将注记与要素关联性、注记方位优先级纳入子函数范畴

(2)

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

(3)

3 算法设计

三维点要素注记优化配置算法是一种三维注记在视线方向上发生遮挡后进行优化后重新配置注记位置的算法。该算法由二三维坐标系变换、GRID算法、遗传算法(geneticalgorithm，GA)、注记质量评价函数组成，相互关系是：二三维坐标系变换和GRID算法是计算基础；用于求解的遗传算法是核心；三维注记质量评价函数是遗传算法适应度计算公式，各模块组合关系如图6所示。

3.1 整体流程

三维点要素注记优化配置算法的设计流程由6步组成，具体流程如下。

第1步：输入三维要素点集、三维待选注记框中心点集矩阵，记为Vwcs。

第2步：透视变换。透视变换是获得透视图像的方法，可以运用于要素、待选注记框的透视后坐标集合Vdcs计算，透视变换矩阵如式(4)所示。Mmv为模型视点矩阵，变换后得到相机坐标系；Mp为投影矩阵，得到投影坐标系；Mw窗口变换矩阵，得到设备坐标系

Vdcs=Vwcs×Mmv×Mp×Mw

(4)

注:R为Camera视点到世界坐标系原点距离；θ为方位角(azimuth)，θ∈[0°，360°]；φ为倾斜角(inclination)，φ∈[-90°，360°]；D表示Camera视点到屏幕坐标系原点的距离；w表示设备宽度；h表示设备的高度。

图6 三维注记优化配置算法结构图Fig.6 The structure of 3D annotation optimal placement algorithm

第3步：采用GRID算法进行基础网格构建。基础网格是判别注记间压盖、注记与要素间冲突的快速方式。GRID算法包括：网格初始化、网格更新、网格读取3个算子。其中，网格初始化算子是实现要素网格化的方法集合，点要素直接网格化，线要素可采用Bresenham算法[21]等，面要素可采用点在面内算法[22]进行网格化，完成初始化，得到要素网格(GRIDFea)，样式如图7所示。网格更新算子，涉及已知坐标点(x,y)，求解网格行列号(row,col)，计算见式(5)。网格读取算子，已知网格行列号(row,col)，求解坐标点(x,y)，计算公式见式(6)。

图7 要素网格化效果图Fig.7 Effect scheme of feature meshed

(5)

(6)

式中，cellsize为网格单元尺寸；ymax是指所有要素的最大外包络框的y最大值；xmin为所有二维屏幕要素的最大外包络框的x最小值。

第4步：GA算法进行最优组合解计算。GA算法是启发式算法的一种，以广泛运用于二维注记配置、TSP问题求解。其中，GA算法选择算子的适应度评价方法采用注记质量评价函数(E)。经初始化、选择算子、交叉算子及变异算子计算后，得到结果解。

第5步：逆透视变换。逆透视变换是将计算得到的二维注记结果解转换为三维注记，是透视变换的逆过程。逆透视变换公式如式(7)所示

(7)

第6步：输出注记结果。将注记结果绘制于地理场景中。

3.2 核心算法

GA算法是模拟生物遗传机制而形成的解决复杂组合优化问题的算法[23]。基本遗传算法实现步骤是：①初始化形成初始种群；②基于适应度函数对个体符号串进行评价；③执行遗传操作生成一个新的符号串群体；重复第②、③步直到算法终止。遗传操作包括：选择算子、交叉算子及变异算子，遗传算法的关键在于染色体个体符号串的表示和遗传操作算子的设计。三维点要素注记配置的GA算法具体步骤如下：

步骤1：设置GA算法的基本参数和经透视变换后的待选注记框集合(ListProAnno)输入、要素网格基础(GRIDFea)输入。GA算法的基本参数设定：交叉概率(PC)、变异概率(PM)、种群规模(Popsize)、进化代数(Iteration)、染色体基因座数量(CountFea)、注记质量评价函数阈值(EValue)、基因上限值(MaxGene)、基因下限值(MinGene)。

步骤2：生成初始种群。当前代数(Pop)等于1，种群中染色体数量为Popsize，每个染色体的基因座数量CountFea。每个基因座基因值(ValueGene)确定为随机时间种子数，要求ValueGene∈{N*∩[MinGene,MaxGene]}。初始种群总体产生随机数的次数为Popsize*CountFea。

步骤3：评价种群各染色体的适应度值(E)。复制GRIDFea得到当前代的GRIDTemp，根据该染色体上各ValueGene找出对应的待选注记框集合中各要素的待选注记框(ProAnno)。在GRIDTemp基础上，对ProAnno进行网格化，网格信息记录于GRIDTemp中。各基因的适应度计算等价于E(Li)，染色体整体适应度计算等价于E。

步骤4：最优染色体选择与终止条件判别。保留种群中最优染色体及其适应度值，判别终止条件((E≥EValue)Or(Pop>Iteration))，符合则停止执行，该最优染色体为注记解；否则，执行步骤5。

步骤5：新一代种群生成。Pop自增1。调用赌轮盘算子进行父代的染色体选择。针对选择出得父本染色体与父本最优染色体进行交叉算子，选择对应基因位，采用单点交叉，若随机算子的概率值小于PC，即认为符合交叉条件，执行交叉。针对选择出得父本染色体进行变异算子，选择有冲突的基因位，若随机算子的概率值小于PM，则认为符合变异条件，执行变异。

步骤6：重新执行步骤3，直至符合步骤4的终止条件。

4 算法试验

4.1 试验环境与试验数据

系统硬件环境：CPU：Intel(R)Core(TM)i5-4590，内存：8GB，GPU：NVIDIA GeForce GT730；系统软件环境：操作系统：操作系统：Windows10 64Bit，编程环境：Visual Studio 2010，编程语言：C#，GIS平台：ESRI ArcObjects 10.2、SuperMap Desktop 8C。试验系统基于ArcScene Control实现各功能，ArcScene Control用于展示小规模三维不动产场景数据。主要功能包括：试验数据加载、三维坐标轴绘制、直接注记配置、注记优化算法配置、试验参数设置等。试验数据采用三维地籍产权体[24]中的三维宗地体作为试验数据，试验数据如图8所示。

图8 三维宗地体示意图Fig.8 Schematic diagram of 3D parcel

参数设置包括注记参数、网格参数、注记质量评价函数参数、遗传算法参数。注记参数： 8号、宋体。待选注记方位取四方位。网格参数：CellSize=0.1，CellValuePoint=1，CellValueLine= 10，CellValuePolygon=100， CellValueAnno= 1000。注记质量评价函数参数：∂=0.1、η=0.45、l=0.45，即认同在小规模地理场景中，注记丢失与注记遮挡其他注记的影响程度一致，次之是注记遮挡其他要素。遗传算法参数：Popsize=30，Iteration=50，PC=0.7，PM=0.1，EValue=30，MaxGene=4，MinGene=1，CountFea为三维点要素个数。

4.2 多视角、多平台对照试验

为验证算法在多视角、多平台上具备普适性和优化性，试验方法采用宗地体对象图8(a)，选具备代表性的GIS平台(ESRI的ArcScene平台、超图的SuperMap Desktop平台)作为对照组，设置多视角，进行三维界址点三维注记配置，对比配置效果。对照结果如图9所示，其中，1序列(1-a、1-b、1-c)视角参数为θ=90°，φ=10°；2序列(2-a、2-b、2-c)视角参数为θ=185°，φ=17°；3序列(3-a、3-b、3-c)视角参数为θ=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)为经本算法优化配置注记的效果图。

图9 多视角、多平台三维注记配置对照效果图Fig.9 Multi-views, multi-platforms 3D annotation placement contrast effect chart

经统计各对照组的注记信息丢失数量(T1)、视线方向上三维注记遮挡其他三维注记数量(T2)、视线方向上三维注记遮挡要素数量(T3)，调用式(2)计算得注记质量评价值(E)，如表2所示。结合表2，以视角场景为横轴、E为纵轴，绘制各平台在多视角下的质量值变化折线图，如图10所示。

表2 多视角、多平台对照组质量统计表
Tab.2 Multi-views, multi-platforms contrast group quality statistics table

序号试验编号T1T2T3E11-a130424.2421-b0151918.7831-c021051.2842-a801030.3052-b0131820.7362-c021150.0073-a1801317.5483-b0242612.9993-c001262.50

对照组分析得，本算法(c)在各视角下的三维注记质量值均优于SuperMap Desktop(a)、ArcScene(b)的三维注记质量值，说明本文算法具备普适性和优化性。采用((value1-value2)/value2)100%计算质量提升比重，在视角1下，本算法(c)相对SuperMap Desktop(a)、ArcScene(b)三维注记质量分别提升111%、173%；在视角2下，本算法(c)相对SuperMap Desktop(a)、ArcScene(b)三维注记质量分别提升65%、141%；在视角3下，本算法(c)相对SuperMap Desktop(a)、ArcScene(b)三维注记质量分别提升256%、381%；综合各视角，本算法(c)相对SuperMap Desktop(a)、ArcScene(b)三维注记质量平均提升144%、232%。以视角2为例，在J671、J670处，2-a存在三维注记信息丢失，2-c无注记信息丢失；2-b存在密集的三维注记遮挡，2-c仅存在三维注记遮挡要素，三维注记信息仍清晰可辨。综上试验对比可证，本文提出的三维点要素注记优化配置算法符合“注记信息不丢失、视线方向上注记遮挡尽量少”的配置目标，具备普适性和优化性。

图10 各平台在多视角下的质量值变化折线图Fig.10 The variation of the quality value of each platform in the multi-views

5 结 论

本文归纳了三维注记配置的内容、位置及方法，并依据三维注记配置目标确立了三维注记质量评价函数，设计的点要素三维注记优化配置算法实现了在小规模地理场景中三维注记优化配置，符合“信息不丢失，视线方向上注记遮挡尽量少”的配置目标。算法的创新在于将启发式组合优化算法引入地理场景的三维注记配置中。经试验对比，验证了算法具备多视角普适性，且算法在小规模地理场景配置三维注记的效果优于现行的GIS平台的效果。值得指出的是，本算法目前注重配置效果，但在大规模地理场景应用上仍受限于启发式组合优化算法的求解效率，下一步研究动向为：采用GPU进行GA运算，以加速算法求解，从而拓展算法至大规模地理场景，如： GRID算法并行、基于 “岛”的GA算法。此外，三维注记质量评价函数可引入遮挡严重程度评价指标，以进一步优化评价效果。

[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] 乔占明, 闫浩文.地图标注和地图注记的探讨[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] 王昭, 吴中恒, 费立凡, 等. 基于几何信息熵的面状要素注记配置[J]. 测绘学报, 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] 张志军, 李霖, 于忠海, 等. 散列式面状注记自动配置技术研究[J]. 武汉大学学报(信息科学版), 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] 张志军. 基于规则引擎的地图注记自动配置方法研究[D]. 武汉: 武汉大学, 2011. ZHANG Zhijun. Research on Automatic Label Placement Based on Rules-Engine[D]. Wuhan: Wuhan University, 2011.

[9] 吴长彬, 闾国年, 刘昱君. 基于规则库和网格算法的土地利用现状图自动数字注记[J]. 测绘学报, 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] 杨乃. 基于空间认知的三维地图设计若干问题的研究[D]. 武汉: 武汉大学, 2010. YANG Nai. Study on Several Issues of 3D Map Design Based on Spatial Cognition[D]. Wuhan: Wuhan University, 2010.

[17] 胡斌, 江南, 邹志强, 等. 大规模室外动态场景调度机制研究[J]. 地球信息科学, 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] 樊红, 张祖勋, 杜道生. 地图注记质量评价模型的研究[J]. 测绘学报, 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]. 武汉大学学报(信息科学版), 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.

(责任编辑：宋启凡)

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

周鑫鑫，吴长彬，孙在宏，等.小规模地理场景中点要素三维注记优化配置算法[J].测绘学报，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

国家自然科学基金(41471318)

2016-05-03

周鑫鑫(1991—)，男，硕士，研究方向为三维地籍及地图制图。

E-mail：windofmay@foxmail.com

吴长彬

E-mail：wuchangbin@njnu.edu.cn

修回日期：2016-10-11