一种地图点要素注记自动配置方法

摘要

本发明提供一种地图点要素注记自动配置方法，包含针对集合内所有点要素生成初始的注记候选区域集合，根据每个点要素的注记候选区域情况，按区域范围相对较小的要素先注记的顺序进行注记配置。本发明以要素邻域内所有可利用的注记空间作为注记配置基础，能在考虑图面冲突压盖前提下，完成高质量点注记配置。同其他注记算法相比，该发明在有效注记数目、质量以及复杂情况下注记等方面取得较大提高，更好的满足了地图注记配置要求。

权利要求

1.一种地图点要素注记自动配置方法，其特征在于，包含以下步骤：

步骤1，输入地图上待注记的点要素集合，针对集合内所有点要素生成初始的注记候选区域集合，包括以下子步骤，步骤1.1，输入注记与点要素的距离阈值，并根据距离阈值以及注记文本框的宽度、高度，确定每个点要素的有效注记邻域范围；

步骤1.2，对每一个点要素，考虑邻域范围内的所有背景要素，根据平面碰撞检测原理，进行可移动区域的计算，获得点要素的注记候选区域；所有点要素的注记候选区域构成初始的注记候选区域集合；

步骤2，以步骤1所生成初始的注记候选区域集合为基础，根据每个点要素的注记候选区域情况，按区域范围相对较小的要素先注记的顺序进行注记配置，包括以下子步骤，步骤2.1，根据注记候选区域集合，按照区域范围相对大小进行排序，确定各待注记点要素的注记配置顺序；每个点要素的区域范围相对大小为注记候选区域和有效注记邻域范围面积的比值，比值小的要素注记配置顺序在先；

步骤2.2，根据步骤2.1确定的注记配置顺序，取当前处于首位的点要素作为当前点要素进行配置，首先从当前点要素的注记候选区域离散筛选注记候选位置，包含以下子步骤，步骤2.2.1，在注记文本框上均匀地取若干个离散点作为距离运算参考点，设取到的离散点数目为n；

步骤2.2.2，取n个离散点中的某一点M为参照，计算当前点要素的注记候选区域中点M与当前点要素距离最近时的注记位置，作为点M相应的注记候选位置；

步骤2.2.3，返回步骤2.2.2取n个离散点中的另一点为参照，直到产生所有n个注记候选位置；

步骤2.3，从步骤2.2生成的n个注记候选位置中，选取最优的注记位置对当前点要素进行注记配置，生成注记；

步骤2.4，将当前点要素从待注记的点要素集合中去除，将当前点要素的注记候选区域从注记候选区域集合中去除，并根据新生成的注记，对注记候选区域集合内相关受影响的点要素的注记候选区域进行更新，返回步骤2.1取下一个处于首位的点要素作为当前点要素进行配置，直到所有的点要素均完成注记配置。

2.如权利要求1所述的地图点要素注记自动配置方法，其特征在于：步骤1.2所述可移动区域的计算实现如下，设注记文本框为多边形P，以注记文本框中点为定位参照点p，P'为P以点p中心对称的对称图形，P的可移动区域S可表示为P'⊕R的补集，其中“⊕”表示Minkowski加法，结果为P'随其定位参考点p在集合R上移动所扫过所有区域的总和，集合R为背景元素。

3.如权利要求1或2所述的地图点要素注记自动配置方法，其特征在于：步骤2.3中，对n个注记候选位置分别按照以下注记质量评价函数进行评价，选取综合评价结果值最低的注记候选位置作为最优的注记位置，Anno＝Min(a×Disk+b×Dirk+c×NearPk+d×NearAk) (k＝1,...,n)

其中，Disk、Dirk、NearPk、NearAk分别为第k个注记候选位置的注记与对应要素关联性因子Dis、方位优先级因子Dir、注记与其他要素的距离因子NearP、注记与其他注记的距离因子NearA，Anno为综合评价结果值最低结果，a、b、c、d为权重值。

4.如权利要求3所述的地图点要素注记自动配置方法，其特征在于：所述注记与其他要素的距离因子NearP的求取如下，其中，ε为相邻点要素最大距离阈值，NearPoint为阈值ε相应邻域内所有点要素的集合；i为集合NearPoint内的任一点要素，disi为当前注记与点要素i的距离。

