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!
|
| _version_ | 1849433878039625728 |
|---|---|
| author | M. Naser Lessani Zhenlong Li Jiqiu Deng Zhiyong Guo |
| author_facet | M. Naser Lessani Zhenlong Li Jiqiu Deng Zhiyong Guo |
| author_sort | M. Naser Lessani |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-f708ff466ac540c5b3c8a6c68798e32c |
| institution | Kabale University |
| issn | 1009-5020 1993-5153 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | Geo-spatial Information Science |
| spelling | doaj-art-f708ff466ac540c5b3c8a6c68798e32c2025-08-20T03:26:52ZengTaylor & Francis GroupGeo-spatial Information Science1009-50201993-51532025-03-0128276177910.1080/10095020.2024.2313326An MPI-based parallel genetic algorithm for multiple geographical feature label placement based on the hybrid of fixed-sliding modelsM. Naser Lessani0Zhenlong Li1Jiqiu Deng2Zhiyong Guo3Geoinformation and Big Data Research Lab, Pennsylvania State University, State College, USAGeoinformation and Big Data Research Lab, Pennsylvania State University, State College, USASchool of Geosciences and Info-Physics, Central South University, Changsha, ChinaSchool of Geosciences and Info-Physics, Central South University, Changsha, ChinaMultiple 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.https://www.tandfonline.com/doi/10.1080/10095020.2024.2313326Label placementfixed positiongeographical featuresparallel genetic algorithmmessage passing interface |
| spellingShingle | M. Naser Lessani Zhenlong Li Jiqiu Deng Zhiyong Guo An MPI-based parallel genetic algorithm for multiple geographical feature label placement based on the hybrid of fixed-sliding models Geo-spatial Information Science Label placement fixed position geographical features parallel genetic algorithm message passing interface |
| title | An MPI-based parallel genetic algorithm for multiple geographical feature label placement based on the hybrid of fixed-sliding models |
| title_full | An MPI-based parallel genetic algorithm for multiple geographical feature label placement based on the hybrid of fixed-sliding models |
| title_fullStr | An MPI-based parallel genetic algorithm for multiple geographical feature label placement based on the hybrid of fixed-sliding models |
| title_full_unstemmed | An MPI-based parallel genetic algorithm for multiple geographical feature label placement based on the hybrid of fixed-sliding models |
| title_short | An MPI-based parallel genetic algorithm for multiple geographical feature label placement based on the hybrid of fixed-sliding models |
| title_sort | mpi based parallel genetic algorithm for multiple geographical feature label placement based on the hybrid of fixed sliding models |
| topic | Label placement fixed position geographical features parallel genetic algorithm message passing interface |
| url | https://www.tandfonline.com/doi/10.1080/10095020.2024.2313326 |
| work_keys_str_mv | AT mnaserlessani anmpibasedparallelgeneticalgorithmformultiplegeographicalfeaturelabelplacementbasedonthehybridoffixedslidingmodels AT zhenlongli anmpibasedparallelgeneticalgorithmformultiplegeographicalfeaturelabelplacementbasedonthehybridoffixedslidingmodels AT jiqiudeng anmpibasedparallelgeneticalgorithmformultiplegeographicalfeaturelabelplacementbasedonthehybridoffixedslidingmodels AT zhiyongguo anmpibasedparallelgeneticalgorithmformultiplegeographicalfeaturelabelplacementbasedonthehybridoffixedslidingmodels AT mnaserlessani mpibasedparallelgeneticalgorithmformultiplegeographicalfeaturelabelplacementbasedonthehybridoffixedslidingmodels AT zhenlongli mpibasedparallelgeneticalgorithmformultiplegeographicalfeaturelabelplacementbasedonthehybridoffixedslidingmodels AT jiqiudeng mpibasedparallelgeneticalgorithmformultiplegeographicalfeaturelabelplacementbasedonthehybridoffixedslidingmodels AT zhiyongguo mpibasedparallelgeneticalgorithmformultiplegeographicalfeaturelabelplacementbasedonthehybridoffixedslidingmodels |