The Displacement Method Research Of Conflict Solution Relate To Buildings And Roads

Map generalization is a complex and abstract process, and it is also one of the most challenging problems in the map data handling. In the era of digital cartography, not only the concept of map generalization is changed, but also the research field and application range are expanded.The implementation of map generalization has transformed from people-oriented to computer-based procedure that using models and algorithms to make the generalization process automated,intelligent and collaborative.The spatial conflict produced at a scale smaller than the source scale of the map data would confuse the geographic information expressed by map. Conflict can occur when the distance between both map symbols is too small to be distinguishable, or the map symbols increase more than its true cover and overlapping with their adjacent map symbols, or the conflicts are produced by the change of topological relationships aroused by other generalization operators. Therefore, in order to present the map spatial information correctly, it is necessary to solve the spatial conflicts.Displacement is an important method to solve spatial conflicts. Due to the nature of conflict propagation, it is not only to meet the requirement of map clarity, but also to consider the spatial relationships between map objects. Because the correct representation of spatial relationships is a significant prerequisite for spatial information transmission, the characteristic of displacement propagation is a crucial reason to make the displacement operator becoming complexity and difficulty in map generalization. Based on the building cluster and road net, this paper studied how to use displacement algorithm to solve spatial conflicts between buildings and roads. The mainly innovation points and research content are as follows:1) The research background and meaning of map generalization and displacement operator are discussed. We firstly summarize the concept and connotation of map generalization under computer environment, after that we expound the requirement of map generalization. Next, the role and difficulties faced by displacement operator are given. Meanwhile, the research status of displacement algorithm at home and abroad is summarized. The displacement algorithms are mainly based on the two ideas, respectively the sequential methods and global methods. We compare the two kinds of displacement algorithms and analyze the deficiency of existing researches.2) The theoretical foundations of map generalization and displacement operator are elaborated. The main content include conceptual framework of map generalization, the operator and algorithms in generalization, the constraint conditions and the essential issues resolved by map generalization. Meanwhile, the definition and creation conditions of displacement are provided. After that, we also study the menthod of conflict detection and constraints in building and road displacement.3) Using the building cluster in block as research object, we treated the building displacement as an optimization process that buildings searches for the optimal position in a reasonable displacement range. Thus we propose the immune genetic algorithm to resolve spatial conflicts.(1) On the basis of analyzing the fundamental of existing intelligent optimization algorithms of building cluster displacement, genetic algorithm and simulated annealing algorithm, we use the two optimization algorithm into building cluster displacement. The genetic algorithm is applied into building cluster displacement from four aspects:displacement range, gene coding, genetic operator and fitness function. The simulated annealing algorithm is used to building cluster displacement from three aspects:candidate location program, object function and schedule design. Then the experiment results of both algorithms are compared to indicate that the genetic algorithm is better to resolve conflicts, but the simulated annealing algorithm is better to maintain the positional accuracy of buildings.(2) Aim at the insufficient of premature convergence exising in genetic algorithm and Simulated Annealing algorithm, we propose the immune genetic algorithm for building cluster displacement to resolve spatial conflicts, In the immune genetic algorithm, the influence factors of antibody selection is not only related to antibody fitness sorce, but also concerned to antibody concentration. The antibody concentration indicates the proportion that similar antibodies occupying in the population. The greater the concentration of an antibody is, the larger the proportion of similar antibodies is. In order to prevent the non-optimal individuals occupying a larger scale in the population that leads to the premature convergence, immune genetic algorithm maintains the diversity of population through restraining the selection of high concentration individual and promoting the selection of low concentration individual. Meanwhile, immune genetic algorithm can improve the local search ability through using the elite retention strategy to protect the excellent antibodies during evolutionary process. Finally, the adjacent conflict index is established to decrease the time of conflict detecting. The experimental results show that immune genetic algorithm can resolve more conflicts and maintain spatial relationships better.4) In order to meet the constraints in building cluster displacement, we change the population initialization, crossover and mutation operators in immune genetic algorithm and design the new fitness function.For the buildings alignment constraint, we view them as a whole and maintain their displacement amount as the same. For the tangency relations constraint between building and road, we improved the fitness function which composed of remaining conflict amount and displacement distances. The remaining conflict is divided into three kinds:conflict between pair of buildings, conflict between roads and buildings with tangency relations, conflict between roads and buildings without tangency relations. The displacement distance is divided into two kinds:the displacement distance of buildings with tangency relations and the buildings without tangency relations. The five parameters are composed together to set up the fitness function. The experimental results indicate that both building displacement constraints can be met by the immune genetic algorithm considering constraints.5) We present a collaborative process method for road graph generalization and building cluster displacement. The adjacent relationship between road net and building cluster is structured by constrainted Delaunay triangulation (CDT) first. If there is a triangle in CDT between road and building or between pair of buildings, then the adjacent relationship exists between them. Then according to distances between map objects, the adjacent link relationships are established throught those close adjacent relationships. Based on the adjacent link relationships, the collaborative process is divided into three stages:the simplification of road may produce conflict with adjacent buildings, and buildings displace to resolve conflict and maintain relationships between road and buildings; the road net and building cluster are treated as a whole to displace according to adjacent link relationships, and it is mainly to resolve conflicts between roads; the building cluster are displaced to resolve conflict between building and road or between pair of buildings. The displacement algorithm used is snake algorithm. Each line segment in adjacent link relationships is treated as the elementary unit in snake, and making full use of the mechanism that can propagate displacement along the network in snake algorithm, the road simplification collaborate with building cluster displacement to maintain the relationships between road net and building cluster.