留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于可移动区域的点状要素注记配置

李霖 张航 朱海红 胡玮

李霖, 张航, 朱海红, 胡玮. 基于可移动区域的点状要素注记配置[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1129-1137. doi: 10.13203/j.whugis20160289
引用本文: 李霖, 张航, 朱海红, 胡玮. 基于可移动区域的点状要素注记配置[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1129-1137. doi: 10.13203/j.whugis20160289
LI Lin, ZHANG Hang, ZHU Haihong, HU Wei. A Point-Feature Labeling Algorithm Based on Movable Regions[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1129-1137. doi: 10.13203/j.whugis20160289
Citation: LI Lin, ZHANG Hang, ZHU Haihong, HU Wei. A Point-Feature Labeling Algorithm Based on Movable Regions[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1129-1137. doi: 10.13203/j.whugis20160289

基于可移动区域的点状要素注记配置

doi: 10.13203/j.whugis20160289
基金项目: 

国家自然科学基金 41271453

中央高校基本科研业务费专项 2012205020211

详细信息
    作者简介:

    李霖, 博士, 教授, 主要从事数字地图制图、空间数据模型、地理本体、地理信息可视化等方面的研究。lilin@whu.edu.cn

  • 中图分类号: P208;P283

A Point-Feature Labeling Algorithm Based on Movable Regions

Funds: 

The National Natural Science Foundation of China 41271453

the Fundamental Research Funds for the Central Universities 2012205020211

More Information
    Author Bio:

    LI Lin, PhD, professor, specializes in computer aided cartography, spatial data model, geographic ontology, and geovisuali-zation. E-mail: lilin@whu.edu.cn

  • 摘要: 注记候选位置的确定是注记配置的重要基础,直接影响到注记算法的实现方式和最终配置效果。现有注记研究广泛使用的注记模型,其候选位置未充分利用图面空间,一定程度上制约了注记效果的进一步提升。在此背景下,提出注记候选区域模型,以要素邻域内所有无冲突压盖的候选区域作为注记配置基础,在考虑点、线、面要素压盖的前提下完成点注记配置。同其他研究相比,该算法在注记结果上取得较大提高,能更好地满足地图生产需要。
  • 图  1  可移动区域描述示意图

    Figure  1.  Diagram of Movability Region

    图  2  引理1示意图

    Figure  2.  Schematic Diagram of Lemma One

    图  3  Minkowski加法示意图

    Figure  3.  Schematic Diagram of Minkowski Addition

    图  4  注记候选区域生成流程图

    Figure  4.  Generation Process of Candidate Label Region

    图  5  注记候选位置生成示意图

    Figure  5.  Schematic Diagram of Candidate Label Position Generation

    图  6  注记候选位置生成示例

    Figure  6.  Cases of Candidate Label Positions Generation

    图  7  不同注记顺序的结果示意图

    Figure  7.  Labeling Cases for Different Labeling Orders

    图  8  不同注记顺序的无冲突压盖注记比例对比图

    Figure  8.  Conflict-Free Label Proportions with Different Labeling Orders

    图  9  不同注记算法的无冲突压盖注记比例对比图

    Figure  9.  Conflict-Free Label Proportions with Different Labeling Algorithms

    图  10  候选区域注记结果

    Figure  10.  Labeling Result of Candidate Region

    图  11  滑动模型注记结果

    Figure  11.  Labeling Result of Slider Model

    图  12  固定位置模型注记结果

    Figure  12.  Labeling Result of Fixed-Position Model

    图  13  2 000个点要素的注记结果对比图

    Figure  13.  Comparison of Labeling Results for 2 000 Point Features

    表  1  不同注记顺序的无冲突压盖注记数目对比统计表

    Table  1.   Statistical Table for the Conflict-Free Label Counts with Different Labeling Orders

    要素数目 面积值由大到小 随机顺序1 随机顺序2 随机顺序3 面积值由小到大
    注记数目 注记比例/% 注记数目 注记比例/% 注记数目 注记比例/% 注记数目 注记比例/% 注记数目 注记比例/%
    500 498.30 99.66 498.50 99.70 499.60 99.92 500.00 100.00 500.00 100.00
    1000 979.30 97.93 989.00 98.90 990.60 99.06 991.50 99.15 999.30 99.93
    1 500 1 414.40 94.29 1 453.70 96.91 1 451.20 96.75 1 451.20 96.75 1 492.20 99.48
    2 000 1 784.60 89.23 1 859.50 92.98 1 869.60 93.48 1 857.40 92.87 1 975.40 98.77
    2 500 2 045.60 81.82 2 183.60 87.34 2 186.10 87.44 2 174.30 86.97 2 409.20 96.37
    3 000 2 220.20 74.01 2 387.00 79.57 2 408.70 80.29 2 402.40 80.08 2 796.70 93.22
    3 500 2 283.60 65.25 2 496.90 71.34 2 521.90 72.05 2 508.90 71.68 3 079.80 87.99
    4 000 2 271.10 56.78 2 495.60 62.39 2 506.00 62.65 2 509.10 62.73 3 270.10 81.75
    4 500 2 161.70 48.04 2 425.64 53.90 2 409.60 53.55 2 408.20 53.52 3 357.10 74.60
    5 000 2 052.70 41.05 2 264.10 45.28 2 237.20 44.74 2 248.40 44.97 3 386.80 67.74
    下载: 导出CSV

    表  2  不同注记算法的无冲突压盖注记数目对比统计表

    Table  2.   Statistical Table for the Conflict-Free Label Counts with Different Labeling Algorithms

    要素数目 候选区域注记 固定位置模型注记 滑动模型注记
    注记数目 注记比例/% 注记数目 注记比例/% 数目差值 比例差值/% 注记数目 注记比例/% 数目差值 比例差值/%
    100 74.70 74.70 46.90 46.90 27.80 27.80 62.20 62.20 12.50 12.50
    200 150.40 75.20 91.00 45.50 59.40 29.70 123.90 61.95 26.50 13.25
    300 220.50 73.50 133.60 44.53 86.90 28.97 185.00 61.67 35.50 11.83
    400 292.80 73.20 176.50 44.13 116.30 29.08 240.60 60.15 52.20 13.05
    500 363.70 72.74 223.00 44.60 140.70 28.14 297.80 59.56 65.90 13.18
    600 430.00 71.67 256.80 42.80 173.20 28.87 351.40 58.57 78.60 13.10
    700 497.90 71.13 303.00 43.29 194.90 27.84 411.90 58.84 86.00 12.29
    800 556.10 69.51 329.30 41.16 226.80 28.35 451.40 56.43 104.70 13.09
    900 619.10 68.79 364.50 40.50 254.60 28.29 509.60 56.62 109.50 12.17
    1 000 682.20 68.22 403.50 40.35 278.70 27.87 559.70 55.97 122.50 12.25
    1 100 739.90 67.26 436.00 39.64 303.90 27.63 606.70 55.15 133.20 12.11
    1 200 797.20 66.43 471.80 39.32 325.40 27.12 654.30 54.53 142.90 11.91
    1 300 843.80 64.91 487.90 37.53 355.90 27.38 686.20 52.78 157.60 12.12
    1 400 898.30 64.16 519.40 37.10 378.90 27.06 733.10 52.36 165.20 11.80
    1 500 945.70 63.05 544.60 36.31 401.10 26.74 783.40 52.23 162.30 10.82
    1 600 996.00 62.25 577.00 36.06 419.00 26.19 821.90 51.37 174.10 10.88
    1 700 1 039.70 61.16 594.20 34.95 445.50 26.21 849.10 49.95 190.60 11.21
    1 800 1 079.60 59.98 612.40 34.02 467.20 25.96 881.90 48.99 197.70 10.98
    1 900 1 125.60 59.24 632.70 33.30 492.90 25.94 938.70 49.41 186.90 9.84
    2 000 1 165.90 58.30 653.30 32.67 512.60 25.63 963.30 48.17 202.60 10.13
    下载: 导出CSV
  • [1] Iturriaga C, Lubiw A. NP-hardness of Some Map Labeling Problems[M]. Waterloo:University of Waterloo, Canada, 1997
    [2] Marks J, Shieber S M. The Computational Comple-xity of Cartographic Label Placement[OL]. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8844,1991
    [3] 吴长彬, 闾国年, 刘昱君.基于规则库和网格算法的土地利用现状图自动数字注记[J].测绘学报, 2008, 37(2):250-255 http://industry.wanfangdata.com.cn/dl/Detail/Periodical?id=Periodical_chxb200802021

    Wu Changbin, Lv Guonian, Liu Yujun. Automated Numeric Placement for Land Utilization Map Based on Rule Data Base and Grid Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2):250-255 http://industry.wanfangdata.com.cn/dl/Detail/Periodical?id=Periodical_chxb200802021
    [4] 张志军, 李霖, 于忠海, 等.散列式面状注记自动配置技术研究[J].武汉大学学报·信息科学版, 2011, 36(6):739-742 http://ch.whu.edu.cn/CN/abstract/abstract568.shtml

    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 http://ch.whu.edu.cn/CN/abstract/abstract568.shtml
    [5] 王昭, 吴中恒, 费立凡, 等.基于几何信息熵的面状要素注记配置[J].测绘学报, 2015, 38(2):183-188 doi:  10.11947/j.AGCS.2015.20130737

    Wang Zhao, Wu Zhongheng, Fei Lifan, et al. Automatic Name Placement of Area Feature:A Metric Information Approach[J]. Acta Geodaetica et Cartographica Sinica, 2015, 38(2):183-188 doi:  10.11947/j.AGCS.2015.20130737
    [6] Edmondson S, Christensen J, Marks J, et al. A Gene-ral Cartographic Labeling Algorithm[J]. Cartographica the International Journal for Geographic Information & Geovisualization, 2010, 33(4):13-24 https://sdm.lbl.gov/~kewu/ps/LBNL-59102.pdf
    [7] Wolff A, Strijk T. The Map-Labeling Bibliography[OL]. http://i11www.ira.uka.de/map-labeling/bibliography,2005
    [8] Do Nascimento H A D, Eades P. User Hints for Map Labeling[J]. Journal of Visual Languages and Computing, 2008, 19(1):39-74 doi:  10.1016/j.jvlc.2006.03.004
    [9] Klau G W, Mutzel P. Optimal Labeling of Point Features in Rectangular Labeling Models[J]. Mathematical Programming, 2003, 94(2-3):435-458 doi:  10.1007/s10107-002-0327-9
    [10] van Kreveld M, Strijk T, Wolff A. Point Labeling with Sliding Labels[J]. Computational Geometry-Theory and Applications, 1999, 13(1):21-47 doi:  10.1016/S0925-7721(99)00005-X
    [11] Rylov M A, Reimer A W. Improving Label Placement Quality by Considering Basemap Detail with a Raster-Based Approach[J]. GeoInformatica, 2014, 19(3):463-486 doi:  10.1007/s10707-014-0214-6
    [12] 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 doi:  10.1016/j.ejor.2013.10.021
    [13] 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 doi:  10.1145/212332.212334
    [14] Raidl G R. A Genetic Algorithm for Labeling Point Features[OL]. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.3527,1998
    [15] Yamamoto M, Camara G, Lorena L A N. Tabu Search Heuristic for Point-Feature Cartographic Label Placement[J]. GeoInformatica, 2002, 6(1):77-90 doi:  10.1023/A:1013720231747
    [16] Schreyer M, Raidl G R. Letting Ants Labeling Point Features[C]. The 2002 Congress on Evolutionary Computation, Honolulu, USA, 2002
    [17] Ribeiro G M, Lorena L A N. Heuristics for Cartographic Label Placement Problems[J]. Computers & Geosciences, 2006, 32(6):739-748 doi:  10.1016/j.cageo.2005.10.004
    [18] Strijk T, van Kreveld M. Practical Extensions of Point Labeling in the Slider Model[J]. GeoInformatica, 2002, 6(2):181-197 doi:  10.1023/A:1015202410664
    [19] Schwartges N, Haunert J H, Wolff A, et al. Point Labeling with Sliding Labels in Interactive Maps[C]. 17th AGILE Conference on Geographic Information Science, Castellon, 2014
    [20] 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 doi:  10.1007/s10707-014-0214-6
    [21] 王志强, 洪嘉振, 杨辉.碰撞检测问题研究综述[J].软件学报, 1999, 10(5):545-551 http://www.cqvip.com/QK/91690X/200332/8605025.html

    Wang Zhiqiang, Hong Jiazhen, Yang Hui. A Survey of Collision Detection Problem[J]. Journal of Software, 1999, 10(5):545-551 http://www.cqvip.com/QK/91690X/200332/8605025.html
    [22] 吴华意.平面内多边形沿曲线定姿态刚体移动时的碰撞判定算法研究[J].计算机学报, 1999, 22(12):1332-1334 doi:  10.3321/j.issn:0254-4164.1999.12.020

    Wu Huayi. Research on Algorithm for Collision Test of Polygon[J]. Chinese Journal of Compu-ters, 1999, 22(12):1332-1334 doi:  10.3321/j.issn:0254-4164.1999.12.020
    [23] 李庆华.确定凸多边形可碰撞区域的快速算法[J].中国科学(A辑), 1992, 22(7):753-762 http://www.cnki.com.cn/Article/CJFDTOTAL-GCTX200002008.htm

    Li Qinghua. Rapid Algorithm Deciding Possible Collision Zone of Convex Polygons[J]. Science in China (A), 1992, 22(7):753-762 http://www.cnki.com.cn/Article/CJFDTOTAL-GCTX200002008.htm
    [24] Ghosh P K. A Solution of Polygon Containment, Spatial Planning, and Other Related Problems Using Minkowski Operations[J]. Computer Vision, Graphics, and Image Processing, 1990, 49(1):1-35 doi:  10.1016/0734-189X(90)90160-W
    [25] Ghosh P K. An Algebra of Polygons Through the Notion of Negative Shapes[J]. CVGIP:Image Understanding, 1991, 54(1):119-144 doi:  10.1016/1049-9660(91)90078-4
    [26] Yoeli P. The Logic of Automated Map Lettering[J]. The Cartographic Journal, 1972, 9(2):99-108 doi:  10.1179/caj.1972.9.2.99
    [27] Imhof E. Positioning Names on Maps[J]. The American Cartographer, 1975, 2(2):128-144 doi:  10.1559/152304075784313304
    [28] van Dijk S, van Kreveld M, Strijk T, et al. Towards an Evaluation of Quality for Names Placement Methods[J]. International Journal of Geographi-cal Information Science, 2002, 16(7):641-661 doi:  10.1080/13658810210138742
  • [1] 韩李涛, 刘建勋, 张海思, 蒋利, 孔巧丽.  一种沿公垂线方向投影的城市地下管线高效精准碰撞检测算法 . 武汉大学学报 ● 信息科学版, 2020, 45(5): 709-718. doi: 10.13203/j.whugis20180417
    [2] 李霖, 周玉杰, 于忠海.  面状居民地名称注记自动配置研究 . 武汉大学学报 ● 信息科学版, 2016, 41(2): 214-220. doi: 10.13203/j.whugis20140385
    [3] 李佳田, 康顺, 李晓娟, 张蓝, 罗富丽, 白建军.  宽泛地理注记的投放模型 . 武汉大学学报 ● 信息科学版, 2015, 40(1): 20-25.
    [4] 刘广琼, 唐曦, 黄余明.  城市轨道交通示意图注记质量评价模型研究 . 武汉大学学报 ● 信息科学版, 2011, 36(6): 734-738.
    [5] 许伟平, 朱庆, 张叶廷.  采用胶囊体进行三维城市模型的实时碰撞检测 . 武汉大学学报 ● 信息科学版, 2009, 34(9): 1030-1033.
    [6] 张晓通, 李霖, 舒亚东, 王红.  面状要素注记智能化配置方法研究 . 武汉大学学报 ● 信息科学版, 2008, 33(7): 762-765.
    [7] 郑春燕, 郭庆胜, 刘小利.  基于禁忌搜索算法的点状要素注记的自动配置 . 武汉大学学报 ● 信息科学版, 2006, 31(5): 428-431.
    [8] 郭庆胜, 刘小利, 贾治革.  城市街道注记离散化定位的自动推理方法 . 武汉大学学报 ● 信息科学版, 2006, 31(2): 152-155.
    [9] 苏姝, 李霖, 王琤.  地图汉字注记质量函数的分析与计算- . 武汉大学学报 ● 信息科学版, 2006, 31(5): 432-435.
    [10] 晁定波.  关于Stokes公式的球面卷积和平面卷积的注记 . 武汉大学学报 ● 信息科学版, 2003, 28(6): 651-654.
    [11] 罗亚波, 陈定方, 肖田元.  虚拟加工环境中的工件动态建模方法研究 . 武汉大学学报 ● 信息科学版, 2003, 28(2): 238-241.
    [12] 樊红, 杜道生, 张祖勋.  地图注记自动配置规则及其实现策略 . 武汉大学学报 ● 信息科学版, 1999, 24(2): 154-157.
    [13] 樊红, 张祖勋, 杜道生, 张剑清.  基于神经网络模型求取注记配置最优解 . 武汉大学学报 ● 信息科学版, 1998, 23(1): 32-35.
    [14] 陈孔哲, 朱欣焰, 张银洲, 苏光奎.  地图汉字注记的自动定位研究 . 武汉大学学报 ● 信息科学版, 1997, 22(2): 136-141.
    [15] 罗志才, 宁津生, 晁定波.  关于卫星重力梯度边值问题的准解的若干注记 . 武汉大学学报 ● 信息科学版, 1996, 21(4): 315-319.
    [16] 马飞.  用数学形态学自动快速寻找地图注记位置 . 武汉大学学报 ● 信息科学版, 1996, 21(2): 150-153.
    [17] 刘少创, 林宗坚.  基于神经网络的地图数字注记识别 . 武汉大学学报 ● 信息科学版, 1994, 19(3): 194-198.
    [18] 李霖.  居民地注记自动定位的研究和试验 . 武汉大学学报 ● 信息科学版, 1993, 18(S1): 32-39.
    [19] 李叶才.  关于Hotine积分的若干注记 . 武汉大学学报 ● 信息科学版, 1989, 14(1): 38-47.
    [20] 党诵诗.  关于阵列的一点注记 . 武汉大学学报 ● 信息科学版, 1988, 13(3): 101-104.
  • 加载中
图(13) / 表(2)
计量
  • 文章访问数:  1041
  • HTML全文浏览量:  49
  • PDF下载量:  371
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-10-31
  • 刊出日期:  2018-08-05

基于可移动区域的点状要素注记配置

doi: 10.13203/j.whugis20160289
    基金项目:

    国家自然科学基金 41271453

    中央高校基本科研业务费专项 2012205020211

    作者简介:

    李霖, 博士, 教授, 主要从事数字地图制图、空间数据模型、地理本体、地理信息可视化等方面的研究。lilin@whu.edu.cn

  • 中图分类号: P208;P283

摘要: 注记候选位置的确定是注记配置的重要基础,直接影响到注记算法的实现方式和最终配置效果。现有注记研究广泛使用的注记模型,其候选位置未充分利用图面空间,一定程度上制约了注记效果的进一步提升。在此背景下,提出注记候选区域模型,以要素邻域内所有无冲突压盖的候选区域作为注记配置基础,在考虑点、线、面要素压盖的前提下完成点注记配置。同其他研究相比,该算法在注记结果上取得较大提高,能更好地满足地图生产需要。

English Abstract

李霖, 张航, 朱海红, 胡玮. 基于可移动区域的点状要素注记配置[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1129-1137. doi: 10.13203/j.whugis20160289
引用本文: 李霖, 张航, 朱海红, 胡玮. 基于可移动区域的点状要素注记配置[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1129-1137. doi: 10.13203/j.whugis20160289
LI Lin, ZHANG Hang, ZHU Haihong, HU Wei. A Point-Feature Labeling Algorithm Based on Movable Regions[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1129-1137. doi: 10.13203/j.whugis20160289
Citation: LI Lin, ZHANG Hang, ZHU Haihong, HU Wei. A Point-Feature Labeling Algorithm Based on Movable Regions[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1129-1137. doi: 10.13203/j.whugis20160289
  • 地图注记自动配置是地图制图生产的核心问题之一。为了地图表达的美观和易读性,注记配置要求注记与注记间无冲突,且注记与背景要素无压盖,而无冲突压盖的注记配置已被证明是NP(non-deterministic polynomial)困难问题[1-2]。按照待注记对象的几何类型划分,地图注记可分为点、线、面3种形式[3-6]。点注记自动配置是其中最为基础的问题,近年来国内外学者对此进行了大量研究[7]

    点注记自动配置需要一个特定注记候选位置模型,该模型直接影响注记算法的实现方式和注记配置的质量。现有研究中最常采用的注记模型有两种。一是固定位置模型,每个点要素有确定数目的若干个固定位置作为注记候选位置[8],主要包括2位置模型、4位置模型、8位置模型等,其中4位置模型的使用最为广泛[9]。二是滑动模型,在保证注记文本框边缘接触点要素的前提下,注记可沿着一个或者多个方向连续滑动[10]

    基于固定位置模型的点注记配置可定义为一个组合寻优问题[11]。根据特定的目标函数,为每个点要素从固定的候选位置集合中选定注记位置,使得自由注记数目最大化或者注记冲突计数最小化等。相应的算法具体包括模拟退火、禁忌搜索、蚁群算法、遗传算法等[12-17]

    固定位置模型的优势在于对注记问题进行了抽象,能通过结合各种组合寻优算法,得到特定目标函数的全局近似最优解。缺点在于固定的候选位置限定了注记解空间,忽略了图面上的背景要素,在考虑点、线、面要素压盖的制图实践中,注记效果受到较大影响。

    滑动模型通过连续滑动的策略,能更好地利用图面空白区域,对必须考虑、点、线面背景要素的地图制图实践而言,有一定的优势[10, 18-19],Maplex等软件即是基于滑动模型实现的[20]。然而,滑动模型的注记配置沿某一轨迹线滑动,注记局限于这一轨迹线上,并未利用周围其他空间。这造成某些情况下点要素邻域范围内虽然存在无冲突压盖注记位置,但却无法实现相应的注记配置。

    在此背景下,本文针对点、线、面背景下的点注记配置问题,根据平面碰撞检测原理[21]提出了一种基于可移动区域的注记候选位置模型。

    • 碰撞检测在计算机图形学、仿真、动画和虚拟现实等技术中得到了广泛的应用[21]。而考虑无点、线、面背景冲突压盖的注记配置,其问题本质上归属于平面碰撞检测中的可移动区域范畴。本文基于可移动区域的原理,获取待注记点要素无背景碰撞的注记候选区域,并在其基础上完成注记配置,从而实现复杂背景下注记的优化配置。

    • 平面碰撞检测中,可移动区域[22-23]可表述为:设多边形P以某一点p为定位点,在平面上作定姿态刚体运动(无旋转和形变),R为平面上的背景障碍图形(点、线、面)(图 1(a)),则P保证与R不发生碰撞时,点p的移动范围即为P的可移动区域。以图 1(b)为例,图中p处于位置1时,PR发生碰撞;处于位置2时,两者无碰撞,可移动区域即所有位置2情况的合集。

      图  1  可移动区域描述示意图

      Figure 1.  Diagram of Movability Region

      可移动区域应用于注记配置问题时,注记即该多边形P,各种地图要素即背景障碍图形R,注记的可移动区域即是指无冲突压盖的注记候选区域。对于可移动区域的求解,本文基于边界组合运算原理进行生成。为了简化该问题,首先仅考虑R为点要素这一简单情形时,多边形P的可移动区域的求解具体如引理1所示。

      引理1  设平面内有一多边形P和背景点RP作由其定位点p表出的定姿态刚体运动。当点p位于点R处时,可得以点p为对称中心,与P成中心对称的多边形P′。则P′的补集即为P的可移动区域,可表示为Φ(p, P, R)。具体如图 2所示,图 2中多边形P的定位点p若处于阴影区域P′中,则P必然与点R发生碰撞;反之,若p处于P′的补集Φ(p, P, R)中,P则与点R无碰撞。

      图  2  引理1示意图

      Figure 2.  Schematic Diagram of Lemma One

      引理1中描述的是多边形P对于点背景R的可移动区域的生成,将R拓展到更为复杂的线、面背景时,则需要做进一步的处理。其基本思路为:可将线和面看作点的集合,从而将线面可移动区域的求解问题转化为引理1中点背景可移动区域的组合运算问题。对于这种区域组合的运算,可以基于如下图形学的原理实现。

      定义1   Minkowski加法[24]。欧几里得空间中的集合P′(以某一点p为定位点)与R的Minkowski加法结果S即为将p扫过R上每一个点时,与之相应的所有P′的合集(如图 3所示),可表示为:

      $$ S = P' \oplus R = \left\{ {b + t:b \in P', t \in R} \right\} $$ (1)

      图  3  Minkowski加法示意图

      Figure 3.  Schematic Diagram of Minkowski Addition

      式中,“⊕”即Minkowski加法。Ghosh[24-25]提出了边界组合理论来实现此种运算,图 3给出了P′和R相加后的结果示意图。由引理1和定义1,可以得到R为点、线、面背景时多边形P可移动区域的完备算法,具体见推理1,注记的无冲突压盖候选区域则基于该理论生成。

      推理1  设平面内有一多边形P、背景图形R(点、线、面),P作由其定位点p表出的定姿态刚体运动,P′为P以点p为对称中心,成中心对称的多边形。则有P′⊕R的补集即P的可移动区域Φ(p, P, R),见图 3

    • 本文将上述可移动区域的原理运用到注记候选位置的确定中,并以此为基础进行注记配置。注记的配置过程通常包括注记的候选位置生成、候选位置评价、注记位置选取[6, 26]

    • 本文注记算法中,候选位置生成分为两个阶段。第一步是利用可移动区域原理,为待注记点要素计算出无冲突压盖的注记候选区域;第二步是在该区域上,进一步提取出有限数量的注记候选位置,作为之后注记位置评价与选取的基础。

      1) 注记候选区域生成

      对某一个待注记点要素而言,根据可移动区域原理即可得到它的注记候选区域,当注记放置于该区域上时,注记与背景要素不发生碰撞。注记候选区域的生成过程如图 4所示。

      图  4  注记候选区域生成流程图

      Figure 4.  Generation Process of Candidate Label Region

      图 4(a)为待注记点要素、注记文本框以及邻域范围(由矩形虚线框表示,若注记在该范围内,则它与点要素的距离小于阈值r)示意图。注记文本框即推理1中的多边形P,其中心点被选定为定位点p,由于注记文本框关于点p中心对称,所以有P′=P图 4(b)为某一注记配置案例,其中圆点为待注记点要素,其他的线、面为背景要素,对应推理1中的R图 4(c)中灰色区域为通过P′⊕R计算,所生成的注记非可移动区域;图 4(d)为注记候选区域,即非可移动区域的补集,由矩形虚线框内黑色区域表示,该区域为下一步注记候选位置提取提供了无冲突压盖的基础。

      2) 注记候选位置提取

      获取注记候选区域后,进一步离散提炼出有限数量的注记候选位置。研究表明,点要素最佳注记候选位置的确定主要考虑注记与注记无冲突、注记与要素无压盖、注记位置优先级3个方面[27-28]。注记候选区域已确保无冲突压盖,故应主要考虑注记位置优先级。

      位置优先级包含注记与要素距离、注记方位两个主要因素[28]。为结合这两个因素,本文通过设定注记文本框上的离散点作为距离运算参考点的方法,提取注记候选区域上各个方位距离要素最近的注记位置作为候选位置,具体流程如下。

      1) 将注记文本框按Δw、Δh的水平、垂直间距(研究中取半个注记文本高)等分产生n个离散点作为距离运算参考点,如图 5(a)所示;

      图  5  注记候选位置生成示意图

      Figure 5.  Schematic Diagram of Candidate Label Position Generation

      2) 选取n个离散点中的某一点M为参考点,计算注记候选区域中,点M与要素距离最近时的注记位置作为候选位置;

      3) 重复步骤2),直到提取出所有n个注记候选位置,图 5(b)为点要素周围无其他背景要素,非可移动区域为矩形时(由点要素所产生,从而保证注记与该点要素无压盖),选取参考点M所生成的注记候选位置示意图。

      依照本文方法产生的注记候选位置,确保了在不压盖背景要素的前提下,各个方向上的注记尽可能地与点要素距离最短。根据图面背景要素分布的不同,算法产生的注记候选位置相应发生改变,从而更充分地利用待注记要素周围的空白区域。所得注记候选位置如图 6所示,图 6(a)为选取左上角点作为参考点所提取的注记候选位置;图 6(b)为分别选取4个角点作为参考点时所提取的4个注记候选位置示意图。

      图  6  注记候选位置生成示例

      Figure 6.  Cases of Candidate Label Positions Generation

    • 为待注记点要素生成n个注记候选位置之后,则需要按照一定的注记质量评价标准,对每一个注记候选位置进行评价。参照文献[26-28]中方法进行地图注记评价:

      $$ \begin{array}{l} Q\left( i \right) = {f_{{\rm{overlap}}}}\left( i \right) + {f_{{\rm{association}}}}\left( i \right) + {f_{{\rm{priority}}}}\left( i \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{f_{{\rm{aesthetics}}}}\left( i \right) \end{array} $$ (2)

      式中,Q(i)为注记候选位置评价函数,1≤in;其系参数与文献[26-28]同。对于每一个注记候选位置i,函数综合注记冲突压盖、注记要素关联性、注记方位优先级、注记美学性几个因子进行评价,并得出相应分值。

    • 完成候选位置生成、评价过程后,可以为待注记点要素选取最优的候选位置进行注记配置,进而完成图面的注记配置。需要说明的是,由于注记候选区域模型的特点,在按顺序进行注记配置过程中,后进行注记配置的点要素的注记空间受到之前配置的注记的影响, 所以注记逐一配置的顺序对于最终的注记结果有一定影响。

      图 7(a)虚线框中的点要素为例,如果其在周围4个点要素注记配置之后再进行注记,则可能无空白区域完成注记配置;而图 7(b)中,先完成该点要素注记配置之后再进行其余几个点要素的注记配置,则能取得更好的结果。

      图  7  不同注记顺序的结果示意图

      Figure 7.  Labeling Cases for Different Labeling Orders

      针对此问题,本文最终根据各点要素的注记候选区域情况,对注记配置的顺序进行了优化。基本思路为:对每一个点要素的注记候选位置面积值标准化并排序,然后根据值由低到高的顺序逐一注记。可使周围要素较为密集、注记候选区域面积较小的点要素先注记,以实现注记效果的优化。候选区域面积标准化公式为:

      $$ {\rm{AreaRati}}{{\rm{o}}_k} = \frac{{{{\mathit{\Phi}} _{{\rm{LabelArea}}}}\left( k \right)}}{{{{\mathit{\Phi}} _{{\rm{OriginArea}}}}\left( k \right)}}{\rm{ }} $$ (3)

      式中,k代表每一个待注记点要素;ΦOriginArea为点要素在无背景要素的理想情况下注记候选区域的大小;ΦLabelArea为点要素实际注记候选区域大小;AreaRatio即标准化后的注记候选区域面积值,取值为0~1。由以上分析可知,本文方法对所有的点要素进行注记配置的全过程为:首先,利用可移动区域原理,为每一个待注记点要素生成相应的初始注记候选区域;然后,计算每一个点要素的注记候选区域面积值,生成注记候选区域面积值集合;最后重复如下过程,直到每个点要素都完成注记配置:①从候选区域面积值集合中选取出仍未被注记且值最小的点要素;②根据该点要素的注记候选区域,通过几何运算,提取出若干个注记候选位置;③从多个注记候选位置中,利用候选位置评价函数,为点要素择优选取点位完成注记配置;④将该点要素标记为已完成注记配置,并对受该新增注记影响的注记候选区域以及相应面积值进行计算更新。

    • 本文对上述基于可移动区域的注记模型予以实现,并进行了点注记配置的对比实验与结果分析。对于注记结果的评价,为方便量化对比,只将无冲突压盖注记数目作为比较标准[12],注记目标为自由注记数目最大化,未考虑方位优先级等其他因素。

    • 为了验证该方法的有效性,并检验不同注记顺序与注记配置效果的关系,实验对不同注记顺序的结果进行了对比。对比的注记顺序包括注记候选区域面积值由大到小,注记候选区域面积值由小到大以及随机注记顺序。为了排除其他可能的干扰因素,本实验中仅针对点要素进行注记配置而暂时不考虑线、面要素压盖问题。实验用到的测试数据为在1:250 000比例尺国家标准地形图的图幅范围内,随机产生的数目分别为500、1 000、1 500…4 500、5 000个注记点要素的数据,每组数据各生成10组,实验共有10×10组测试数据集合。其中每个注记点要素的文本从一个预先生成好的地名数据库中随机获取,其字号均设为9磅。

      算法对测试数据分别使用上述3种不同的注记顺序进行点注记配置,并重复进行了3组基于随机顺序的注记配置。最终,不同注记顺序的配置结果统计如图 8(随机顺序取的是3次结果的平均值)以及表 1所示。

      图  8  不同注记顺序的无冲突压盖注记比例对比图

      Figure 8.  Conflict-Free Label Proportions with Different Labeling Orders

      表 1  不同注记顺序的无冲突压盖注记数目对比统计表

      Table 1.  Statistical Table for the Conflict-Free Label Counts with Different Labeling Orders

      要素数目 面积值由大到小 随机顺序1 随机顺序2 随机顺序3 面积值由小到大
      注记数目 注记比例/% 注记数目 注记比例/% 注记数目 注记比例/% 注记数目 注记比例/% 注记数目 注记比例/%
      500 498.30 99.66 498.50 99.70 499.60 99.92 500.00 100.00 500.00 100.00
      1000 979.30 97.93 989.00 98.90 990.60 99.06 991.50 99.15 999.30 99.93
      1 500 1 414.40 94.29 1 453.70 96.91 1 451.20 96.75 1 451.20 96.75 1 492.20 99.48
      2 000 1 784.60 89.23 1 859.50 92.98 1 869.60 93.48 1 857.40 92.87 1 975.40 98.77
      2 500 2 045.60 81.82 2 183.60 87.34 2 186.10 87.44 2 174.30 86.97 2 409.20 96.37
      3 000 2 220.20 74.01 2 387.00 79.57 2 408.70 80.29 2 402.40 80.08 2 796.70 93.22
      3 500 2 283.60 65.25 2 496.90 71.34 2 521.90 72.05 2 508.90 71.68 3 079.80 87.99
      4 000 2 271.10 56.78 2 495.60 62.39 2 506.00 62.65 2 509.10 62.73 3 270.10 81.75
      4 500 2 161.70 48.04 2 425.64 53.90 2 409.60 53.55 2 408.20 53.52 3 357.10 74.60
      5 000 2 052.70 41.05 2 264.10 45.28 2 237.20 44.74 2 248.40 44.97 3 386.80 67.74

      由统计结果来看,不同的注记顺序策略对最终的注记结果产生了较大影响。在点要素数目较少时,无冲突压盖注记比例均较高,不同注记顺序的结果差距暂不明显。点要素数目为1 500个以内时,其注记比例都保持在94.29%以上。随着要素数目的不断增加,三者取得的无冲突压盖注记数目均出现下滑。基于面积值由小到大的注记顺序下滑程度相对最小,在5 000个点要素时仍保持为67.74%的比例,随机顺序次之,较前者存在一定差距。采用面积值由大到小的注记顺序比另外两种顺序得到的结果均要差,其无冲突压盖注记比例从500个点的99.66%逐步下降到5 000个点时的41.05%,每一组别的结果都低于随机顺序的结果,差距最大达到6%以上;而与面积值由小到大的顺序相比,注记比例差值由500个点时的0.34%逐步递增到5 000个点时的26.69%,差异更为明显。基于随机顺序的3组两两较为接近,同面积值由小到大顺序的结果相比,平均注记比例的差值随着点要素数目的增加而增加,最终在5 000个点要素时,注记比例相差22%左右,差距也较为明显。

      通过实验可以看出,采用本文模型进行注记配置时,注记顺序对最终结果有直接影响。基于注记候选区域面积值,采取由小到大的注记顺序,对注记的结果有较好的优化效果。后面的实验部分均采用这种优化后的顺序进行注记配置。

    • 由于现有研究中固定位置模型和滑动模型使用最为广泛,本文采用这两种模型作为对比算法。众多基于固定位置模型的点注记算法中,模拟退火法应用最为广泛[11-13],将模拟退火算法的注记配置结果纳入对比。模拟退火法的参数设置和文献[12]的设置保持一致,具体为:初始温度40 000 ℃度,终止温度0.01 ℃,退火速度0.975 ℃/h,单次退火迭代次数12 000,注记候选位置选取4位置模型。此外,滑动模型在考虑点、线、面压盖的注记配置中具有优势,亦可选为对比方法,以便更进一步地检验本文算法的效果。

      实验采用的测试数据为在1:50 000比例尺国家标准地形图的图幅范围内,随机生成的数目分别为100、200、300…1 900、2 000个注记的点要素集合,每一数目的测试数据各生成10组,实验共有20×10组测试数据。其中每个注记点要素的文本从一个预先生成好的地名数据库中随机获取,其字号均设为6磅。实验以某图幅中的实际道路线状要素和居民地面状要素作为图面背景,先判断注记要素是否处于上述背景要素中,如果是,则舍弃,最终生成的实验点要素集合均落在图面空白区域。

      最终的候选区域注记、滑动模型注记和固定位置模型注记的对比统计结果见表 2,对应的注记比例统计折线图如图 9所示。结果表明,在考虑点、线、面背景要素无冲突压盖的注记实验中,候选区域注记的结果与滑动模型和固定位置模型相比均存在一定的优势。与固定位置模型相比,优势最为明显,各要素数目下均维持了超过25%的无冲突压盖注记比例差值;与滑动模型相比,本文算法注记比例也保持了9.84%~13.25%的提升。而滑动模型与固定位置模型比较,也展现出了在处理点、线、面背景要素上的优势,各组实验结果均优于后者,有15.00%~17.14%不等的注记比例提升。

      表 2  不同注记算法的无冲突压盖注记数目对比统计表

      Table 2.  Statistical Table for the Conflict-Free Label Counts with Different Labeling Algorithms

      要素数目 候选区域注记 固定位置模型注记 滑动模型注记
      注记数目 注记比例/% 注记数目 注记比例/% 数目差值 比例差值/% 注记数目 注记比例/% 数目差值 比例差值/%
      100 74.70 74.70 46.90 46.90 27.80 27.80 62.20 62.20 12.50 12.50
      200 150.40 75.20 91.00 45.50 59.40 29.70 123.90 61.95 26.50 13.25
      300 220.50 73.50 133.60 44.53 86.90 28.97 185.00 61.67 35.50 11.83
      400 292.80 73.20 176.50 44.13 116.30 29.08 240.60 60.15 52.20 13.05
      500 363.70 72.74 223.00 44.60 140.70 28.14 297.80 59.56 65.90 13.18
      600 430.00 71.67 256.80 42.80 173.20 28.87 351.40 58.57 78.60 13.10
      700 497.90 71.13 303.00 43.29 194.90 27.84 411.90 58.84 86.00 12.29
      800 556.10 69.51 329.30 41.16 226.80 28.35 451.40 56.43 104.70 13.09
      900 619.10 68.79 364.50 40.50 254.60 28.29 509.60 56.62 109.50 12.17
      1 000 682.20 68.22 403.50 40.35 278.70 27.87 559.70 55.97 122.50 12.25
      1 100 739.90 67.26 436.00 39.64 303.90 27.63 606.70 55.15 133.20 12.11
      1 200 797.20 66.43 471.80 39.32 325.40 27.12 654.30 54.53 142.90 11.91
      1 300 843.80 64.91 487.90 37.53 355.90 27.38 686.20 52.78 157.60 12.12
      1 400 898.30 64.16 519.40 37.10 378.90 27.06 733.10 52.36 165.20 11.80
      1 500 945.70 63.05 544.60 36.31 401.10 26.74 783.40 52.23 162.30 10.82
      1 600 996.00 62.25 577.00 36.06 419.00 26.19 821.90 51.37 174.10 10.88
      1 700 1 039.70 61.16 594.20 34.95 445.50 26.21 849.10 49.95 190.60 11.21
      1 800 1 079.60 59.98 612.40 34.02 467.20 25.96 881.90 48.99 197.70 10.98
      1 900 1 125.60 59.24 632.70 33.30 492.90 25.94 938.70 49.41 186.90 9.84
      2 000 1 165.90 58.30 653.30 32.67 512.60 25.63 963.30 48.17 202.60 10.13

      图  9  不同注记算法的无冲突压盖注记比例对比图

      Figure 9.  Conflict-Free Label Proportions with Different Labeling Algorithms

      具体而言,候选区域注记的平均注记比例从100个点时的74.70%逐步下降至2 000个点时的58.30%;滑动模型、固定位置模型的注记比例则分别由100个点时的62.20%、46.90%下降至2 000个点时的48.17%、32.67%。三者随着注记要素数目增加,相互之间注记比例的差值变化不大,整体上略有减少。同时,三者注记比例的下降也较为缓慢,这是由于在该注记实验中,待注记要素数目最高为2 000个,注记之间的冲突不是注记配置时面临的最大困难,点、线、面背景要素的密集分布的影响更为主要。在这种情况下,能否更好地在图面上找到并利用可放置注记的空白区域决定了算法注记结果上的差异。因此,3种算法在100~2 000个点实验中所存在的较为稳定的注记比例差值主要是由处理点、线、面背景时,模型间的固有特征和差异所决定的。

      为了更清晰地对比3种算法得到的注记配置结果,图 101112中展示了对2 000个点要素中的第1组数据使用不同算法得到的注记结果局部展示图。其中图 10为候选区域注记局部结果图,图 11图 12为同一区域滑动模型和固定位置模型结果。

      图  10  候选区域注记结果

      Figure 10.  Labeling Result of Candidate Region

      图  11  滑动模型注记结果

      Figure 11.  Labeling Result of Slider Model

      图  12  固定位置模型注记结果

      Figure 12.  Labeling Result of Fixed-Position Model

      在本组注记配置结果中,候选区域注记总计无冲突压盖数目为1 183个,滑动模型注记为980个,固定位置模型注记为652个。候选区域注记的结果均优于后两者,分别比滑动模型和固定位置模型多出203个、531个自由注记,取得了10.15%和26.66%的注记比例提升。

      图 13(a)分别为图 101112中5个虚线框对应的3种方法局部的对比案例,图 13(b)为一些典型的候选区域注记结果示例。从图 13(a)的对比中可以看出,候选区域注记算法更具优势,其基于可移动区域的注记方式,在空白区域上只要有位置可放置注记均能完成注记配置,同时得益于基于面积值的注记顺序优化,取得了较好的注记效果。而滑动模型由于可以沿轨迹线滑动,对很多固定位置模型不方便处理的案例也取得了无冲突压盖注记解,表现出了一定优势;但由于其解空间限定于某一条轨迹线,对该线周围的邻近区域较难考虑,所以较候选区域注记的结果有一定差距。

      图  13  2 000个点要素的注记结果对比图

      Figure 13.  Comparison of Labeling Results for 2 000 Point Features

    • 本文考虑点、线、面背景要素无压盖的点注记配置实际问题,利用平面碰撞检测中的可移动区域原理,提出基于候选区域的注记算法。和目前主流的固定位置模型和滑动模型相比,本文算法基于要素可注记候选区域,在其基础之上寻求最优注记解,并保证在考虑点、线、面复杂背景情况下,若要素邻域范围内仍有空间可以注记,算法均可完成该要素的注记配置。同时,算法通过优化注记顺序的方式,对注记配置结果实现了优化,在最终的无点、线、面要素压盖的点注记配置对比实验中,取得了较好的注记效果。

      由于算法具有良好的扩展性,后续研究可尝试将这种基于区域的候选位置模型,结合线、面注记质量评价标准,运用于线、面要素等注记配置中。此外,对于某些图面背景过于复杂的待注记要素而言,由于其不存在可移动区域,为了更好地完成注记配置,需要解决对背景要素选择性压盖或者对点要素进行取舍等相关问题,在下一步研究中将对其进行探索。

参考文献 (28)

目录

    /

    返回文章
    返回