5.如权利要求3所述的地图点要素注记自动配置方法，其特征在于：所述注记与其他注记的距离因子NearA的求取如下，其中，ε为相邻注记最大距离阈值，Nearanno为阈值ε相应邻域内所有注记的集合；i为集合Nearanno内的任一注记；disi为当前注记与相邻注记i的距离；ω为常量，AnnoLen为当前注记的长度；lengthi为注记重合的长度。

说明书

一种地图点要素注记自动配置方法

技术领域

[0001] 本发明属于地图制图自动化技术领域，特别涉及一种地图点要素注记自动配置方法。

背景技术

[0002] 从20世纪50年代，国内外地图制图工作者对地图的编制如何摆脱繁重的手工方式，实现地图制图自动化进行了理论与方法的研究。经过50年的发展，从最初提出的地图制图自动化，后来提出的计算机辅助地图制图、计算机地图制图，计算机地图制图的技术问题(包括硬件与软件系统)已基本解决，已全部实现各种类型地图的计算机制图。

[0003] 采用数字地图制图技术和电子出版技术,地图制图生产实现了由传统的模拟制图技术向现代计算机数字制图技术的发展,地图制图与出版的数字化一体化已成为地图制图生产的基本技术手段,提高了地图制图与出版的速度和质量,降低了地图制作成本，丰富了地图设计者的创作手法，缩短了成图周期,适应了国民经济建设、国防建设、社会发展和人类文明进步的需求,是地图学发展史上的一个革命性转变。

[0004] 地图注记自动配置是地图制图自动化中核心问题之一，国内外学者对此进行了许多深入的研究和探讨，取得了一些进展。例如，在注记候选位置的确定方面，主要成果有固定位置模型、滑动模型，以及基于格网等近似连续的注记模型等。

[0005] 由于现有研究通常将启发式搜索作为注记配置算法的基础，因此固定位置模型是最常采用的注记候选位置模型，常见的有4位置、8位置模型以及其他改善的固定位置模型，由于其并非在要素所有可注记候选区域中寻求注记解的固有缺陷，实际应用中许多注记位置并没有到达较好的效果。而少数近似连续的注记候选位置模型，例如上述的基于格网、滑动模型等算法，也有着复杂程度高、注记效果不佳等缺陷，需要提出全新的技术方案进行改进和完善。

发明内容

[0006] 本发明所要解决的问题是，提供一种能够在复杂图面背景无冲突压盖前提下，进行点要素注记自动配置方法。

[0007] 本发明提供一种地图点要素注记自动配置方法，包含以下步骤：

[0008] 步骤1，输入地图上待注记的点要素集合，针对集合内所有点要素生成初始的注记候选区域集合，包括以下子步骤，

[0009] 步骤1.1，输入注记与点要素的距离阈值，并根据距离阈值以及注记文本框的宽度、高度，确定每个点要素的有效注记邻域范围；

[0010] 步骤1.2，对每一个点要素，考虑邻域范围内的所有背景要素，根据平面碰撞检测原理，进行可移动区域的计算，获得点要素的注记候选区域；所有点要素的注记候选区域构成初始的注记候选区域集合；

[0011] 步骤2，以步骤1所生成初始的注记候选区域集合为基础，根据每个点要素的注记候选区域情况，按区域范围相对较小的要素先注记的顺序进行注记配置，包括以下子步骤，[0012] 步骤2.1，根据注记候选区域集合，按照区域范围相对大小对进行排序，确定各待注记点要素的注记配置顺序；每个点要素的区域范围相对大小为注记候选区域和有效注记邻域范围面积的比值，比值小的要素注记配置顺序在先；

[0013] 步骤2.2，根据步骤2.1确定的注记配置顺序，取当前处于首位的点要素作为当前点要素进行配置，首先从当前点要素的注记候选区域离散筛选注记候选位置，包含以下子步骤，

[0014] 步骤2.2.1，在注记文本框上均匀地取若干个离散点作为距离运算参考点，设取到的离散点数目为n；

