CONSTRAINING TRIANGULATION TO LINE SEGMENTS: A FAST METHOD FOR CONSTRUCTING CONSTRAINED DELAUNAY TRIANGULATION

"In this paper we present an edge swapping approach for incorporating line segments into triangulation. If the initial triangulation is Delaunay, the algorithm tends to produce optimal Constrained Delaunay triangulation by improving the triangles’ aspect ratios from the local area being constrained. There are two types of methods for constructing Constrained Delaunay Triangulation: straight-forward ones which take both points and line segments as source data and produce constrained triangulation from them at once; and post-processing ones which take an already constructed triangulation and incorporate line segments into it. While most of the existing post-processing approaches clear the triangle’s edges intersected by the line segment being incorporated and fill the opened hole (cavity) by re-triangulating it, the only processing that our algorithm does is to change the triangulation connectivity and to improve the triangles’ aspect ratios through edge swapping. Hereof, it is less expensive in terms of both operating and memory costs. The motivation behind our approach is that most of the existing straight-forward triangulators are too slow and not stable enough. The idea is to use pure Delaunay triangulator to produce an initial Delaunay triangulation and later on to constrain it to the line segments (in other words, to split the processing into two steps, each of which is stable enough and the combination of them works much faster). The algorithm also minimizes the number of the newly introduced triangulation points - new points are added only if any of the line segment’s endpoints does not match an existing triangulation point."