An incremental algorithm based on edge swapping for constructing restricted Delaunay triangulations
Marc Vigo Anglada · 1995
This work presents an algorithm that given a generalized planar graph obtains its constrained Delaunay Triangulation (CDT). The proposed method works incrementally based in two procedures, one that inserts a new point in a CDT, and another one that inserts a new constraining edge in the CDT. In particular, an algorithm that obtains the CDT of a given polygon (possibly with holes) is obtained. These algorithms have been implemented and included in several aplications, showing their robustness and eficiency, even in the case that the original graph has many vertices or edges.