地图中面状要素标注算法的设计与改进

Algorithms Design and Improvement of Area Features in Map Labeling

通过对现有的面状要素标注算法的深入研究,对面状要素标注算法采用分类处理。在求解多边形骨架的算法中,改进了求简单多边形的直径算法,提出了一种新的平面点集三角剖分算法,该算法直接以简化的多边形进行三角剖分,并将借用回溯法来解决面状要素标注所产生的冲突。理论分析和实验表明:与已有的标注算法相比,减少了骨架算法求解的步骤,有效的解决了面状要素标注所产生的问题。

The existing algorithm for area feature labeling is the classified processing approach. In the solution to the problem of polygon skeleton, this paper proposes a kind of new triangulation algorithm for the point-set in a plane instead of the diameter algorithm for a simple polygon. The triangulation is directly adopted in the algorithm of a simple polygon, and a backtracking technique is used to solve the conflict, which produces in the area feature labeling. Theoretical analysis and experimental results indicate that compared with the existing algorithms of map labeling, this kind of algorithm can effectively solve the problem which has produced in area feature labeling and reduce some steps in the solution of skeletons of a polygon.