Looking for Pseudo-code for Fortune's algorithm

algorithm pseudocode
Vincent picture Vincent · Jan 19, 2011 · Viewed 9.5k times · Source

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!

Answer

Ivan picture Ivan · Sep 4, 2011

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.

Related questions

Algorithm to calculate the number of divisors of a given number

What would be the most optimal algorithm (performance-wise) to calculate the number of divisors of a given number? It'll be great if you could provide pseudocode or a link to some example. EDIT: All the answers have been very helpful, …

Read More
Quicksort: Choosing the pivot

When implementing Quicksort, one of the things you have to do is to choose a pivot. But when I look at pseudocode like the one below, it is not clear how I should choose the pivot. First element of list? …

Read More
Find the paths between two given nodes?

Say I have nodes connected in the below fashion, how do I arrive at the number of paths that exist between given points, and path details? 1,2 //node 1 and 2 are connected 2,3 2,5 4,2 5,11 11,12 6,7 5,6 3,6 6,8 8,10 8,9 Find the paths from 1 to 7: Answer: 2 paths found and they …

Read More