Research on Map Labeling Problems in Geographic Information System

在二维地图中自动放置对应于图形特征的文本或符号标签在若干应用领域中是重要的。在地图中，区域、河流和车站等的标签（或名称），被放置在适当的位置理解。在哪里放置这些标签对于地图的可读性很重要。放置这样的标签的问题被称为地图标注问题。本研究计画的目的是发展有效的演算法，并探讨与此问题相关的议题。其中一个是标签数量最大化问题，另一个是标签大小最大化问题。首先，我们考虑了标记数字数据绘制的地图中的点和曲线的标记数最大化问题。在离散模型中，我们必须管理许多候选位置，并且不能以精细的量调整标签位置。因此，我们使用连续的标记空间的点和曲线，并提出了有效的算法。然而，由于许多点可能密集地分布，因此点的标记空间可能是空的。我们知道，在这种情况下，不可能把所有的点都放进去。解决此问题的一种方法是使用引线放置标签。我们用引导线建立模型。文中提出了一些实用的算法，并给出了计算结果。对于标签大小最大化问题，我们也可以开发有效的算法。当我们考虑将这个问题应用到智能交通系统时，我们必须保持几何数据的动态变化，并且我们研究了这种情况。此外，在应用领域中，有许多问题与标号问题有很强的联系，我们也考虑了这些问题。

The automatic placement of text or symbol labels corresponding to graphical features in two dimensional maps is important in several application areas. In maps, labels (or names) of regions, rivers and stations, etc., are placed in appropriate positions understood. Where to place such labels is important for readability of a map. The problem of placing such labels is called the map labeling problem. The aim of this research project is to develop efficient algorithms for the problem, and we also investigate topics having connection with this problem.There are two types for the labeling problem. One of them is the label number maximization problem, and the other is the label size maximization problem. First, we considered the label number maximization problem for labeling points and curves in maps drawn from digital data. In discrete models, we have to manage many candidate positions and cannot adjust label positions by fine amounts. Therefore, we used continuous labeling spaces for points and curves, and proposed efficient algorithms. However, as many points may be distributed densely, the labeling space for a point could be empty. We know that it is impossible to place all the points in this case. One approach to this problem is placing labels using leader lines. We formulate the model with leader lines. Some practical algorithms are proposed in this project and computational results are also shown. For the label size maximization problem, we can develop efficient algorithms, too.When we consider the application of this problem to Intelligent Transport System, we have to maintain dynamic change of geometric data, and we investigate such cases.~ Moreover, there are many problems having strong connection with the labeling problem in application areas, we also consider those problems.