| The development and wide usage of Digital Earth show a colorful world to human, and become another way to knowledge and truth in the earth and the universe. As a hard-core of the technique of digital earth, 3S attracts more and more attention. The technique of GIS, RS and GPS increases people's ability of understanding and changing the world. The GIS system processes the original data from GPS and RS, and then gives them some definite analysis. So it becomes the BRAIN of 3S.GIS (Geographic information system) developed with amazingly quick speed. Every kind of technique about GIS consummates from day to day. Being the most important part of GIS, Spatial Analysis is not only the difficulty, but also the emphases. In the future, it will become absolutely necessarily part of people's lives, just like water, electricity and gas. What we do in this paper is to enter into a kind of Spatial Neighboring Analysis technique in the Spatial Analysis theory field. Voronoi diagram is a kind of approach to delimitate influenced coverage of an economic object. It is a classic structure in computational geometry, and is used in many aspects such as CAD, GIS and digital earth and so on. In this paper, we design and implement an efficient incremental algorithm for constructing Voronoi diagram of planar point set. The algorithm adopts the technique of Buffering and Data Preprocessing to select a generator and to speed up nearest neighbor search process. It can also deal with the degradation cases, such as co-linearity of three points and co-circularity of four points, and has a high precision in computation. In despite of the theoretic time complexity of the algorithm is O(n2) , the results show that the average time complexity is approximately O(n) .In the whole process of constructing Voronoi Diagram, the paper tries it's best to cut down errors aiming at the process of abnormity. First of all, co-circularity of four points what include an inserting point is dealt with in detail. Secondly, the spatial range of the analysis we talk about isn't consequentially unlimited with practical application in GIS. It has to be restricted by all kinds of factor. As a result, the Voronoi Diagram has it's own edge. Everything affected by the edge is treated with detail by detail. A new point is added to the diagram each time. At the same time other points that have already been added are reassigned to a modified affected coverage. Each new point leads to the several divisions from other affected coverage, which united to new affected coverage belonged to the added point. The polygons cut out from other coverage have not only protruding polygons, but also concave ones. The discriminating method is provided in the paper, and then is the process of merging protruding polygon and concave one. In the GIS based on MapObjects, polygon is discriminated from others with an ordered sequence of polygon's vertices. So the sequence of the polygon's vertices is especially important, the according process is necessary. One of the two abnormities is that several same vertices existing in one polygon. The solution is deleting the redundant vertices. The other is co-linearity of three vertices, and accordingly its solution is to obliterate the vertices between the other two of the three. With the abnormity processing, the algorithm is consummated and the quality of output Voronoi Diagram structure is increased. Good data foundation is provided for the high-level GIS function based on Voronoi Diagram.The Voronoi Diagram can only construct data foundation of GIS function. Derived from Voronoi Diagram, Spatial Analysis and Spatial Neighboring Query have a good future. Using the formulae of society and nature, Spatial Analysis can be solution to every kind of matter. Delimitating spatial object's affected coverage is very difficult, but it is very important to spatial analysis, spatial query, urban planning and regional planning. In practice, we often define the administrative division or geographical unit of a spatial feature as its influential...
|
PDF Full Text Request