Animation of the advancing front delaunay triangulation algorithm:
1. The first triangle constructed is called a supertriangle. It is an equilateral triangle that entirely contains the convex hull of the points to be triangulated. The vertices of this construction will be removed in the last step, leaving the triangulated network.
2. Points to be triangulated are added one by one. The list of points is ordered by their y co-ordinate.
3. The horizontal red line shown in the animation shows the advancing front. This is a horizontal line passing through the y co-ordinate of the most recent point added to the network.
4. Circumcircles pass through the three vertices of each triangle in the network. As each additional point is added to the structure, triangles who's circumcircle contains the new point are identified. These circumcircles are drawn in red and their associated triangles highlighted yellow and removed.
5. New triangles are formed between the most recently inserted point and the segments of the void left after removing the flagged triangles.
6. The speed of the algorithm is improved by flagging all triangles who's circumcircle is entirely behind the advancing front. Triangles below this line no longer require testing in point 4 above. These are identified in green and then added to the pool of dark grey triangles that no longer need to considered with the addition of each new point.
7. After the final point is added, the vertices of the supertriangle and any triangles that share these vertices are removed.
Each of the frames of this animation were generated using PHP and the GD library.
