Multiple Geographical Feature Automatic Label Placement Based On Multiple Candidate Positions In Two Degrees Of Freedom Space

Automatic multiple geographical feature label placement(MGFLP)is a combinatorial optimization problem shown to be an NP-hard problem,and it is a challenge in automatic cartography.Many automatic label placement algorithms for point,line,and area features were put forward.It is a common way to use multiple candidate positions(MCP)for label placement,but the research in this way mostly focuses on point features and does not take all three types of features and all the possible candidate positions into account on the map.Therefore,in this thesis,the concept of degrees of spatial freedom for feature label placement is proposed based on the idea of degrees of freedom of mechanical motion.We define the degrees of freedom(DOF)and its space for feature labels on a planar map so as the potential space,including all the optional candidate positions of each feature label,can be standardized.Based on two degrees of freedom(2-DOF)space,feature reference position(FRP),and certain buffer distance(CBD)from FRP,we studied the methods including generating,calculating,evaluating,and selecting MCP for feature label.By using and improving the discrete differential evolution genetic algorithm(DDEGA),we carried out MGFLP experiments on the same dataset used by DDEGA algorithm.The main research work and achievements in this thesis are as follows:(1)By referring to the idea of mechanical motion,the three degrees of freedom of X,Y,and rotation of the label are converted into the three degrees of freedom of the position,distance,and rotation of the label relative to the map feature,so as to define the plane map feature label space of degrees of freedom.Based on the two degrees of freedom of the reference position and the buffer position,the degree of freedom space that defines the variable range of the label of different feature of points,lines and areas is defined,and the expression forms and methods of the degree of freedom space of different feature are explored.M is divided into buffer positions,and the method and process of generating multiple candidate positions in two degree of freedom space of point,line,and area feature are given.(2)A set of label quality evaluation model based on multiple candidate positions in two degree of freedom space is designed,which includes label conflict factor,label label-feature factor,line feature ambiguity factor,point priority factor,and area priority factor.To solve the problem that the overlay of small-area area features and the label of large-area area features are not in the middle.At the same time,the DDEGA algorithm is improved,and the algorithm is divided into three parts: candidate position generation,label quality evaluation,and genetic process iteration,which improves the operating efficiency of the algorithm,thus forming a DDEGA-NM algorithm suitable for multiple candidate positions in two degrees of freedom space.(3)Based on the DDEGA-NM algorithm,the theoretical limit value calculation,comparison of different algorithms,and exploration of various optimal parameters of the algorithm are carried out.The experimental results show that although the multi-candidate location based on two degrees of freedom space increases the complexity of NP-hard problem,the label placement effect is better than the traditional eight candidate position model by optimizing the performance of the algorithm and increasing the number of iterations;The optimal parameters are: N=8,M=3,the label conflict weight is 0.4,the label label-feature weight is 0.4,and the minimum buffer distance accounts for one 1/8 of the height of the text,and the maximum buffer distance accounts for 4/8 of the height of a text.(4)On the basis of the optimal parameters of the DDEGA-NM algorithm,the algorithm is optimized again,starting from selecting the fittest solutions in the initial population and the genetic iterative process,manual intervention selection before the first iteration,starting from the candidate position of the element with lower score value is selected,and then intervene in random selection after each iteration,so that the combination of label candidate positions is as close to the local optimal combination as possible,so as to reduce the time for the algorithm to find the optimal solution.Experiments on map annotation configuration at different scales show that controlling the initial population quality and the genetic process can improve the quality of automatic label placement and shorten the time to convergent value.The above research results provide a new way for automatic feature label placement.