GISdevelopment.net --> Application --> Miscellaneous
S.Behzadi (Presenting Author)
M.Sc. Student, Dept. of GIS Eng.
Email: behzadi@sina.kntu.ac.ir
Ali A. Alesheikh
Associate Professor, Dept. of GIS Eng.
Email: alesheikh@kntu.ac.ir
Faculty of Geodesy and Geomatics Eng. K.N.Toosi University of Technology
No 1346, Mirdamad cross, Valiasr st., Tehran, Iran 19967-15433
Abstract
Surface reconstruction by means of triangulation of point data is a common practice in Geospatial Information Systems (GIS). Various triangulation algorithms are proposed for Digital Terrain Model (DTM) generation. Varying in computational efficiency, most triangulation methods lead to computationally complex optimization problems. The algorithms use only (x, y) coordinates of points to generate triangles, while considering the third dimensional information (Z) as well as the topology of the study area can improve significantly the quality of approximation.
In this paper, an improved algorithm is proposed in which three dimensional information together with area topology are considered. In this method, one or many tree graphs will be made using sampling points. It then generates triangles by tracking the connections between points.
The new algorithm has some attractive features, such as the potential of obtaining more accurate results. This paper evaluates the existing triangulation algorithms. Several case studies are made to compare the results and present the advantages of the method. The result of performance analysis of the new algorithm is encouraging.
1.The disadvantages of triangulation
In triangulation, a set of triangles is created. The purpose of creating these triangles is that they must be equilateral. In triangulation, stableness is only important. In some of triangulation method, (x, y) components are only used to make triangles though each points in these triangles has three components (x, y, z). These triangles are horizontally stable but they may not always be the solution of the problem because they are only made by two components (x, y). For example 4 points are showed in (figure 1-a) and the best triangles are showed in (figure 1-b) [2].
If there exists a thalweg line near points 1 and 3 (figure 1-c) then the triangle in (figure 1-d) is the best solution for the process.
These triangles are less stable than the triangle in (figure 1-b) but they are the answer of the problem because in these triangles, third component (z) is used.
Fig 1: a: four sample points in an area, b: triangulation with two components, c: four sample points in an area with additional parameter, d: triangulation with additional parameter
2.The disadvantages of making DTM with mathematical approach:
In these approaches, mathematical computations are used such as Inversed Distance Weighting (IDW). At first, a set of points is selected around an unknown point. The number of these points and the slope of the area around the unknown point are not known. Then the value of the unknown point cannot be calculated exactly. Then there is no confidence to the value that is calculated for the unknown point. For example (figure 2-a) if first set is used to calculate the value of unknown point a value is achieved that is not equal to a value that achieve by using second set of points. These values may be near the real value of unknown point. Hence, choosing different points makes different results [4].
3.What is snowing layer?
The main idea in this method is achieved by observing the nature. In this method, a new relationship is described between the sampling points. The result of this relationship is one or many tree graphs. In this method, a layer that is similar to snowing layer is used. When the weather is snowing, snowflakes covered the area with a white layer and the white layer is made on this area. This layer is the DTM of the area. The first point of area which meets the layer is the highest point in the area (figure 2-b).
The landing of this layer will continue. Then other points around the highest point are covered by this layer. By decreasing the height of this layer more points are covered and the distance between these new covered point and highest points increase. The process continues until this layer meets another peak of mountain (this point is as high as other point in this step but the distance between this point (peak point) and other points is longer than the distance between other points with each others)-(figure 2-c).
Fig 2: a: finding unknown point by IDW, b: snowing layer and the area, c: the area was covered with the snowing layer, d: covered area with snowing layer,uncovered area with snowing layer
This process continues until the layer meets other peaks of mountain, thus this layer covers all area.
4.Mathematical expression for snowing layer:
In this section, a spatial connection between sampling points is made base on snowing layer idea. In this connection all components of each point are used. At first, all points in the area are ranked base on their height (z) and the position of these point is not important then these points are put in the S set S(: a set of ordered points base on their height - S: a set of points which are selected and covered by snowing layer). The highest point in set is selected and it is put in set. Then the second point in set is selected then it is connected to neatest point in set (now there is only one point in set). This process continues and other points in set is selected and connected to nearest point in set (figure 2-d).
Each point which is selected from set will be connected to nearest point in set then it will be put in set. This process will continue until all points in set are transferred to set (figure 4-a).
The distance between the selected points in set and nearest point in set d >> + is a constant value with a little tolerance (S). If the selected point in set has a much distance (S) with the nearest point in set (S), then this new point is a new peak in this area and it is put in S set without any connection with other points in S set. Other peaks are discovered by this condition thus in this approach, all component of each points are used in selecting point and connection between points. This new algorithm is executed on the sampling points of an area and the result of execution of this algorithm is showed by figure 4-a.
The heights of a few points are calculated that is showed by figure 4-b: The resulting surface is a curved surface because the equation that makes this surface is a weighted mean equation (the weight of each vector is the distance between another vector and unknown point divided on sum of the distance between two vectors and unknown points). The value of each unknown point is calculated by this surface. Whenever the unknown point is near to a vector, it follows the shape and the direction of that vector as a result there is no fracture on the edge.
5.Calculating the unknown quantity (z) :
At the previous step, the relationship and connection between points are determined. In this step, the unknown component of each point (z) is calculated by using the vectors which were made at the previous step.
The two nearest vectors of each point are used to calculate the unknown component of that point. Two vectors have three cases with each others in the 3D space:
These cases are showed by figure 3-a, b, c.
Fig 3: a, b, c: the cases of two vectors in 3D space
Since these two vectors are the nearest vectors to unknown point, they have the most effect on the value of the unknown point. These vectors are created base on the shape of the area then the calculated value of unknown component has a high accuracy.
The intersected and parallel cases are spatial cases of avert.
In case (c):
If then it will change to case (a)
If then it will change to case (b)
Then the (aversion) case will be investigated and the unknown component is calculated by equation 1 and figure 3-d:
: The height of point on
: The height of point on
The heights of a few points are calculated that is showed by figure 4-b:
The resulting surface is a curved surface because the equation that makes this surface is a weighted mean equation (the weight of each vector is the distance between another vector and unknown point divided on sum of the distance between two vectors and unknown points). The value of each unknown point is calculated by this surface.
Whenever the unknown point is near to a vector, it follows the shape and the direction of that vector as a result there is no fracture on the edge.
6.Conclusions:
In this paper, a new strategy for creating optimum triangles is presented. The landing of snowing layer was described by mathematical rules, base on sampling points. There are many differences between the concepts of this method and other methods such as Delaunay triangulation and mathematical methods to make a DTM. The main difference between this method and other methods is that mimics nature but other methods may not. An extended procedure can be derived by making changes and adding different condition on it to make a DTM.
In the presented algorithm, one or many tree graphs will be made by sampling points. The lines of these graphs are the most stable lines. Thus the lines can be used to investigate the accuracy of triangles in triangulation. If these lines correspond to the lines of triangle, essential condition will be reached but this condition is not enough. The lines of these graphs can show the direction of slope and the amount of it dramatically. They can be used instead of contour lines.
In this method, one or many tree graphs will be made by sampling points. A new method can be described for triangulation by continuing the connection between points that each three component (x, y, z) are used to make triangles.
Fig 4: a: the connection in snowing layer and execution of snowing algorithm on sampling data, b: The heights of a few points
7.Reference
An Extended Algorithm for Generating Digital Train Model
S.Behzadi (Presenting Author)
M.Sc. Student, Dept. of GIS Eng.
Email: behzadi@sina.kntu.ac.ir
Ali A. Alesheikh
Associate Professor, Dept. of GIS Eng.
Email: alesheikh@kntu.ac.ir
Faculty of Geodesy and Geomatics Eng. K.N.Toosi University of Technology
No 1346, Mirdamad cross, Valiasr st., Tehran, Iran 19967-15433
Abstract
Surface reconstruction by means of triangulation of point data is a common practice in Geospatial Information Systems (GIS). Various triangulation algorithms are proposed for Digital Terrain Model (DTM) generation. Varying in computational efficiency, most triangulation methods lead to computationally complex optimization problems. The algorithms use only (x, y) coordinates of points to generate triangles, while considering the third dimensional information (Z) as well as the topology of the study area can improve significantly the quality of approximation.
In this paper, an improved algorithm is proposed in which three dimensional information together with area topology are considered. In this method, one or many tree graphs will be made using sampling points. It then generates triangles by tracking the connections between points.
The new algorithm has some attractive features, such as the potential of obtaining more accurate results. This paper evaluates the existing triangulation algorithms. Several case studies are made to compare the results and present the advantages of the method. The result of performance analysis of the new algorithm is encouraging.
1.The disadvantages of triangulation
In triangulation, a set of triangles is created. The purpose of creating these triangles is that they must be equilateral. In triangulation, stableness is only important. In some of triangulation method, (x, y) components are only used to make triangles though each points in these triangles has three components (x, y, z). These triangles are horizontally stable but they may not always be the solution of the problem because they are only made by two components (x, y). For example 4 points are showed in (figure 1-a) and the best triangles are showed in (figure 1-b) [2].
If there exists a thalweg line near points 1 and 3 (figure 1-c) then the triangle in (figure 1-d) is the best solution for the process.
These triangles are less stable than the triangle in (figure 1-b) but they are the answer of the problem because in these triangles, third component (z) is used.
Fig 1: a: four sample points in an area, b: triangulation with two components, c: four sample points in an area with additional parameter, d: triangulation with additional parameter
2.The disadvantages of making DTM with mathematical approach:
In these approaches, mathematical computations are used such as Inversed Distance Weighting (IDW). At first, a set of points is selected around an unknown point. The number of these points and the slope of the area around the unknown point are not known. Then the value of the unknown point cannot be calculated exactly. Then there is no confidence to the value that is calculated for the unknown point. For example (figure 2-a) if first set is used to calculate the value of unknown point a value is achieved that is not equal to a value that achieve by using second set of points. These values may be near the real value of unknown point. Hence, choosing different points makes different results [4].
3.What is snowing layer?
The main idea in this method is achieved by observing the nature. In this method, a new relationship is described between the sampling points. The result of this relationship is one or many tree graphs. In this method, a layer that is similar to snowing layer is used. When the weather is snowing, snowflakes covered the area with a white layer and the white layer is made on this area. This layer is the DTM of the area. The first point of area which meets the layer is the highest point in the area (figure 2-b).
The landing of this layer will continue. Then other points around the highest point are covered by this layer. By decreasing the height of this layer more points are covered and the distance between these new covered point and highest points increase. The process continues until this layer meets another peak of mountain (this point is as high as other point in this step but the distance between this point (peak point) and other points is longer than the distance between other points with each others)-(figure 2-c).
Fig 2: a: finding unknown point by IDW, b: snowing layer and the area, c: the area was covered with the snowing layer, d: covered area with snowing layer,uncovered area with snowing layer
This process continues until the layer meets other peaks of mountain, thus this layer covers all area.
4.Mathematical expression for snowing layer:
In this section, a spatial connection between sampling points is made base on snowing layer idea. In this connection all components of each point are used. At first, all points in the area are ranked base on their height (z) and the position of these point is not important then these points are put in the S set S(: a set of ordered points base on their height - S: a set of points which are selected and covered by snowing layer). The highest point in set is selected and it is put in set. Then the second point in set is selected then it is connected to neatest point in set (now there is only one point in set). This process continues and other points in set is selected and connected to nearest point in set (figure 2-d).
Each point which is selected from set will be connected to nearest point in set then it will be put in set. This process will continue until all points in set are transferred to set (figure 4-a).
The distance between the selected points in set and nearest point in set d >> + is a constant value with a little tolerance (S). If the selected point in set has a much distance (S) with the nearest point in set (S), then this new point is a new peak in this area and it is put in S set without any connection with other points in S set. Other peaks are discovered by this condition thus in this approach, all component of each points are used in selecting point and connection between points. This new algorithm is executed on the sampling points of an area and the result of execution of this algorithm is showed by figure 4-a.
The heights of a few points are calculated that is showed by figure 4-b: The resulting surface is a curved surface because the equation that makes this surface is a weighted mean equation (the weight of each vector is the distance between another vector and unknown point divided on sum of the distance between two vectors and unknown points). The value of each unknown point is calculated by this surface. Whenever the unknown point is near to a vector, it follows the shape and the direction of that vector as a result there is no fracture on the edge.
5.Calculating the unknown quantity (z) :
At the previous step, the relationship and connection between points are determined. In this step, the unknown component of each point (z) is calculated by using the vectors which were made at the previous step.
The two nearest vectors of each point are used to calculate the unknown component of that point. Two vectors have three cases with each others in the 3D space:
- Two vectors can intersect
- Two vectors can be parallel
- Two vectors can avert
These cases are showed by figure 3-a, b, c.
Fig 3: a, b, c: the cases of two vectors in 3D space
Since these two vectors are the nearest vectors to unknown point, they have the most effect on the value of the unknown point. These vectors are created base on the shape of the area then the calculated value of unknown component has a high accuracy.
The intersected and parallel cases are spatial cases of avert.
In case (c):
If then it will change to case (a)
If then it will change to case (b)
Then the (aversion) case will be investigated and the unknown component is calculated by equation 1 and figure 3-d:
: The height of point on
: The height of point on
The heights of a few points are calculated that is showed by figure 4-b:
The resulting surface is a curved surface because the equation that makes this surface is a weighted mean equation (the weight of each vector is the distance between another vector and unknown point divided on sum of the distance between two vectors and unknown points). The value of each unknown point is calculated by this surface.
Whenever the unknown point is near to a vector, it follows the shape and the direction of that vector as a result there is no fracture on the edge.
6.Conclusions:
In this paper, a new strategy for creating optimum triangles is presented. The landing of snowing layer was described by mathematical rules, base on sampling points. There are many differences between the concepts of this method and other methods such as Delaunay triangulation and mathematical methods to make a DTM. The main difference between this method and other methods is that mimics nature but other methods may not. An extended procedure can be derived by making changes and adding different condition on it to make a DTM.
In the presented algorithm, one or many tree graphs will be made by sampling points. The lines of these graphs are the most stable lines. Thus the lines can be used to investigate the accuracy of triangles in triangulation. If these lines correspond to the lines of triangle, essential condition will be reached but this condition is not enough. The lines of these graphs can show the direction of slope and the amount of it dramatically. They can be used instead of contour lines.
In this method, one or many tree graphs will be made by sampling points. A new method can be described for triangulation by continuing the connection between points that each three component (x, y, z) are used to make triangles.
Fig 4: a: the connection in snowing layer and execution of snowing algorithm on sampling data, b: The heights of a few points
7.Reference
- Burrough P.A., McDonnell R., 1998, Principles of geographical information systems for land resources assessment
- EL_Sheimy N., Digital Terrain Modelling
- Findlay D., June 2005, Working with Digital Elevation Models and Digital Terrain Models in ArcView 3.2,
- Rolf A., de By Richard A. Knippers, Yuxian Sun, Martin C. Ellis, Menno-Jan Kraak, Michael J. C.Weir, Yola Georgiadou, Mostafa M. Radwan, Cees J. vanWesten, Wolfgang Kainz, Edmund J. Sides, PRINCIPLES OF GEOGRAPHIC INFORMATION SYSTEMS, VERSION OF 25TH JANUARY 2001.
- Shojaee D., Alesheikh A.A, Helali H., TRIANGULATION FOR SURFACE MODELLING