The Methods of Triangulation



4-Evaluation of these Algorithms
There are some criteria for comparison and investigation of these algoritms. These criteria are:
  1. Rapidity: Rapidity criterion is one of the most important criterion for triangulation algorithm because usually large amounts of data are available to be triangulated and therfore time efficiency is crucial.
  2. Accuracy and precision: As we need a reliable surface, triangulation algorithms should be accurate and precise.
  3. Stablity: we mean by stability the uniquness of results in different performances. Because multiple performances are essential in TIN editting this is an important property of the algorithm.
A comparison is made between triangulation algorithms with respect to time complexity by Kramer in 1995[13]. These algorithms are:
  • Insert: randomized insertion algorithm
  • Dewall: Delaunay wall algorithm without searching structre
  • Matrix: with sparse matrix
  • Grid: with regular grid
  • Flipping: flipping algorithm plus computation of the start triangulation
  • PlaneSweep: planesweep algorithm
  • Quadtree: randomized insertion algorithm using a quadtree for locating the enclosing triangle
In Graph 3-1 , horizontal line represents the number of points and vertical line shows the time.


Graph 3-1 : A comparison between triangulation algorithms[13]

As the graph shows, palne sweep algorithm is the most efficient when the number of points are less than 11000 but for more points inceremental algorithm performs better. It shows that data structure play an important role in time efficiency of the algorithms[13].

5-Conclusions and Recommendations
In this article different algorithms for triangulation were investigated and compared together from the view points of rapidity, robustness, reliability and accuracy. It was showed that Delaunay triangulation is the most practical algorithm as it provides unique trianles in different performances.Furthermore, it was showed that data structure is the most important factor that influences the time efficiency of triangulation algorithms.

Non-Delaunay triangulation algorithms are weak in surface modelling, and they are affected by starting point and density of points. These procedures are not repaetable and pridictable. Therefore their use is not recommanded.

Delaunay triangulation algorithms build a uniqe triangulation from a set of points. They are accurate and reliable. The only shortcomming of these algorithms is that they do not take into account the height of points so their robustness is not certain. In that respect an improved Delaunay triangulation that make use of points height in surface modelling is recommended for further study. This is what we intend to implement.

6-References
  1. R.Lattuada and J.Raper, Application of 3D Delaunay algorithms in geoscientific modelling.
  2. S.R. Idelsohn, E.Oņate, N.Calvo, F.Del Pin, Meshless Finite Element Ideas.
  3. Stephan Wise, GIS BASIC, First Published 2002
  4. Christopher B.Jones, Geographical Information Systems and Computer Cartography, 1998
  5. Michael F. Worboys, GIS, A Computing Perspective, 1997
  6. Marc Vigo Anglada, An improved incremental algorithm for constructing restricted Delaunay triangulations
  7. Antoine Vigneron, Computing a Delaunay Triangulation, National of University of Singapore, 2004
  8. George Kontopoulos, Triangulation in 2D space 2D quality meshing algorithm by Ruppert .
  9. Leila De Floriani, Delaunay Triangulation, 2003
  10. Mantena V. Raj u, A Parallel algorithm for Delaunay Triangulation, 2001
  11. Glenn Eguchi, Delaunay Triangulations, Computational Geometry, 2001
  12. Marc Vigo Anglada, An improved incremental algorithm for constructing restricted Delaunay triangulations
  13. Jorge C Kramer, Delaunay triangulation in two and three Dimension, 1995
Page 3 of 3
| Previous |