一种考虑标签形状和大小的面特征标签放置方法

本发明属于数据处理，尤其涉及一种考虑标签形状和大小的面特征标签放置方法。

背景技术：

1、在可视化领域，为静态图添加文本标签是为可视化补充语义信息的一种常见方式。例如，在地图上将国家名字放置到国家疆域内，在人体结构图上将器官名字放置在对应器官周围。但是当被标记物由单个或多个离散封闭多边形组成时，该问题被称为面特征标签放置问题。这类问题的核心目标是确保标签与所标记的多边形视觉和谐。然而，视觉和谐并没用统一、明确的定义，一般指的是，标签处于目标多边形视觉中心位置，尽量远离多边形边界。

2、为了实现这一目标，研究者们定义了不同的标签理想位置，并提出了多种求解方法。最常见的两类方法是最大子多边形法和最大内切圆法：其中，当多边形存在内部孔洞，最大子多边形法可能会导致标签放置在孔洞内部，从而降低可读性，最大内切圆法将标签视作质点，忽略了标签自身的形状和大小对视觉效果的影响。当标签具有较大的长宽比时，这类方法常常导致视觉不协调的情况。

3、为了克服以上两类方法的缺点，本发明定义了一种考虑了标签本身形状和大小的新的理想位置，并在polylabel算法的启发下设计、实现了polylabel+算法。该算法修改了空间过滤条件，能够高效地以任意精度逼近定义的理想位置，并在77.2％的情况下，polylabel+算法的标签放置结果优于polylabel算法。修改的空间过滤条件可通过数学证明。具体的，本发明提供了一种考虑标签形状和大小的面特征标签放置方法。

技术实现思路

1、本发明的目的是提供一种考虑标签形状和大小的面特征标签放置方法。

2、为了解决上述技术问题，本发明提供了一种考虑标签形状和大小的面特征标签放置方法，其特征在于，具体包括：

3、将标签的长和宽、目标多边形以及算法模型的精度作为基础，并新建一个所述标签的优先队列；

4、算法模型以目标多边形的包围框的短边为边长构造得到能覆盖目标多边形的多个方格，并将它们压入一个优先队列中，优先队列记录需要检查的方格，并以方格的潜力上限的降序排名，依次检查队列中的方格，当方格的中心节点的分数大于当前最佳分数时，则将最佳方格进行更新，更新为当前的方格；

5、判断方格的潜力上限是否低于最佳方格的最佳分数与精度之和，若是，则将所述方格抛弃，若否，则将所述方格向下划分一层得到四个子方格，并将它们加入队列中；

6、循环上述过程直到队列为空，最终所述最佳方格的中心即为定义精度下的理想位置。

7、本发明可以以任意精度逼近全局最优，能够高效地以任意精度逼近定义的理想位置，把给定形状和大小的文本标签放置在视觉的理想位置。本发明的有益效果具体阐述如下：

8、1、计算高效：首先，本发明基于四叉树空间划分和动态空间过滤，可快速排除大量不会产生全局最优的区域，使得需要检查的次数大幅下降；其次，本发明以优先队列为数据结构，每次弹出的都是在理论上最有希望取得全局最优解的区域，可以最快速度刷新当前的最优值，促进快速收敛；最后，以多边形的质心作为初始位置，常常在算法初期就获得接近全局最优的解，加快了空间过滤。在由300个地区边界组成的测试数据集上的实验表明，本发明可在毫秒级完成计算，平均耗时为15.6毫秒。

9、2、参数简单，可以以任意精度逼近全局最优：本发明的polylabel+算法只有一个参数——精度，控制了最终获得的位置与全局最优位置偏差的理论上限。该值越低，结果越接近于全局最优。

10、3、更为协调的视觉效果：由于理想放置位置考虑了标签的大小和轮廓，本发明提出的polylabel+方法可以在更多情况下使得标签的边界远离目标多边形的边界。在一个由10位志愿者参与的、300个地区边界组成测试数据集的定量评估中显示，本发明的polylabel+算法在77.2％的地区边界获得了主观上更好的可视效果。

11、进一步的技术方案在于，所述目标多边形为需要进行标签放置的目标。

12、进一步的技术方案在于，所述方格的潜力上限根据所述方格的中心节点的分数与方格的边长进行确定。

13、进一步的技术方案在于，所述方格的中心节点的分数根据所述方格的矩形标签的四个顶点到多边形的距离的最小值进行确定。

14、进一步的技术方案在于，将所述方格向下划分一层得到四个子方格，具体包括：

15、以所述方格的边长为基础，按照划分数量为4进行子方格的划分边长的确定；

16、根据所述划分边长以及划分数量将所述方格向下划分一层得到四个子方格。

17、进一步的技术方案在于，所述预设数量根据所述方格的边长以及所述方格的当前的划分次数进行确定，其中所述方格的边长越长，所述方格的当前的划分次数越少，则所述预设数量越多。

18、其他特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点在说明书以及附图中所特别指出的结构来实现和获得。

19、为使本发明的上述目的、特征和优点能更明显易懂，下文特举较佳实施例，并配合所附附图，作详细说明如下。

1.一种考虑标签形状和大小的面特征标签放置方法，其特征在于，具体包括：

2.如权利要求1所述的一种考虑标签形状和大小的面特征标签放置方法，其特征在于，所述目标多边形为需要进行标签放置的目标。

3.如权利要求1所述的一种考虑标签形状和大小的面特征标签放置方法，其特征在于，所述方格的边长根据所述目标多边形的包围框的数量以及不同的包围框的长度进行确定，其中所述目标多边形的包围框的数量越多，不同的包围框的长度越短，则所述方格的边长的越短。

4.如权利要求3所述的一种考虑标签形状和大小的面特征标签放置方法，其特征在于，所述方格的边长的确定的方法为：

5.如权利要求4所述的一种考虑标签形状和大小的面特征标签放置方法，其特征在于，基于不同的长度区间的边长补偿量以及推荐边长进行所述方格的边长的确定，具体包括：

6.如权利要求1所述的一种考虑标签形状和大小的面特征标签放置方法，其特征在于，所述方格的潜力上限根据所述方格的中心节点的分数与方格的边长进行确定。

7.如权利要求1所述的一种考虑标签形状和大小的面特征标签放置方法，其特征在于，所述方格的中心节点的分数根据所述方格的矩形标签的四个顶点到多边形的距离的最小值进行确定。

8.如权利要求1所述的一种考虑标签形状和大小的面特征标签放置方法，其特征在于，将所述方格向下划分一层得到四个子方格，具体包括：