Intelligently Progressive Model for Dense Point Feature Label Placement

Map feature label placement is a strongly subjective problem, which depends on the experience and aesthetic judgement of the map producer.This paper presents the Intelligently Progressive Model (IPM) to solve this problem.The primary outline is as following: firstly divide the problem according to the cartographic rules, then based on the heuristic idea, establish successively the optimal model that harmonizes the appreciation of the label placement result and distributed characteristics of geographic features.We also present the fine revising idea to deal with some cases that the labels are intertwined.The above steps are under the principle of approaching to the optimal result gradually.The approaching loop is controlled by the change of the evaluation value in the optimal model and ends when the optimal value is reached, that is, there is no change of the evaluation value. This paper reviews the development of solution to automated map label placement briefly, and analyzes the characteristics of ES and optimal theory's application in label placement problem.Successively the classification and application of the cartographic rules in the process are explained.In consideration of the computational complexity, that the label placement problem is NP-Hard forces us to find an alternative way that can achieve the globally optimal result.In IPM, the rules are employed respectively according to their limitation to the label.The processes that each rule is stricken down can be sorted according to the rules' complexity.For example, the rule that labels can not overlap any map feature is convenient to tackle by examining the map database through simple process.Then that alleviates seriousness of the whole problem.Afterward the optimal model is explained in which several factors abstracted in the cartographic rules are functioned.In this part the seed cluster is generated at first to produce the placements with the greatest probability according to the formula (1), which is the foundation of further optimizing under formula (2).Then the fine revising method is discussed in which transforming the overlapped labels avoids giving up freely in awkward conditions and enables to improve the working efficiency.As selecting the typical placement, the directions of fine revising is ranked by the preference of relative placements. In automated label placement problem the processing sequence of spatial data is a vital factor that affects the result.The latter placement of spatial point object may give the former more space to deal with revising of the former label placement.In order to handle this problem, the IPM is applied in this paper.The skeleton of IPM is as follows.During some operating, the resultant effect that includes the change of the appreciation of the optimal model and the number of labels is recorded.At the end of the operating whether it is taken again is decided by the judgement from the above effect.This idea is applied to all above steps of label displacement. As an important tool to express the geographical information the map label should function both to illustrate the map feature and to enhance the distributed characteristic of cartographic objects, so the latter should have a weight in the label placement.By inspecting IPM, feasibility that the IPM is exercised to contain this factor can be found.Also the algorithm introduced is applicable to more general placement involving point, line, and area features.