Convex onion peeling genetic algorithm: An efficient solution to map labeling of point-feature

Map labeling of point-feature 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 problem is a critical problem in the applications of cartography and Geographical Information Systems (GIS). In this paper we study the fundamental issues related to map labeling of point-feature and develop a new genetic algorithm to solve this problem. We adopt a data structure called convex onion peeling and utilize it in our proposed Convex Onion Peeling Genetic Algorithm (COPGA) to efficiently manage point features. We evaluated the performance of the proposed algorithm through extensive experiments on both synthetic and real datasets. The experimental results show that our genetic algorithm based on the convex onion peeling structure is an efficient, robust and extensible algorithm for automated map labeling of point-feature.