Research On The Problems Related To Delaunay Triangulation And Voronoi Diagram In GIS

Geographic information system as an important tool for acquiring, processing,management and analysis of geospatial data has been rapid development in recentyears. Most geospatial data are related to geometry data about the point, line andplane, and the realization of the geometry data in the computer mainly relies oncomputational geometry algorithms. Delaunay Triangulation and Voronoi Diagramstructure as the two important object of study in computational geometry playimportant roles in the function of spatial data display and visualization, and spatialanalysis in GIS. This thesis mainly studies the algorithm problems related toDelaunay Triangulation and Voronoi Diagram in GIS, and discusses the application ofVoronoi Diagram in GIS.Firstly, this thesis introduces the research background and meaning of theproblems related to Delaunay Triangulation and Voronoi Diagram. It also introducesthe related concepts and basic theory, including the definition of the Convex Hull, thedefinition and nature of Delaunay Triangulation, the definition and nature of VoronoiDiagram.Then, the thesis studies the algorithm problem of inserting any constrained lineinto Delaunay Triangulation. By analyzing the relationship between the constrainedline and the original triangulation, it gives the pretreatment method of various kinds ofconstrained lines, and describes the process of inserting any constrained line intoDelaunay Triangulation based on the iterative algorithm.Thirdly, the thesis studies a Voronoi Diagram generation algorithm based onDelaunay Triangulation. It proposes an improved incremental insertion method basedon the convex hull to generate the Delaunay Triangulation for the set of discretepoints, and then the Voronoi Diagram of the point set is generated through theDelaunay Triangulation.Finally, the thesis designs a prototype system based on.NET platform andArcGIS Engine technology to achieve the computational geometry algorithmsresearched before, and makes use of this system to define the city division intodistricts of Wuhu.