1. An MPI-based parallel genetic algorithm for multiple geographical feature label placement based on the hybrid of fixed-sliding models
- Author
-
M. Naser Lessani, Zhenlong Li, Jiqiu Deng, and Zhiyong Guo
- Subjects
Label placement ,fixed position ,geographical features ,parallel genetic algorithm ,message passing interface ,Mathematical geography. Cartography ,GA1-1776 ,Geodesy ,QB275-343 - Abstract
Multiple Geographical Feature Label Placement (MGFLP) has been a fundamental problem in geographic information visualization for decades. Moreover, the nature of label positioning has proven to be an Nondeterministic polynomial-time hard (NP-hard) problem. Although advances in computer technology and robust approaches have addressed the problem of label positioning, the lengthy running time of MGFLP has not been a major focus of recent studies. Based on a hybrid of the fixed-position and sliding models, a Message Passing Interface (MPI) parallel genetic algorithm is proposed in the present study for MGFLP to label mixed types of geographical features. To evaluate the quality of label placement, a quality function is defined based on four quality metrics: label-feature conflict; label-label conflict; label association with the corresponding feature; label position priority for all three types of features. The experimental results show that the proposed algorithm outperforms the DDEGA, DDEGA-NM, and Parallel-MS in both label placement quality and computation time efficiency. Across three datasets, compared to Parallel-MS, running times decreased from 118.45 to 8.34, 45.98 to 3.51, and 20.01 to 0.43 min, with further reductions in label-label and label-feature conflicts.
- Published
- 2024
- Full Text
- View/download PDF