Advanced Labeling Algorithms for Digital Maps

在本研究中，我们考虑了地图上各点的标注问题，得到了以下结果：1.首先讨论了每个点都有优先权的标注问题。我们考虑了两种情况；在第一种情况下，我们禁止删除点数，在第二种情况下，我们允许这样做。通过将Wagner-Wolff方法推广到无优先级地图标注问题，给出了两种情况下的标注算法。2.如果标注尺寸不够小，通常的标注算法不能总是放置所有点的标注。因此，我们考虑了为未分配标签的点放置带有引线的标签的问题。最后，针对标签字符可以自上而下和/或两行书写的情况，提出了两种算法，并通过计算机实验验证了算法的有效性。我们首先展示了Wagner-Wolff算法的一个简单扩展，然后对其进行了改进以减少执行时间。

In this research, we considered the problem of placing labels of the points in a map and obtained the following results :1.We first dealt with the labeling problem in which each point is assigned its priority. We considered two cases ; in the first case we forbad the removal of points, and in the second case we allowed it. By extending the Wagner-Wolff method for the map labeling problem with no priorities, we presented labeling algorithms for both cases.2.If the label sizes are not small enough, the usual labeling algorithms cannot always place labels of the all points. Thus we considered the problem of placing labels with leader lines for the points to which labels are not assigned. We proposed two algorithms for this problem and showed their effectiveness by computer experiments.3.Finally we developed labeling algorithms for the case in which the characters of labels can be written from top to bottom and/or in two lines. We first showed a simple extension of the Wagner-Wolff algorithm and then refined it to reduce the execution time.