Delaunay Triangulations

Delaunay Triangulations

You are going to code the Delaunay Triangulation algorithm we went over in class on Monday. Recall that the algorithm starts with a given triangulation T. The algorithm repeats the following until there are no illegal edges: find an illegal edge e, flip it. That’s it.

As we saw right at the end of class Monday, testing whether an edge is legal can be done using an in-circle? predicate. If ABC and BCD are two triangles sharing the edge BC and ABCD is a convex quadrilateral, then BC is legal if and only if D is outside the circle through A, B, and C. Otherwise, if ABCD is non-convex, we’ll call BC legal. Similarly, any edge of the convex hull is legal. The Predicates tab contains an implementation of the inCircle test.

The Application

The start-up code contains a working DCEL implementation and code for producing a triangulation via the incremental algorithm. It also contains some nifty DCEL exploration commands. When you first load the program, you’ll see it gives you an incremental triangulation of a random point set. Highlighted in red is one half-edge of the DCEL storing the triangulation, and its origin vertex. Use the following commands to navigate the DCEL:

  • +/- Increase or decrease the number of points and select a new random sampling.
  • r Generate a new random set.
  • right/left arrow keys Move the selected half-edge to the next or previous one.
  • t Move to the current half-edge’s twin.

After you complete the first part of the assignment you will also be able to do the following:

  • f Flip an edge.

And after the second part:

  • d Compute the Delaunay triangulation.

Your task

Implement the following 3 functions:

  • DCEL.HalfEdge.isLegal Returns true if and only if the half-edge is legal.
  • DCEL.HalfEdge.flip Flips a half-edge. Should do nothing if the flip is not allowed (because either the half-edge is on the convex hull, or the two triangles next to the half-edge form a non-convex quadrilateral.)
  • delaunify Takes as input a DCEL that is a triangulation. Turns it into a Delaunay triangulation using the algorithm described above. Note: This is in the Algorithms tab.

Some implementation details

I have provided a fully functioning DCEL implementation. One key method, that you may want to use, is DCEL.HalfEdge.remove(), which removes a half-edge from the DCEL. You didn’t have to implement this last week, but its a useful method to have.

Turning it in

Turn it in on Canvas by Monday 11:55pm.