generating constraints edges randomly for generating an constrained delaunay triangulation

Question

I have implemented the sweep-line approach used by Domiter and Zalik to generate a constrained Delaunay triangulation for a set of points in 2D space in Java. I want to make sure that the code which I've developed truly works for n randomly generated points and k constraint edges among them.

Now using a generic strategy I'd like choose a random point from the set of n vertices and then choose a second random point and have an edge between them might not work since what I understand from the definition of a constrained Delaunay triangulation is that the constraint edges are the edges of a planar straight line graph. Thus they are non-intersecting. If the points are selected at random a check might have to be performed to determine that they do not produce intersecting constraints. That approach may not be efficient at all.

Thus, I was wondering whether somebody knew of an efficient strategy to generate constraints randomly.

Thanks in advance.

Answer 1

You could try a two stage process:

• Generate a small set of random points and construct an un-constrained Delaunay triangulation. You could then randomly select from within the edges of this small triangulation to form the set of constraint edges. Obviously, since the edges come from a triangulation they'll be non-intersecting.

• Append an additional set of random points to the data set and construct the constrained Delaunay triangulation of the full set, imposing the constraint edges found previously.

While I believe this method would be an efficient way to construct a non-intersecting, randomised constrained data set for a triangulation code, a better approach might be to test using real data.

The Triangle package includes a couple of benchmark geometries that might be useful in this regard.

Hope this helps.