[0015] 步骤2.2.2，取n个离散点中的某一点M为参照，计算当前点要素的注记候选区域中点M与当前点要素距离最近时的注记位置，作为点M相应的注记候选位置；

[0016] 步骤2.2.3，返回步骤2.2.2取n个离散点中的另一点为参照，直到产生所有n个注记候选位置；

[0017] 步骤2.3，从步骤2.2生成的n个注记候选位置中，选取最优的注记位置对当前点要素进行注记配置，生成注记；

[0018] 步骤2.4，将当前点要素从待注记的点要素集合中去除，将当前点要素的注记候选区域从注记候选区域集合中去除，并根据新生成的注记，对注记候选区域集合内相关受影响的点要素的注记候选区域进行更新，返回步骤2.1取下一个处于首位的点要素作为当前点要素进行配置，直到所有的点要素均完成注记配置。

[0019] 而且，步骤1.2所述可移动区域的计算实现如下，

[0020] 设注记文本框为多边形P，以注记文本框中点为定位参照点p，P'为P以点p中心对称的对称图形，P的可移动区域S可表示为P'⊕R的补集，其中“⊕”表示Minkowski加法，结果为P'随其定位参考点p在集合R上移动所扫过所有区域的总和，集合R为背景元素。

[0021] 而且，步骤2.3中，对n个注记候选位置分别按照以下注记质量评价函数进行评价，选取综合评价结果值最低的注记候选位置作为最优的注记位置，

[0022] Anno＝Min(a×Disk+b×Dirk+c×NearPk+d×NearAk)

[0023] (k＝1,...,n)

[0024] 其中，Disk、Dirk、NearPk、NearAk分别为第k个注记候选位置的注记与对应要素关联性因子Dis、方位优先级因子Dir、注记与其他要素的距离因子NearP、注记与其他注记的距离因子NearA，Anno为综合评价结果值最低结果。

[0025] 而且，所述注记与其他要素的距离因子NearP的求取如下，

[0026]

[0027] 其中，ε为相邻点要素最大距离阈值，NearPoint为阈值ε相应邻域内所有点要素的集合；i为集合NearPoint内的任一点要素，disi为当前注记与点要素i的距离。

[0028] 而且，所述注记与其他注记的距离因子NearA的求取如下，

[0029]

[0030] 其中，ε为相邻注记最大距离阈值，Nearanno为阈值ε相应邻域内所有注记的集合；i为集合Nearanno内的任一注记；disi为当前注记与相邻注记i的距离；ω为常量，AnnoLen为当前注记的长度；lengthi为注记重合的长度。

[0031] 在现有技术背景下，本发明根据碰撞检测原理提出了一种基于“可移动区域”的注记候选区域模型：获取点注记无背景压盖的可移动候选区域，并根据符合制图规范的注记质量评价原则，在该区域上选取最优注记位置，同时针对算法特点进行注记顺序的优化，从而优化点注记自动配置过程。依照本发明所提供的地图点要素注记自动配置方法，其以要素邻域内所有可利用的注记空间作为注记配置基础，能在考虑图面冲突压盖前提下，完成高质量点注记配置。同其他注记方法相比，该发明在有效注记数目、质量以及复杂情况下注记等方面取得较大提高，更好的满足了地图注记配置要求。

附图说明

[0032] 图1为本发明实施例在地图点要素注记自动配置时的流程图。

[0033] 图2为本发明实施例中点要素邻域范围的示意图。

[0034] 图3为本发明实施例中的对称图形示意图。

[0035] 图4为本发明实施例中Minkowski加法边界运算的示意图。

[0036] 图5为本发明实施例中注记候选区域生成步骤的示意图。

[0037] 图6为本发明实施例中注记候选位置离散选取的示意图。

[0038] 图7为本发明实施例中注记方位优先级的示意图。

[0039] 图8为本发明实施例中注记与相邻要素距离示意图。

[0040] 图9为本发明实施例中注记与相邻注记距离、重合长度示意图。

[0041] 具体实施方法

[0042] 本发明要解决的核心问题是：考虑无点线面混合背景冲突压盖的注记配置，其本质上属于平面碰撞检测中碰撞规避的范畴。运用其可移动区域原理，获取待注记要素无背景“碰撞”的注记候选区域，作为进一步注记位置寻优的基础，实现混合背景下点状要素的注记优化配置。

