Research on Map Labeling Problems in Geographic Information System

地理信息系统中的地图标注问题研究

• 批准号: 13680424
• 负责人: IMAI Keiko
• 金额: $ 2.24万
• 依托单位: Chuo University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680424/
• 关键词: computational geometry; geographical information system; map labeling problem; digital map data; intelligent transport system; online labeling; labeling with leder lines; guide map

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.

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

项目成果

Y.Asano, H.Imai, M.Toyoda, M.Kitsuregawa: "Finding Neighbor Communities in the Web using Inter-site Graph"Proceedings on the 14th International Conference on Database and Expert Systems Applications, Lecture Notes in Computer Science. 2736. 558-568 (2003)

Y.Asano、H.Imai、M.Toyoda、M.Kitsurekawa：“使用站点间图在网络中查找邻居社区”第 14 届数据库和专家系统应用国际会议论文集，计算机科学讲义。

御厨健一, 今井桂子: "道案内図に対するラベル配置"地理情報システム学会 第7回空間ITワークショップ予稿集. 14-21 (2003)

Kenichi Mikuriya、Keiko Imai：“路线指南地图上的标签放置”地理信息系统协会第七届空间 IT 研讨会论文集 14-21 (2003)。

今井桂子, 亀田 貴之, 大塚善仁, 佐竹直也: "地図におけるラベル配置問題 - 点と辺に対する解法の実験的評価"「第7回"統合型地理情報システム"シンポジウム」予稿集. 23-30 (2001)

Keiko Imai、Takayuki Kameda、Yoshihito Otsuka、Naoya Satake：“地图中的标签放置问题 - 点和边解决方案的实验评估”第七届“综合地理信息系统”研讨会论文集 23-30（2001））。

Y.Ohtsuka, K.Imai: "Node Label Placement Problems with Leader Lines"IPSJ SIG Technical Reports. 2001-AL-79. 53-58 (2001)

Y.Ohtsuka、K.Imai：“引导线的节点标签放置问题”IPSJ SIG 技术报告。

Y.Asano, H.Imai, M.Toyoda, M.Kitsuregawa: "Applying the Site Information to the Information Retrieval from the Web"3rd International Conference on Web Information Systems Engineering, IEEE CS Press. December 2002. 83-92 (2002)

Y.Asano、H.Imai、M.Toyoda、M.Kitsurekawa：“将站点信息应用于网络信息检索”第三届网络信息系统工程国际会议，IEEE CS Press。