An MPI-based parallel genetic algorithm for multiple geographical feature label placement based on the hybrid of fixed-sliding models
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 an...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2025-03-01
|
| Series: | Geo-spatial Information Science |
| Subjects: | |
| Online Access: | https://www.tandfonline.com/doi/10.1080/10095020.2024.2313326 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1009-5020 1993-5153 |