Research On Algorithms Of Computational Geometry In GIS

The content of GIS includes: to gain spatial data, to express spatial data, to process spatial data, to analyse spatial data, to display and visualization spatial data. Finish these elements should use many basic algorithms of computational geometry.Computational geometry is a new strong vitality of the field of theoretical computer science, the result of researching on computational geometry has been widely used in space analyse,computer graphics, chemical, statistical analysis, pattern recognition, geographic database and many other areas.The typical problems of studing computational geometry are made up of Geometric primitives, Geometry researching, Optimizing and others. The geometric primitive includes convex hull, Voronoi diagram, Triangulation problems, Partition problems and Intersection problems. Geometry researching includes Locating a point, Visualization, Geometry researching in a regional and so on.When studing the algorithm of Convex hull and Triangulation problems. This paper finds an error in an important algorithm and improves it; the improved algorithm is more rationalized and efficient. This paper gives out an algorithm of Delaunay triangulation to discrete points based on radial-sweeping compositor and convex hull, which can effectively resolve the degeneracy problem and can educe an equation, validated by experiments, about the number of discrete points, triangles and points on convex hull.When studing the algorithm of geometry researing, this paper puts forward combining vector and ray-crossing algorithm to resolve ray-crossing algorithm's anomalous cases, improving the algorithm of detection a point whether in polygon. When the condition needing much detection to one polygon comes out, this paper put forwards a method of point inclusion test for simple polygons based on forked point. The pre-process of this method is very simple and experiment results show that the method is simple and efficient.