[0043] 以下结合附图和实施例，详细描述本发明的地图点要素注记自动配置方法。

[0044] 具体实施时，本发明方法可采用计算机软件技术实现自动运行。参见图1，实施例所提供的方法流程包括以下步骤：

[0045] 步骤1，输入地图上待注记的点要素集合，针对集合内所有待注记点要素，考虑背景要素(包括点、线、面要素)生成初始的注记候选区域集合，包括以下子步骤:

[0046] 步骤1.1，输入注记与点要素的距离阈值，并根据距离阈值以及注记文本框的宽度、高度，确定每个点要素的有效注记邻域范围；

[0047] 注记与要素的距离需要保证在一定的阈值以内，否则注记将具有歧义性，具体实施时本领域技术人员可以自行预设阈值。以注记和点要素的距离阈值为r时为例，其邻域范围的生成见图2。其中w、h分别为注记文本框的宽度与高度；带圆点的实线圈表示待注记的点要素；虚线圆圈即阈值半径r所形成的圆，若要求注记与要素距离保持在r以内，则注记框必须与该虚线圈有交集；虚线圆角矩形框为有效注记邻域范围，其宽度与高度分别为w+2r和h+2r，它表示注记文本框的中点所能放置的区域范围，超过此范围则注记与要素的距离大于阈值r，注记的可移动区域计算在该邻域范围内进行。

[0048] 步骤1.2，对每一个点要素，考虑其邻域范围内的所有背景要素(点、线、面要素)，根据平面碰撞检测原理，进行其可移动区域的计算，获得点要素的注记候选区域，所有点要素的注记候选区域构成初始的注记候选区域集合；

[0049] 设P＝(P0,P1,…,Pm-1)为平面上由一系列顶点P0、P1、P2…组成的多边形，m为顶点数目，定位参考点为p，其可在平面上任意选取，与多边形P相对位置保持不变；R＝(R0,R1,…,Rn-1)为由一系列顶点R0、R1、R2…组成的背景面(线)，n为顶点数目。背景中的点要素可视为极短的线，做同样处理即可。P作由其定位参考点p表出的定姿态刚体移动，P'为P以点p中心对称的对称图形(见图3)，则P的可移动区域S可表示为P'⊕R的补集。这里的“⊕”为Minkowski加法，其结果为P'随其定位参考点p在集合R上移动所扫过所有区域的总和，其运算示意图如图4所示，图为Minkowski加法运算的结果，其中Φ为S的补集，即P相对于R的可移动区域，当p在区域Φ以内时，P与R绝对不发生碰撞、压盖。曲线e称为Minkowski曲线。

[0050] 将以上“可移动区域”求取方式运用到注记候选位置的确定中即可得到注记候选区域，它由注记文本框中心点可放置位置来定义，是待注记要素邻域范围内无点、线、面背景碰撞的全体注记候选位置的集合。具体而言，注记的矩形文本框即为上述多边形P，注记文本框的中点被选定为定位参考点p，由于注记文本框关于中点p中心对称，所以有P'＝P。注记候选区域生成步骤示意图如图5所示，其中(a)为点要素、注记文本框以及邻域范围示意图；(b)为原始地图要素，其中圆点为待注记点要素，其他的点(用×表示)、线、面为邻近背景要素；(c)为注记“非”可移动区域，由阴影部分表示；(d)为注记候选区域，由虚线框内阴影部分表示。

[0051] 步骤2，以点要素步骤1所生成初始的注记候选区域集合为基础，根据每个点要素的注记候选区域情况，按区域范围相对较小的要素先注记、反之则后注记的顺序进行注记配置，包括以下子步骤:

