|
The Methods of Triangulation
M. Varshosaz Assistant Professor, Faculty of Geodesy & Geomatics Eng., K.N. Toosi University of Technology K.N. Toosi University of Technology, Vali_Asr St, Tehran , Iran, 19697 Email: varshosazm@kntu.ac.ir H. Helali PhD Student, Faculty of Geodesy & Geomatics Eng., K.N. Toosi University of Technology Email: helali@alborz.kntu.ac.ir D. Shojaee MSc Student, Faculty of Geodesy & Geomatics Eng., K.N. Toosi University of Technology Email: dshojaee@gmail.com 1- Introduction Triangulation is a method for tessellation of domain. In fact triangulation is a common method for surface representation and for building a TIN. Triangulation produces a continuous surface. Important problems in triangulation algorithm are independency from starting point or dispersion of them. Further result must be repeatable and predictable. Therefore the triangulation is made, the aim is to maximize the minimum angles and establish circle condition. In Delaunay Trinangulation circum-circle of any triangle should not contain another point[4]. These unique triangles are independent from starting points or any other parameters. Logically for height interpolation we use nearst point, therefore in triangulation, we connect near points. Most important applications of triangulation are DTM generation, feature surface modelling, computer graphic, scientific visualization, robotic, computer vision, image synthesis, mathematic and natural science. 2- Non-Delaunay Algorithms There are a wide variety of algorithms available to build a triangulation for a set of points. Some of these algorithms are investigated here. 2-1- Greedy Triangulation This algorithm is suitable for triangulation of simple polygons. The objective is to minimize the total edge length in the triangulation. This is achieved by an iterative process that selects the shortest available internal diagonal at each stage. Each of these edges must be tested for intersection with the other edges in the triangulation. In the worst case, all O(n 2 ) diagonals will be considered. This algorithm needs a big array of distance and did not show satisfactory results[5]. 2-2- Triangulation of Garey et.al The algorithm of Garey et.al. (1978) is suitable for the triangulation of simple polygons. With respect to time complexity, this algorithm is more efficient than greedy method. The algorithm proceeds by the first decomposing the polygon into monotone polygons and then triangulating each of the monotone polygons. Let us assume that monotonicity is with respect to the y-axis and that no two different vertices of the polygon have the same y-coordinate. Stage 1 of the algorithm decomposes the polygon into monotone polygons. This stage is essentially the regularization of the polygon. Extra edges are added between vertices of the polygon so that :
2-3- Radial Sweep This method was invented by Mirante and Weingarten in 1982. In this algorithm, central point in set of given points is connected to other points radially (fiqure 2-1-a). In the next step triangles are formed as radial edges are connected together (fiqure 2-1-b). Then convex hull of points is constructed (fiqure 2-1-c). Finally points from their angles are arranged. Some of these triangles may have not good connections. For optimization of these triangles, their neighboring triangles that have a common edge are found. Then a tetrahedral is formed from each two triangles its diagonals are computed. Finally large diagonal is replaced with the short one. This procedure is repeated until no edge changes [8].  Figure 2-1 : Radial sweep triangulation[8]
Page 1 of 3
| Next | |