Meshes from points

It's been an hard job, but an interesting experience. My 3D engine "PLT" now features its own Delaunay triangulation. Now I can turn an arbitrary set of points into a continue, smooth, tridimensional mesh.

The algorythm is well explained on Wikipedia, and practically consists in breaking an encompassing triangle in smaller ones, ensuring that every triangle does not "contain" any other vertex.

This check is the heart of the algorythm and it's achieved by verifying that every vertex lie outside the circle identified by the three points of each triangle.

There's a lot of geometry, trigonometry and even a little bit of calculus inside of this piece of software; the exams of discrete algebra and calculus found a practical, consistent application.

The next step is to speed it up: the algorythm is far from its potential O(n log n) possibilities and must be optimized. It seems to be even greater than the expected O(n²), probably due to the STL internal sorting algorythms.

Thanks to Erazor for the idea and Gerry for the math support. =)