ABSTRACT
The Delaunay triangulation of constrained data set is widely used in Geographic Information System (GIS), geo-science, computational geometry, multi-resolution and high precision DTM, et al. This paper briefly analyses some existing Delaunay triangulation algorithms and constrained algorithms, and a detailed description of data structure based on DCEL Divide and Conquer algorithm and Constraint insertion algorithm. This paper design and implementation of constrained Delaunay triangulation general idea is two-step system, first implementation of unconstraint Delaunay triangulation (Initial triangulation), and then embed them into Constrained Segments. Designed and implemented an algorithm GUI demo based on VC, to achieve the purpose of visual observation algorithm. Finally, by experiments adding constraints algorithm performance testing before and after, the results show that the algorithm performance to the actual requirements.
Keywords: Delaunay triangulation, Doubly-Connected Edge List, Divide and conquer, Constrained data set, Two-step system.