Study on Delaunay Triangulation with the Islets Constraints

Dong Wei, Xinghua Liu

.

DOI: 10.4236/iim.2010.26045                

Abstract

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.

Keywords

Islets Constraints, Bidirectional Search, Delaunay Triangulation

Conflicts of Interest

The authors declare no conflicts of interest.

References

[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.