Study on Delaunay Triangulation with the Islets Constraints

DOI: 10.4236/iim.2010.26045   PDF   HTML     5,804 Downloads   9,254 Views  


Aiming at Delaunay triangulation with islets constrains in terrain simulation. A general Delaunay triangulation algorithm for constrained data set with islets is proposed. The algorithm firstly constructs Constrained Delaunay Triangulation with constraint polygons which are inner boundary of islets, then according to topological relations within edge, surface, arc segment, applies bidirectional search to find the triangle in islet, lastly it carries on certain corresponding processing to complete the Delaunay triangulation algorithm with islets. The analyses show the algorithm simple, fast speed. The algorithm can be used in 3-D terrain vision.

Share and Cite:

D. Wei and X. Liu, "Study on Delaunay Triangulation with the Islets Constraints," Intelligent Information Management, Vol. 2 No. 6, 2010, pp. 375-379. doi: 10.4236/iim.2010.26045.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Z. M. Ma and B. Luo, “Entire Optimized Triangulation Algorithm of Delaunay Triangle Network for DEM Construction,” Journal of Chang’an University (Natural Science Edition), Vol. 28, No. 3, 2008, pp. 44-48.
[2] L. P. Chew, “Constrained Delaunay Triangulations,” ACM Symposium on Computational Geometry, Springer-Verlag, Berlin, 1987, pp. 215-222.
[3] L. X. Wu, Y. B. Wang and W. Z. Shi, “Integral Ear Elimination and Virtual Point Based Updating Algorithms for Constraint Delaunay TIN,” Science in China: E, Vol. 51, No. S1, 2008, pp. 135-144.
[4] S. H. Liu, P. G. Cheng and H. H. Chen, “Study of Algorithm for Triangulation of Restrained Data Set with Islets,” Computer Application, Vol. 23, No. 4, 2003, pp. 96-98.
[5] S. G. Deng, M. Chen, et al., “Study on Algorithm for Delaunay Triangular Irregular Network of Islets Constrained Data Field,” Science of Surveying and Mapping, Vol. 32, No. 5, 2007, pp. 63-64.
[6] M. Lamot and B. Zalik, “A Fast Polygon Triangulation Algrithm Based on Uniform Plane Subdivision,” Computers and Graphics, Vol. 27, No. 2, 2003, pp. 239-253.
[7] H. B. Ma, J. T. Guo, et al., “Study on Delaunay Triangulation Algorithm for Polygon with inside Islets,” Journal of Northeastern University (Natural Science), Vol. 30, No. 5, 2009, pp. 733-736.
[8] W. Tang, S. Z. Chen, et al., “An Approach to the Modification of the Triangulation Algorithm with Islets Constrains,” Hydrogeology & Engineering Geology, Vol. 33, No. 5, 2006, pp. 58-60.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.