### 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 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 is added to the graph, and the following procedures are performed:

- Among existing triangles, search for those whose circumcircles contain ;

- Eliminate those triangles, keep the rest;

- Connect all the nodes whose triangles are just eliminated to ;

- 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.

[…] Bowyer/Watson algorithm: continue Posted in FEM by Yi Zhang on 08/14/2009 Here is Delaunay triangulation for one thousand random points, using Bowyer/Watson algorithm in my last post. […]

first step in this algorithm is find out a triangle , i read a lot of paper , but still not understand how to find the triangle from a set of points , can you explain to me ?

Email:Renoald@live.com

If it’s the mother triangle we are talking about here, in practice we can use the domain (the area to be examined, because I use generated mesh to solve discretized PDE) to construct a triangle that contains the domain. It’s trivial to find a triangle that covers a known rectangle.

how many triangle need to find on first time ? because your first diagram show three triangle !

Sorry about the confusion, the 1st plot is intended to show the result of picking the 1st node within the mother triangle.

I have another question : since you are using Mathematica , i using matlab , this two software quick similar , for your opinion or suggestion , can i using the build in function Delaunay In matlab to generate mother triangle and implements the Boywer/Watson algorithm ?

I don’t see much difference between the two on this matter. In fact, both matlab and mathmatica have in house packages dealing with Delauney triangulation. I wrote it simply to improve my understanding of the algorithm.