Post view

Digital Terrain Models

In the following article we would like to examine how we can digitalize and model existing or new surfaces.

To name only a few applications of such models:

- Find the best position for radio masts or solar power plants
- Simulate noise emissions, and floods
- Calculate Volumes
- Visualization of jobsites, and machine control

The **Mathematical Approach** would be to find a functional model valid for the surface. We can distinguish between considering the complete surface or just a part of the surface. Most ""real"" surfaces are very hard to describe in mathematical models, since they contain a lot of irregular shapes. We could also split the surface into areas (Local Approach) , that are easier to model, but this will create some complications when merging the different areas without generating leaps.

Line based models can map the surface either as a **Profile**

or as Conture lines, connecting points on the same height

Instead of using a mathematical function or a profile we can use points to represent a surface

Imagine a raster to be blended over our surface, now we store on every node of the raster the corresponding height value of the surface.

The figure shows a raster with a low resolution while the right figure shows a raster with a higher resolution. If we have a very complex surface we would need to have a very high raster resolution, resulting in a very big file slowing down future calculations. Furthermore e.g. ridges or special surface features will be mapped blurry since we cannot define special points in the raster.The advantage is that the algorithm and handling of raster data is very easy

An alternative to raster based modeling is Triangulated Irregular Networks (TIN). A TIN models the surface based on a point cloud (Mass points), those points are connected in a network of triangles. After connecting the Mass points with a network of triangles they are called node. Since each point used for the triangulation as a height value, we can interpolate the height of every point on the surface.

As we can see right away one key benefit compared to raster modelling is, that we can define mass points according to the shape of the surface. If the surface is very irregular in one area we can define more mass points, while in areas where the surface shows less irregularity we can use less. If we look at the following figure, we can see that only using 4 points for our surface already gives us 2 options how we can calculate the TIN

The basic idea how to determine what option is the best one is fairly easy: The closer we move to a fix point the better the approximation is, hence every point on a triangle should be as close as possible to a fix point. This is best fitted by an equilateral triangle, or whatever option is close to an equilateral triangle. One way to calculate the best option is the Delaunay Triangulation. The Delaunay algorithm establishes our network based on the following property: Three points establish a Delaunay triangle, if a circle defined by these the points does not include any other mass point.

The figure on the left would show a triangulation valid according to the definition of a Delaunay triangle. On the right figure the mass point 2 is inside the circle defined by the triangle 1,3,4 hence this triangulation is not valid. The implementation of the Delaunay triangulation without any adaption would cause significant computation time.

Therefore we can use algorithms to determine a voronoi diagram of our given set of points (seeds). The voronoi diagram divides the set of points to cells, each point within one cell is closer to the seed of the cell then to any other cell:

Since the voronoi diagram and the Delaunay triangulation are dual graphs we can generate the TIN directly from the voronoi diagram. If we draw lines orthogonal to the voronoi edges trough the seeds and can connect 2 seeds with this line then it is an edge of our Delaunay triangle.

The figure on the left shows the valid Delaunay triangulation, the figure on the right an invalid one(the common edge of both triangles is not perpendicular to the voronoi edge)

Another big advantage of using a TIN is the possibility to make use of breaklines. No triangle in a TIN may cross a breakline, this is useful to model special shapes like ridges. The red polyline in the left picture could be a ridge, by defining a break line we prevent the triangulation crossing the ridge.

Post info

07.12.2015 (1446 days ago)

Rate

Recommend