|
|||||
|
|
A two-phase algorithm for point-feature cartographic label placement |
|
| Authors: | Yuan Ding Nan Jiang Changbin Wu Xinxin Zhou |
| Institution: | 1.Key Laboratory of Virtual Geographic Environment, Ministry of Education,Nanjing Normal University,Nanjing,China;2.College of Geographic Sciences,Nanjing Normal University,Nanjing,China;3.Jiangsu Center for Collaborative Innovation in Geographic Information Resource Development and Application,Nanjing,China |
| Abstract: | Point-feature cartographic label placement (PFCLP) involves placing labels adjacent to their corresponding point features on a map. A widely accepted goal of PFCLP is to maximize the number of conflict-free labels. This paper presents an algorithm for PFCLP based on the four-slider (4S) model. The algorithm is composed of two phases: an initialization phase during which an initial solution is constructed by an exact algorithm and a heuristic method to maximize the probability of conflict-free labels. The initialization phase is followed by an improvement phase that adopts a backtracking greedy search. The exact algorithm can find a portion of the conflict-free labels in an optimal solution and an extension of the exact algorithm is provided that can find additional conflict-free labels. Computational tests were performed for instances based on standard sets. The two-phase algorithm generated better solutions relative to all methods previously reported in the literature. It also executes at a reasonable speed and is more stable than most other methods. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |