Constrained Triangulation

In many cases the triangulation problem may be of constrained nature, that is a set of edges may be prescribed and must appear in the triangulation. One example is the triangulation of a simple polygon. In this case, there is no immediate way to apply the Delaunay triangulation method which has the nice property that the minimum angle of its triangles is maximum over all triangulations.

The constrained triangulation is done with 3 steps:

Regularize the point and edge sets
Use the chain method to decompose the regular PSLG
Triangulate the monotone polygons

The regularization step is done with two plane sweeps, left-to-right and then right-to-left. So the vertices must be sorted by x first. At any time, the edges that intersect the sweepline are considered to be active and are stored in a balanced tree. The edges can be ordered either from bottom to top or vice versa.

Let us consider the left-to-right sweep first. When the sweepline meets a vertex, we first check if the vertex has incoming edge. If not, the vertex if left irregular and we add an edge connecting the vertex with the last vertex passed by the sweep line which lies between the neighboring active edges of the current vertex. If there is incoming or outgoing edges, we have to make changes to the balanced tree. Any incoming edge is deleted and outgoing edge is added.

The right-to-left sweep is similar. The regularized PSLG we got has the following properties:

No two edges intersect (except at vertices)
Each vertex (except the left-most) is joined directly to at least one vertex that lies to the right.
Each vertex (except the right-most) is joined directly to at least one vertex that lies to the left.

Each of the regions of the planar graph resulting from the regularization procedure is a monotone polygon. Now the problem is reduced to the trinagulation of monotone polygons.

The final step is the triangulation of the regularized PSLG. We use the chain method to undertake this task. Interested readers could read "Computational Geometry" by Preparata.

It is possible for the graph to have only one chain. The it can not be triangulated. So convex hull of the point set is added. In our problem, it is easy to undertake this task. One only need to consider the top-most chain and the bottom-most chain.

For the convenience of the above procedures, we use the hashtable to store the edges associated with each vertex. The key for the entry is the vertex. And we use a list to store more than one edges associated with the vertex.

After the regularization step, we need to sort the edges associated with each vertex. In many real problems, only a few points are associated with one vertex. So the sorting time is linear. Even in the worst case, it is clear that the time is still bounded by NlogN, since one edge only has two points associated with it (the starting point and the ending point).

Constrained Triangulation

Back to CS252 Project: Constrained Triangulation