I’ve been experimenting with mesh generation, specifically Delaunay triangulation. The concept is very simple:
A circle circumscribing any 3 points (3 points define a triangle and a circle) will not encompass any other points in the set.
The following image from Wikipedia shows the circles that circumscribe each of the triangles.
I wrote some code in C++ that would perform the triangulation of an arbitrary set of points in two dimensions. The code is probably not very efficient but it does the job. The code can generate a .svg file of the triangulation as well as print out the triangles/vertices to a text file so that it can be imported into some other application. Here is an image of the triangulation of a random set of points:
The code uses a K-dimensional tree structure to find nearest neighbours to increase the speed of the mesh generation. Download the code from git hub using the following
git clone git://github.com/rabidgeek/Mesh-Triangulation.git
Or use the following director link if you do not have git.