[0052] 步骤2.1，根据注记候选区域集合，按照区域范围相对大小进行排序，确定点要素的注记配置顺序。注记配置顺序的确定，一般是在要素逐一注记配置过程中，对于周围要素较为密集，或者注记候选区域面积较小的待注记点要素先注记；反之，则后注记，从而优化注记全局效果。因此，本发明提出，区域范围相对大小根据所有待注记点要素的实际注记候选区域面积和理想状况下注记候选区域面积的比值大小确定，进行排序，其比值取值范围为0到1之间，面积比值小的点要素优先注记，反之则之后注记。其中，实际注记候选区域面积由考虑所有邻域内点、线、面、已有注记等背景要素下，进行可移动区域计算所得到的注记候选区域面积，即步骤1.2的计算结果；理想状况下注记候选区域面积即邻域内无任何干扰背景要素时的有效注记邻域范围，即步骤1.1的计算结果。因此，每个点要素的区域范围相对大小为步骤1.2所得注记候选区域和步骤1.1所得有效注记邻域范围面积的比值，比值小的要素注记配置顺序在先。

[0053] 步骤2.2，根据步骤2.1确定的注记配置顺序，取当前处于首位的点要素作为当前点要素进行配置。首先，注记候选区域为点注记配置提供了无冲突压盖的位置候选基础，为使注记算法可行且高效，需要在其上进一步离散筛选出一定数量的注记候选位置。以当前点要素的注记文本框为基础，通过设定注记文本框上的n个离散点作为距离运算参考点的方法，获取该注记候选区域上各个方位距离要素最近的n个注记位置作为候选位置，示意图如图6所示，包含以下子步骤：

[0054] 步骤2.2.1，在注记文本框上均匀地取若干个离散点作为距离运算参考点，设取到的离散点数目为n。实施例将注记文本框按Δw、Δh(实施例中设定为半个注记文本高度值，具体实施时也可根据注记效率、质量具体需求预先设定为其他值)的水平、垂直间距等分产生n个离散点作为距离运算参考点。

[0055] 步骤2.2.2，取n个离散点中的某一点M为参照，计算步骤1所得当前点要素的注记候选区域中，点M与当前点要素距离最近时的注记位置作为注记候选位置，即将注记文本框中心点在注记候选区域中遍历，遍历到注记候选区域中每一个位置时都求取当前点M与点要素距离，取距离最小时的注记文本框中心点所在位置为点M相应的注记候选位置。图6(b)为某椭圆形注记候选区域下的所有n个注记候选位置中的某4个注记候选位置示意图(正上、正左、正右以及某一与点M距离最近的注记候选位置，其余点位由于绘图效果因素略去)。

[0056] 步骤2.2.3，返回步骤2.2.2取n个离散点中的另一点为参照，直到对n个离散点依次处理完毕，产生n个注记候选位置。

[0057] 步骤2.3，对于步骤2.2生成的n个注记候选位置，选取最优的注记位置对当前点要素进行注记配置，生成注记。

[0058] 具体实施时，本领域技术人员可自行选择最优的注记位置，或者设定注记质量评价函数，通过注记质量评价函数对关联性、方位优先级、易读性等指标进行综合评价，选取最优的注记位置对该点要素进行注记配置。一般综合评价考虑包含以下方面：

[0059] (1)无冲突压盖原则：注记配置要求无冲突压盖，而本发明上述注记候选区域中产生的候选位置，即无冲突和压盖的注记位置，所以必然满足该原则，这也是本发明的优点所在。

[0060] (2)要素注记关联性：注记与相应要素的关联性原则，要求注记结果能明确反映注记与要素的所属关系。对于该原则，主要考虑注记与相应点要素之间的距离因素，距离的远近与关联性的强弱直接相关，该评价因子由Dis表示。Dis的求解通过求点要素与步骤2.2中的各距离运算参考点的距离得到。

[0061] (3)注记方位优先级：不同方位上的注记候选位置，在美学和认知习惯上存在差异，所以注记在方位上有优先顺序之分，具体实施时，本领域技术人员可自行设定相应因子取值。文中注记的方位优先级因子用Dir表示。如图6所示，注记在右、上、左、下四个正方向上优先级分别取Dir＝1、2、3、4，其余右上、左上、左下、右下方向上优先级均取Dir＝5、6、7、8。如图7所示。

[0062] (4)注记易读性：研究为进一步增强地图的美学平衡特征，将注记的易读性作为质量评价标准的重要部分，纳入注记配置过程中进行考虑。注记易读性最主要的考虑因素为注记与要素的相互位置关系，具体包括注记与其他要素、注记与其他注记相对位置的密集情况。

