A parallel genetic algorithm for multiple geographical features label placements
Topics:
Keywords: parallel genetic algorithm; Message Passing Interface; label placement, fixed position, sliding model
Abstract Type: Virtual Paper Abstract
Authors:
Mohammad Naser Lessani, Geoinformation and Big Data Research Laboratory, Department of Geography, University of South Carolina
Zhenlong Li, Geoinformation and Big Data Research Laboratory, Department of Geography, University of South Carolina
,
,
,
,
,
,
,
,
Abstract
Multiple geographical feature label placement (MGFLP) has been a fundamental problem in computer graphic visualization for decades. The nature of label positioning is proven an NP-hard problem, where the complexity of such a problem is directly influenced by the volume of input datasets. Advances in computer technology and robust approaches have addressed the problem of labeling. However, what is less considered in recent studies is the computational complexity of MGFLP, which significantly decreases the adoptability of those recently introduced approaches. In this study, a parallel genetic algorithm is proposed for map label placement to accelerate the process of label positioning based on Message Passing Interface (MPI). In addition, after the optimization phase of the algorithm, label-feature conflicts are removed based on the concept of sliding model; it is the combination of the fixed position model and sliding model indeed. To evaluate the quality of label placement, a quality function is defined based on four quality metrics, label-feature conflict, label-label conflict, label ambiguity factor, and label position priority of points and polygons. Experimental results reveal that the proposed algorithm significantly reduced the overall score of the quality function and the computational time of label placement compared to the previous studies.
A parallel genetic algorithm for multiple geographical features label placements
Category
Virtual Paper Abstract