Confused with Voronoi diagram algorithm (Fortune's sweepline)

Question

Hi, I am implementing Voronoi diagram to find out the nearest location in a map visually. Right now I want to do this using integer coordinates (x,y) only in a canvas.

Problem is- I am really confused about this algorithm. I read the Computational Geometry book, few more theory on Fortune's algorithm. And I am really confused now. It seems very complex to me when I am going for coding.

Please advice me very simple implementation of voronoi diagram (with given coordinates). Please advice me simple java or python or scheme code preferably without- hash, multi-threading, Delaunay Traingulation, fancy colors etc.

Isn't it possible to implement Voronoi diagram using Fortune's algorithm without multithreading or hash map?

Thanks in advance.

Answer 1

The Voronoi diagram is just a diagram: not a data structure or algorithm. I don't think it's suited to finding the nearest point in a set. Constructing the diagram would not change the asymptotic complexity of your problem, although it would make your problem more complicated and less memory efficient. You would be better off putting your points in a quadtree or something similar. If you're looking for algorithms, the name of the problem you're trying to solve is "spatial indexing". "Nearest point" is one of the problems solved by quadtrees and other spatial indexes.

Answer 2

It seems complicated because it is complicated! You don't need a hashtable or threads, but you will need a priority queue (usually implemented as a heap, and available in both the java and python standard libraries) and a tree which lets you do range queries in O(log n) (the ones in the standard libraries aren't really suitable because you can't get at their internals; i'd suggest implementing an AA tree). And the algorithm itself is still pretty hairy.

Can you run an external program? If so, i really suggest you leave the heavy lifting to QHull, which is very good at Voronoi diagrams. Much better than either of us will ever be, sadly.

Answer 3

I was looking at Voronoi diagrams quite a bit last year and I can certainly appreciate the confusion. There are a few implementations of Voronoi diagram generating algorithms around. See this page for a couple, and also here. As twic mentioned, Qhull is certainly worth looking at - MATLAB uses it to generate Voronoi diagrams and Delaunay triangulations and fun things like that.

Answer 4

Here is another implementation in Ruby and C, including visualization:

http://github.com/abscondment/rubyvor/