Advanced Labeling Algorithms for Digital Maps

数字地图的高级标记算法

• 批准号: 16500018
• 负责人: MASUDA Sumio
• 金额: $ 0.64万
• 依托单位: Kobe University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16500018/
• 关键词: algorithm; map labeling; ラベリング; 地図情報処理

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.

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

项目成果

優先度付き地図ラベル配置問題に対するラベル候補作成法

优先地图标签放置问题的标签候选生成方法

• 发表时间: 2005
• 期刊: 電子情報通信学会2005年総合大会講演論文集 (印刷中)
• 作者: 八木原 勇太;寺田 実;阿部 昇
• 通讯作者: 阿部 昇

地点の優先度を考慮した地図ラベル配置アルゴリズム

考虑点优先级的地图标签放置算法

• 发表时间: 2005
• 期刊: 電子情報通信学会論文誌 Vol.J88-A・No.5
• 作者: Kiyotaka Takasuka;Minoru Terada;Kazutaka Maruyama;舟川 国男
• 通讯作者: 舟川 国男

引出し線を用いた地図ラベル配置アルゴリズム

使用引导线的地图标签放置算法

• 发表时间: 2005
• 期刊: 電子情報通信学会技術研究報告 (印刷中)
• 作者: 柏村 俊太郎;寺田 実;大森 和貴
• 通讯作者: 大森 和貴

引出し線を用いたラベル配置

使用引导线放置标签

• 发表时间: 2006
• 期刊: 電子情報通信学会論文誌 Vol.J89-A・No.3
• 作者: 柏村 俊太朗;寺田 実;Satoshi Fujita;大森 和貴
• 通讯作者: 大森 和貴

Algorithms for the Map Labeling Problem with Priorities

具有优先级的地图标记问题的算法

• 发表时间: 2005
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Japanese Edition) J88-A-5
• 作者: Kunio;Funakawa
• 通讯作者: Funakawa