Lawson Delaunay triangulation algorithm implemented with Quad-Edges

Example of a Delaunay triangulation computed with a QuadEdge data structure.

This example uses a refinement algorithm where we compute a giant triangle surrounding all the sites, then insert them one by one while keeping the triangulation.

The geometric predicates (inCircle and isRightOf) have not been made robust. The envelope has been left gray.

Clicking on a triangle displays its circumscribed circle, it should be empty.

Open your debug panel a to see the algorithm working.

There is a strategically placed "debugger" instruction, open you debug panel, reload the page and click run multiple times to see the algorithm working.

Ex.: The site V18 has been inserted, the green edges where initially added, the red edges are the result of flipping some edges to maintain conformity, in orange we see the polygon that has been affected (it's the same as the "star shaped polygon" of Bowyer-Watson)