15
votes

I'd really appreciate if someone who ever dealt with Fortune's algorithm for generating Delaunay-triangulations presented me a rather low-level pseudo-code of the algorithm! I read the one on wikipedia but it's a bit confusing and looks high-level, and any piece of code I could find had the original C implementation's inconveniences.

I'd like to implement it in C++, but in a way that the output generated is in the form of (my own) classes I'm going to use (vertices, edges and triangles as objects). So I need to understand everything and implement it from scratch.

I also read the description of the algorithm, and I know what it does and how, but this is still to abstract for me right now. However, I'd also be happy with a similar description going into the (implementation) details, it doesn't have to be code-like!

1
Is there a good reason for not using CGAL ? Delaunay triangulation is very very tricky to get right: the roundoff errors you are bound to encounter will ruin any implementation which doesn't use adaptive precision arithmetic. - Alexandre C.
The only reason is that I've somehow never heard about it before :) This really looks very promising, apart from the commercial licence for commercial uses, but I guess it's OK. I will play around with it a little to see if it fits my needs enough, but if no one comes up with a nice pseudocode and it's really that hard to implement, you might want to repeat this as an answer that I can mark as best! - Vincent

1 Answers

23
votes

it took me about a month to fully understand Fortune's algorithm, I wrote my seminar school work about it. When you get it, it seems very easy :)

Here is my description of Fortune's algorithm, with imperative pseudocode and implementation details.