FEM-based Map Generalization Algorithm And Application In LBS

As one of the core and difficult subject in cartography, map generalization has been thefocus of academia and industry since1960s. Because of the complexity in digital environmentand the difficulty to solve, map generalization becomes the most challenging and creativeresearch field in modern cartography.Line elements account for more than80%of the geographic elements, andline-simplification algorithm is the core algorithm in line generalization algorithms. Thesimplification of line elements is to compress a large number of redundant points and extractnecessary points, and keep the main features of line elements for minimum memory space.Based on the idea of elasticity mechanics that the elastomer is subject to the deformation by anyexternal forces and the recovery to an original status by removal of forces, this thesis, by usingthe finite element method to the line simplification, proposes a line-simplification algorithmbased on finite element method (FEM), and applies this algorithm to Location Based Service(LBS).The main research work and innovation are summarized as follows:(1) A line-simplification algorithm is proposed. Combined with the finite element method,this algorithm simplifies lines to achieve simplification on route instead of points. At present, theresearch of FEM-based map generalization is mainly focused on displacement operator andrelatively less on simplification operator. This thesis makes GPS trajectory the research object,simplifying the linear trajectory hierarchically on map scale to improve the map visibility anddisplay efficiency.(2) This algorithm achieves the simplification on graphics features and the cluster analysison semantic features. Using the specificity of GPS trajectory including the semantic features thatmeans each point of the trajectory contains time-info, this algorithm is capable of simultaneouslysimplifying the graphics features and clustering the time for clustering of semantic information,which avoids defect of the traditional simplification algorithm that separates the graphics featureand the semantic feature. This algorithm indicates a better readability after simplification. (3) From a perspective of geometry, three indexed are selected to evaluate the simplificationalgorithm proposed in this thesis. The experiment results show that the simplification algorithmhas a good stability.(4) Combined with the simplification algorithm, a LBS system with functions of real-timemap generalization is achieved, of which the key achievements include the dynamicsimplification service and the semantic analysis service with time features for the historicaltrajectory of moving targets, as well as the clustering of the moving targets. The system is alsoapplied to the ship control and monitoring system of Ningbo frontier inspection station. Byretrieving the position coordinate record of ships from database, the function is capable ofhierarchical record mapping and trajectory simplification according to the resolution at the clientterminal, the measuring scale and other conditions.From an overall point of view, this algorithm comprehensively considers the graphicsfeatures and the semantic features to simplify the trajectory with a good stability, and containsmore semantic information for Location Based Services.