Advanced Labeling Algorithms for Digital Maps

在本研究中，我们考虑了地图中点的标签放置问题，得到了以下结果：1。我们首先处理标记问题，其中每个点被分配其优先级。我们考虑了两种情况；在第一种情况下，我们禁止删除点，而在第二种情况下，我们允许删除点。通过扩展无优先级地图标注问题的Wagner-Wolff方法，我们提出了两种情况下的标注算法。如果标签的大小不够小，通常的标注算法不能总是对所有的点进行标注。因此，我们考虑了为未分配标签的点放置带有引线的标签的问题。针对这一问题，我们提出了两种算法，并通过计算机实验证明了它们的有效性。最后，我们开发了标签字符可以从上到下和/或在两行中书写的情况下的标记算法。我们首先展示了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.