Digital Terrain Modeling And Study Of The Algorithm For Shortest Path Between Two Points In 3D Space With Obstacles

The algorithms for DTM modeling based on discrete points and the shortest path problem on DTM are studied in this dissertation. The shortest path problem among polyhedrons in 3D space is also discussed. The display and control of DTM is achieved using OpenGL mode. We improve a dynamic Delaunay triangulation algorithm with constrained points in plane. The points in 3D space are projected into plane and triangulated using the algorithm. These points are mapped back to 3D space to build the TIN digital terrain model. The algorithm is further analyzed to optimize the TIN model and get the ideal Delaunay triangulation mesh. We also introduce the application of the level of detail model in view-dependent TIN simplification and the multi-resolution terrain display. The OpenGL programming is also introduced.Based on the digital terrain model expressed by TIN, A fast algorithm to get the exact shortest path between two points on the TIN is improved. The subdivision method of finding approximate shortest path on TIN model is discussed in this dissertation. The mesh can be refined using subdivision method by inserting new points in the TIN model. Thus we can get the approximate shortest path by Dijkstra algorithm. We improve the method of computing exact shortest distance on complex surface according to the patulous property of the surface in local area. The triangle sequence that every two adjoining triangles shared one edge can be rotated into a plane. Then the distance can be computed between two points in such triangle sequence. The distance we get is straight line or broken lines. As the distance is computed, the path points are also recorded. The exact path points on the TIN are computed according to the property that two intersecting lines' in-angle is equal to out-angle. The case of shortest path with obstacles on the TIN is also considered. We can get the correct direction path that can avoid the polygons by the exact shortest path algorithm. The precision of our algorithm is high. Additionally the shortest path problem among polyhedrons in 3D space is studied.