Delaunay Triangulation
Delaunay Triangulation is used to create a mesh of triangles from a given set of points.
The contents of this page are based on the Triangulate Site. All code has been written from scratch to avoid copyright problems.
| Provided Code | C#, VS-2005 project |
| License | Public Domain |
The algorithm
Delaunay Triangulation uses
create encompassing supertriangle
for each point in vertex_list
clear buffer
for each triangle in triangle_list
if point lies in circumcircle of triangle
remove triangle from triangle list
add triangle edges to buffer
end_if
end_for
remove both copies of all duplicate edges from buffer
add triangles for each remaining edge in the buffer to the triangle list
end_for
The Code Explained
Downloads
The current code base is nothing more than the basic algorithm without any optimizations. In addition, both sample applications are nothing more than proof of concept applications, which the screenshots indicate. I hope to improve both the code base and the sample applications in the distant future.
polygoner.zip
This application allows you to place points in the application windows, which will be used to create a mesh.
stepwise-polygoner.zip
This application allows you to place points in the application windows, which will be used to create a mesh. Clicking the button will perform the triangulation step by step.
Public Domain
The sample code is placed in the public domain.
Creating a Delaunay Triangulation is trivial but tedious, once the algorithm and underlying mathematics are understood. Having to implement the algorithm from scratch in order to be able to claim complete ownership or authorship of an application is a waste of time, if implementations exist.
I dislike waste of time, and I dislike having had to write this code from scratch, just to avoid copyright notices or giving credit for something as simple as this. I hope this code makes it possible for someone else to avoid wasting time.