[0063] 1)注记与其他要素：注记同其他点要素应该尽量远离，面、线要素则无影响，距离近也不会产生歧义，本发明通过计算注记同其他相邻点要素距离值并求和的方式，量化注记与其他要素邻近情况为评价因子NearP，求取公式如下：

[0064]

[0065] 其中ε为运算时，加入计算的其他相邻点要素最大距离阈值(通常设定为图幅内最大字号注记文本的高度值)，NearPoint为阈值ε相应邻域内所有点要素的集合，以注记候选位置为中心，其邻域范围的生成与步骤1.1的方式相同，领域范围为虚线圆角矩形框，其宽度与高度分别为w+2ε和h+2ε；i为集合NearPoint内的任一点要素；disi为当前注记与点要素i的距离，其计算方式见图8，注记与相邻要素的距离求解具体情况可总结为图中相邻点要素a、b两种情况，其分别对应的disi距离值见图中disa、disb。

[0066] 2)注记与其他注记：为防止注记局部密集分布，配置注记时考虑与已有注记距离情况。研究通过计算注记同其他注记距离值和重合长度值的方式，量化注记与其他注记邻近情况为评价因子NearA，求取公式如下：

[0067]

[0068] 其中ε为运算时，加入计算的其他注记最大距离阈值(设定值同上)，Nearanno为阈值ε相应邻域内所有注记的集合，以注记候选位置为中心，其邻域范围的生成与步骤1.1的方式相同，领域范围为虚线圆角矩形框，其宽度与高度分别为w+2ε和h+2ε；i为集合Nearanno内的任一注记；disi为当前注记与相邻注记i的距离；ω为常量，通常设定为1；AnnoLen为当前注记的长度；lengthi为注记重合的长度，见图9。注记与相邻注记的距离、重合长度求解具体情况可总结为图中相邻注记a、b两种情况。其中a注记与当前注记重合距离lengthi为0，其距离值disi对应为图上disa；而b注记与当前注记重合距离lengthi为图上length所示，距离值disi对应为图上disb。

[0069] 将上述所有注记质量评价因子进行综合之后，最终待注记要素的注记位置选取，即对n个注记候选位置分别进行质量评价评价择优，选取最优位置进行注记配置。研究通过注记质量评价函数对待注记要素n个注记候选位置进行评价，选取综合评价结果值最低的点位作为最终注记位置进行注记配置。综合择优评价方式如下，其中a、b、c、d权重值可根据注记具体需要自行设定，可以采用1:1:1:1、2:2:1:1等多种设定。

[0070] Anno＝Min(a×Disk+b×Dirk+c×NearPk+d×NearAk)

[0071]  (k＝1,...,n)

[0072] 其中，Disk、Dirk、NearPk、NearAk分别为第k个注记候选位置的评价因子Dis、Dir、NearP、NearA，Anno为综合评价结果值最低结果。

[0073] 步骤2.4，将被注记的当前点要素从待注记的点要素集合中去除，将当前点要素的注记候选区域从从注记候选区域集合中剔除，并根据新生成的注记，对注记候选区域集合内相关受影响的点要素的注记候选区域进行更新，即去掉新生成的注记与剩余注记候选区域重叠的部分。返回进入步骤2.1，直到所有的点要素均完成注记配置。

[0074] 将已经进行过注记的点要素其对应的注记候选区域从注记候选区域集合中剔除。具体实施时，可以按照之前可移动区域计算的方法，对由新增注记影响的剩余的注记候选区域进行重新计算更新，并重新计算所有注记候选区域集合的面积比值，从而重新确定注记顺序，但效率较低，考虑到注记影响的范围较小，本发明建议对注记候选区域集合内相关受影响的点要素的注记候选区域进行更新，去掉新生成的注记与当前注记候选区域集合内剩余注记候选区域重叠的部分。再回到步骤2.1，对下一个注记进行配置。反复执行此过程直到完成所有要素的注记配置。

[0075] 以上所述仅为本发明中的一个实施例，并不用于限制本发明。凡在本发明的精神与原则之内，所做的任何修改，改进等，均应包含在本发明的保护范围之内。