Abstract:
|
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 applications, showing their robustness and efficiency, even in the case that the original graph has many vertices or edges. |