Delaunay Triangulation

Summer vacation marks the arrival of a bunch of free time. In this blog post I'll start by explaining a topic in computational geometry (a mix of computer science and mathematics) called Delaunay Triangulation. I'll end with an example of how this seemingly useless idea can be used to create something visually interesting, tying into the development of my indie game. Jump down to the end if you'd rather skip the technicalities.

Luckily in this current day and age we have an almost limitless resource for information called the internet coupled with a fantastic search engine called Google. Thus if my explanation for "Delaunay Triangulation" doesn't suffice just point your browser to the wikipedia page or google it.

A Delaunay triangulation ensures the resulting triangles end up "nice".
Nice in the sense that they're not overly skinny.

What Exactly is a Delaunay Triangulation?

Given a bunch of points, a Delaunay Triangulation is an arrangement of triangles constructed out of them that satisfies a couple key properties.

Specifically these two properties:

1. The Delaunay Property: for each circle drawn such that its boundary passes through each vertex of a triangle, no point will lie in its interior.
2. Every single point belongs to a triangle.

Below is a simple interactive demo of the technique.

Click Random Points to get started, then Triangulate to generate the triangulation.

How is this done?

The algorithm I'm using along with the source code is given in detail at the Google code project page. In short, though there's really not an easy way to explain it, the process starts with one triangle being constructed and the triangulation is then built outward in a manner that ensures the final result satisfies the Delaunay Property.

Why is this useful?

Triangulation in general has a lot of applications in engineering and computer graphics. What makes Delaunay Triangulation particularly useful is the fact that the resulting triangles are nicer – which speeds up computations requiring a mesh of triangles considerably (see Finite Element Method or, something I've previously worked on, moterpolate to get started).

I'm using it in the loading screen for my Asteroids game mainly to hook players in from the start and also introduce them to the controls but it also causes my game to stand out among the multitude of others on the web. Some cool aspects to this:

• It's interactive.
• It's different everytime (thanks to the use of random numbers and its procedural generation).
• It's visually amusing.

The demo is linked below… enjoy!

It's not perfect, but definitely interesting.
Space bar to shoot, arrow keys to move.