| GIS (Geographical Information System ) is a new rising brim subject which is the combination of the computer science , grography , mapping , environment science , space science , geology , information science and manage science . GIS is developing at a very fast speed , and it is widely used in more and more field , such as the management system of city underground pipe-net , integrative management of the city , management of the port , finance management and analysis system , the management and analysis system of the environment , and the population management system . As the widely used of GIS , some basic problems in map display become more and more important and people pay more and more attention to them ,such as label placement , for in no matter what field , the quality of the map display can affect the quality of the software directly.In GIS , three different label-placement tasks are usually identified : labeling of point features (such as cities or mountain peaks ) , line features (such as rivers or roads) , and area features (such as oceas or countries). For the point features labeling ,the text labels must be placed near the labeled feature on maps while avoiding overlaps with cartographic symbols and other labels .For the line features and area features , in spite the avoiding overlaps , the label words should be placed along the features and there should be some distance between each words . If the features are area features , label words should be placed inside the area and along a line in the middle of the polygon the whole way.In this paper , the three label-placement tasks are discussed separately .The point-feature Label Placement (PFLP) has been proved to be NP-hard , so the published algorithms are either have exponential time complaxity or are incomplete . The existing algorithms for PFLP includes the exhaustive search , the greedy algorithms , the discrete gradient descent algorithms , the algorithms of approximating the gradient with overlap vectors , the stochastic search algorithms , the heuristic method and so on .The exhaustive methods are impractical for the running time of the methods will increase rapidly as the number of the input number increases . The discrete gradient algorithms and the algorithms of approximating the gradient with overlap vectors improve greatly in time complexity ,but the algorithms tend to stuck in local minima without getting the final result .The simulated anneling for PFLP(a kind of stochastic gradient-descent method) has the best labeling quality , but the time complexity is high .The Heuristic method based on rules has a comparatively high speed , and is easy to implement ,the Heuristic method is used where the running time is strictly confined .For the line features labeling, the problem is comparatively easier,and is less strict in confining the label placement then PFLP .But it can not be ignored for it is the bridge between the other labeling problem . We could place the label words along the line features by using the functions provided in MapObjects. If added aesthetic feeling is demanded ,the label words can be placed along the line features with some distance between every two words according to coordinates of the line features if the step length is given .For the area features label , from the requirement of the label placement and the characteristic of the area features, the requirement could be satisfide by placing the label words on the skeletons of the area polygons .The published algorithms are summarized in this paper . The definition of skeleton was given by Blum , many researches about skeleton were done sine then .But the existing algorithms by now are mostly used handling image—recognizing the shape of image , reconstruct the model ,seldom are for graphic polygon. On the basis of summarization and compare former algorithms ,the approximate skeleton method for 2-D polygons based on center of gravity is put forward .The algorithms runs in time O(n),where n is the total number of vertices in the polyg...
|
PDF Full Text Request