Bowyer/Watson algorithm

by Yi Zhang

Bowyer/Watson algorithm is an insertion-point method searching for Delaunay triangulation, like Lawson’s algorithm which rejects unaccpetable triangle by flipping. Bowyer/Watson algorithm generates arbitrage dimensional triangulation by inserting point and examining its neighbors. It is  a popular method due to simplicity and, with improvement from original one, robustness. Here I wrote a demo using Mathematica.

With node set V whose Delaunay triangulation to be computed, first an enclosing triangle is to be assinged, with all the nodes inside the enclosing triangle. Then the iteration begins. In each step an point p\in V is added to the graph, and the following procedures are performed:

  • Among existing triangles, search for those whose circumcircles contain p;
  • Eliminate those triangles, keep the rest;
  • Connect all the nodes whose triangles are just eliminated to p;
  • Insert next point.

Some steps are like this

As to writing a code for this procedure, two things are fundamental: determine whether a new point belongs to certain triangle; for a triangle to be eliminated, determine which edge to keep and which not. The efficiency of those procedures highly depends on the data structure and the method searching triangles whose circumcirlce containing new point. As to the latter, one can first identify the triangle in which new point lies, then test its neighbours, and those neighbouring the qualified neighbours….

When the last point is inserted and the iteration is done, we have the red graph show above as the final Delaunay triangulation, with enclosing to be removed. The result is the same as the PlanarGraphPlot output from Mathematica, shown in the last plot above.

Advertisements