A Constrained Delaunay Triangulation Algorithm Based on Incremental Points

Abstract:

The foundation of delaunay triangulation and constrained delaunay triangulation is the basis of three dimensional geographical information system which is one of hot issues of the contemporary era; moreover it is widely applied in finite element methods, terrain modeling and object reconstruction, euclidean minimum spanning tree and other applications. An algorithm for generating constrained delaunay triangulation in two dimensional planes is presented. The algorithm permits constrained edges and polygons (possibly with holes) to be specified in the triangulations, and describes some data structures related to constrained edges and polygons. In order to maintain the delaunay criterion largely，some new incremental points are added onto the constrained ones. After the data set is preprocessed, the foundation of constrained delaunay triangulation is showed as follows: firstly, the constrained edges and polygons generate initial triangulations，then the remained points completes the triangulation . Some pseudo-codes involved in the algorithm are provided. Finally, some conclusions and further studies are given.

• Periodical: Applied Mechanics and Materials (Volumes 90-93)
• Pages: 3277-3282
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.90-93.3277
• Online since: September 2011
• Authors: Bai Chao Wu, Ai Ping Tang, Lian Fa Wang
• Keywords: Computational Geometry, Constrained Delaunay Triangulation, Data Structure, Delaunay Triangulation, Geographical Information System (GIS)

References

[1] KOLINGEROV I, ZALIK B. Improvements to randomized incremental Delaunay insertion [J]. Computers & Graphics, 2002, 26(3): 477-90.

DOI: 10.1016/s0097-8493(02)00090-0

[2] PAUL CHEW L. Constrained delaunay triangulations [J]. Algorithmica, 1989, 4(1): 97-108.

DOI: 10.1007/bf01553881

[3] SU P, SCOT DRYSDALE R L. A comparison of sequential Delaunay triangulation algorithms [J]. Computational Geometry, 1997, 7(5-6): 361-85.

DOI: 10.1016/s0925-7721(96)00025-9

[4] GUIBAS L, KNUTH D, SHARIR M. Randomized incremental construction of Delaunay and Voronoi diagrams [J]. Algorithmica, 1992, 7(1): 381-413.

DOI: 10.1007/bf01758770

[5] MUCKE E P, SAIAS I, ZHU B. Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations [M]. Proceedings of the twelfth annual symposium on Computational geometry. Philadelphia, Pennsylvania, United States; ACM. 1996: 274-83.

DOI: 10.1145/237218.237396

[6] ŽALIK, BORUT, KOLINGEROV , et al. An incremental construction algorithm for Delaunay triangulation using the nearest-point paradigm [J]. International Journal of Geographical Information Science, 2003, 17(2): 119-38.

DOI: 10.1080/713811749

[7] GUIBAS L, STOLFI J. Primitives for the manipulation of general subdivisions and the computation of Voronoi [J]. ACM Trans Graph, 1985, 4(2): 74-123.

DOI: 10.1145/282918.282923

[8] ANGLADA M V. An improved incremental algorithm for constructing restricted Delaunay triangulations [J]. Computers & Graphics, 21(2): 215-23.

DOI: 10.1016/s0097-8493(96)00085-4

[9] FANG T-P, PIEGL L A. Algorithm for constrained delaunay triangulation [J]. The Visual Computer, 1994, 10(5): 255-65.

DOI: 10.1007/bf01901582

[10] FANG T P, PIEGL L A. Delaunay triangulation using a uniform grid [J]. Computer Graphics and Applications, IEEE, 1993, 13(3): 36-47.

DOI: 10.1109/38.210490

[11] LEE D T, SCHACHTER B J. Two algorithms for constructing a Delaunay triangulation [J]. International Journal of Parallel Programming, 1980, 9(3): 219-42.

[12] DWYER R. A faster divide-and-conquer algorithm for constructing delaunay triangulations [J]. Algorithmica, 1987, 2(1): 137-51.

DOI: 10.1007/bf01840356

[13] DWYER R. Higher-dimensional voronoi diagrams in linear expected time [J]. Discrete & Computational Geometry, 1991, 6(1): 343-67.

DOI: 10.1007/bf02574694

[14] FORTUNE S. A sweepline algorithm for Voronoi diagrams [M]. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States; ACM. 1986: 313-22.

DOI: 10.1145/10515.10549

[15] LEE D, LIN A. Generalized delaunay triangulation for planar graphs [J]. Discrete & Computational Geometry, 1986, 1(1): 201-17.

DOI: 10.1007/bf02187695

[16] BOISSONNAT J-D. Shape reconstruction from planar cross sections [J]. Computer Vision, Graphics, and Image Processing, 1988, 44(1): 1-29.

DOI: 10.1016/s0734-189x(88)80028-8

[17] DE FLORIANI L, PUPPO E. An on-line algorithm for constrained Delaunay triangulation [J]. CVGIP: Graphical Models and Image Processing, 1992, 54(4): 290-300.

DOI: 10.1016/1049-9652(92)90076-a

[18] SLOAN S W. A fast algorithm for generating constrained delaunay triangulations [J]. Computers & Structures, 1993, 47(3): 441-50.

DOI: 10.1016/0045-7949(93)90239-a