Voronoi

I can officially almost add 2D delaunay triangulation (or voronoi diagrams) to the list of things I have implemented (if I actually had a list it would be pretty long by now). But why bother, you ask? Well, every time I have needed Delaunay, which is more often than you would think, I seemed to end up using popen with the program qhull and writing my input data to a file and reading from the popen (or by setting up a fifo to do the writing with dup/dup2). Although this works, it is nice to have a lightweight version.

Anyway, this is blog more about debugging than anything. I implemented a version of Fortune's algorithm (from Computational Geometry: Algorithms and Applications) without using an AvlTree (yeah, I know it is not quite n*log(n), but it is fast enough). The implementation is rather straightforward, but I stumbled on a few oversights. First, was determining when the breakpoints on the beach line will converge, and second was the allowance of the sweep line to move in the reverse direction for circle events.

For the first problem, I ended up just computing the circumcenter of the 3 points, hypothetically moving the sweep-line to its y-coordinate and testing whether the breakpoints were close enough to each other. Detecting these events incorrectly will result in the data structure representation of the beach line becoming inconsistent. This for the most part made everything almost work.

Unfortunately, while checking for possible circle events, I was throwing away those events that should have already happened (e.g., y-coordinate greater than current sweep line). This turns out to be a no-no, as when I removed this check (after looking several other places for the source of the problem) everything worked great. Just finished running a script to check the triangulations with those returned from Octave, and the number of triangles seems to check out, so I am assuming that the results are okay--not very thorough, I know, but the ones I inspected visually seemed to be identical.

There are several algorithms that are named after people (e.g., Dijkstra), that seem like they are rather obvious and someone surely others would have come up with if. I'm not so sure Fortune's algorithm fits into this category.

Anyway, it sure looks neat to watch it in action. I almost gave up looking for the problem this evening. I wonder how many problems were really close to being solved and just needed a little more perseverance. I'm glad I wasted about 2 hours looking for these problems, even if I never end up using this code. Still some cleaning up to do.