Optimizing map labeling of point features based on an onion peeling approach
Map labeling of point features is the problem of placing text labels to corresponding point features on a map in a way that minimizes overlaps while satisfying basic rules for the quality. This is a critical problem in the application of cartography and geographical information systems (GIS). In thi...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Maine
2011-05-01
|
| Series: | Journal of Spatial Information Science |
| Subjects: | |
| Online Access: | http://josis.org/index.php/josis/article/view/34 |
| _version_ | 1819231853611057152 |
|---|---|
| author | Wan D Bae Shayma Alkobaisi Sada Narayanappa Petr Vojtechovsky Kye Y. Bae |
| author_facet | Wan D Bae Shayma Alkobaisi Sada Narayanappa Petr Vojtechovsky Kye Y. Bae |
| author_sort | Wan D Bae |
| collection | DOAJ |
| description | Map labeling of point features is the problem of placing text labels to corresponding point features on a map in a way that minimizes overlaps while satisfying basic rules for the quality. This is a critical problem in the application of cartography and geographical information systems (GIS). In this paper we study the fundamental issues related to map labeling of point features and develop a new genetic algorithm to solve this problem. We adopt a method called convex onion peeling and utilize it in our proposed convex onion peeling genetic algorithm (COPGA) to efficiently manage map labels of point features. The proposed algorithm takes advantage of a convex onion peeling structure to achieve better map label initialization and to enhance the evolutionary process. The performance of the proposed algorithm was evaluated through extensive experiments on both synthetic and real datasets. In experiments with an implementation of our algorithm using OpenMap, the results show that our genetic algorithm, based on convex onion peeling, is an efficient, robust, and extensible algorithm for automated map labeling of point features. |
| first_indexed | 2024-12-23T11:51:34Z |
| format | Article |
| id | doaj.art-74a0f284237645e3a555dc5261283627 |
| institution | Directory Open Access Journal |
| issn | 1948-660X |
| language | English |
| last_indexed | 2024-12-23T11:51:34Z |
| publishDate | 2011-05-01 |
| publisher | University of Maine |
| record_format | Article |
| series | Journal of Spatial Information Science |
| spelling | doaj.art-74a0f284237645e3a555dc52612836272022-12-21T17:48:12ZengUniversity of MaineJournal of Spatial Information Science1948-660X2011-05-012011232810.5311/JOSIS.2011.2.428Optimizing map labeling of point features based on an onion peeling approachWan D Bae0Shayma Alkobaisi1Sada Narayanappa2Petr Vojtechovsky3Kye Y. Bae4University of Wisconsin-StoutUnited Arab Emirates UniversityJeppesen, Inc.University of DenverDigipen Institute of TechnologyMap labeling of point features is the problem of placing text labels to corresponding point features on a map in a way that minimizes overlaps while satisfying basic rules for the quality. This is a critical problem in the application of cartography and geographical information systems (GIS). In this paper we study the fundamental issues related to map labeling of point features and develop a new genetic algorithm to solve this problem. We adopt a method called convex onion peeling and utilize it in our proposed convex onion peeling genetic algorithm (COPGA) to efficiently manage map labels of point features. The proposed algorithm takes advantage of a convex onion peeling structure to achieve better map label initialization and to enhance the evolutionary process. The performance of the proposed algorithm was evaluated through extensive experiments on both synthetic and real datasets. In experiments with an implementation of our algorithm using OpenMap, the results show that our genetic algorithm, based on convex onion peeling, is an efficient, robust, and extensible algorithm for automated map labeling of point features.http://josis.org/index.php/josis/article/view/34cartographyGIScomputational geometryautomated map labelingonion peelinggenetic algorithmsimulated annealinghill climbing |
| spellingShingle | Wan D Bae Shayma Alkobaisi Sada Narayanappa Petr Vojtechovsky Kye Y. Bae Optimizing map labeling of point features based on an onion peeling approach Journal of Spatial Information Science cartography GIS computational geometry automated map labeling onion peeling genetic algorithm simulated annealing hill climbing |
| title | Optimizing map labeling of point features based on an onion peeling approach |
| title_full | Optimizing map labeling of point features based on an onion peeling approach |
| title_fullStr | Optimizing map labeling of point features based on an onion peeling approach |
| title_full_unstemmed | Optimizing map labeling of point features based on an onion peeling approach |
| title_short | Optimizing map labeling of point features based on an onion peeling approach |
| title_sort | optimizing map labeling of point features based on an onion peeling approach |
| topic | cartography GIS computational geometry automated map labeling onion peeling genetic algorithm simulated annealing hill climbing |
| url | http://josis.org/index.php/josis/article/view/34 |
| work_keys_str_mv | AT wandbae optimizingmaplabelingofpointfeaturesbasedonanonionpeelingapproach AT shaymaalkobaisi optimizingmaplabelingofpointfeaturesbasedonanonionpeelingapproach AT sadanarayanappa optimizingmaplabelingofpointfeaturesbasedonanonionpeelingapproach AT petrvojtechovsky optimizingmaplabelingofpointfeaturesbasedonanonionpeelingapproach AT kyeybae optimizingmaplabelingofpointfeaturesbasedonanonionpeelingapproach |