3D Modeling Of Spatial Complex Entities Based On Discrete Points

The traditional GIS,that is two-dimensional GIS,usually using the plane as the definition domain,and a subset of real number space as a numerical field.Because there is a unique mapping relation between domain and range,the functional relationship resulted from it determines the two-dimensional nature of the traditional GIS.Thus,it has some limitations in the aspect of information display,advanced spatial analysis and processing of complex spatial entities.As a result,two-dimensional GIS has been unable to meet the needs of the development of urban planning and design,resource and environmental management,ecological environment monitoring and protection,geological exploration and measurement,and many other areas of the national economy.In order to overcome its limitations,and more accurately and completely express and reproduce the real three-dimensional spatial information,the two-dimensional GIS must be transformed to three-dimensional GIS,and the three-dimensional modeling acts as the core of three-dimensional GIS.At present,among many 3D modeling algorithms,the 3D Delaunay triangulation algorithm is the most widely used.Because it has many excellent features,such as it has a good mathematical theoretical basis,the local control ability of the grid is strong,the grid cell tends to the regular tetrahedron and so on.These properties ensure that the grid generated by it can better approximate the physical boundary,reproduce the sharp features of the original model,and very suitable for 3D modeling of complex spatial entities.However,due to the complexity of the three-dimensional space,the algorithm still needs further research and improvement.Meanwhile,with the rapid development of surveying and mapping technology,the accuracy of data acquisition has been generally improved,and even the phenomenon of excess precision appears.However,the actual accuracy of spatial analysis is generally lower than results of surveying and mapping.Based on such situation,the paper tries to explore the modeling thought of the movable discrete point without affecting the visual effect and the accuracy of spatial analysis.In the paper,firstly,the 3D Delaunay triangulation algorithm for spatial discrete points is studied,based on the basic idea of the incremental inserting algorithm,the key part of the algorithm is optimized and improved,which includes several aspects,such as data pretreatment,the establishment of the initial tetrahedral mesh,the location of the point and the determination of the Delaunay cavity,the generation of the new tetrahedron and the establishment of the topological relationship,by improving the efficiency of each part in the process of the algorithm,to ensure the quality of the grid,as well as improving the overall efficiency of 3D Delaunay triangulation.As for the modeling algorithm of the movable discrete point,first of all,we must make it clear that the discrete point of the "move" is not arbitrary,and it's necessary to fully consider the characteristics of the original model,so as to determine the appropriate moving rules of discrete points and slightly adjust the original point in a certain range.Under the precondition of without affecting the visual effect and the accuracy of the spatial analysis,the topological relationship among the moving discrete points is easy to establish.Then,the spatial entity modeling is carried out by the location of the moving discrete points.Finally,establishing model evaluation system to compare modeling effects of discrete points moving before and after,in order to test the feasibility of the algorithm.The research of the paper are as follows:(1)Study the problem of two-dimensional convex hull,implement the fast convex hull algorithm with different initial convex hull form,and compare the influence of different initial convex hull forms on the overall efficiency.(2)Deeply study the 3D Delaunay triangulation algorithm based on the incremental inserting algorithm,optimize and improve the key parts in the implementation process,to improve the quality of the grid and the efficiency of the algorithm.(3)Study the problem of data pretreatment of discrete point set,make the originally disorganized discrete point set have local ordering,and improve the efficiency of point positioning.(4)Study the problem of point location in three-dimensional space,improve the efficiency of point positioning so that it is possible to quickly and accurately position of the tetrahedron where the insertion points are.(5)Study the problem of identifying the Delaunay cavity and extracting the boundary of the Delaunay cavity by using the outer sphere criterion.(6)Preliminary inquiry the modeling theory of movable discrete points,study the moving rules and moving algorithm of discrete points.(7)Study the algorithm of generating contour lines,which is based on the distribution of discrete points on the plane,the outline of discrete points is gradually approached by contracting convex hull.(8)Study the algorithm of generating triangulation network between two adjacent contour lines.(9)Molding algorithm of the movable discrete point.Firstly,the discrete points are moved to the corresponding plane,then generate the contour line,finally,the triangulation network is generated between two adjacent contour lines and integrated into a whole.Finally,a large number of experiments are carried out to test the proposed algorithm,the experimental results are analyzed in detail,and some conclusions with certain guiding significance have been drawn.The experimental results show that the improved 3D Delaunay triangulation algorithm and 3D molding algorithm of the movable discrete point are correct and feasible.