Confused with Voronoi diagram algorithm (Fortune's sweepline)

Question

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?

Milicent

Answer 1

I opened a github repository with a port of Fortune's original paper. Fortune's implementation was very tough to follow mostly due to how he handled data structures.

This book appears a lot more modern

Fortune's original paper requires a few reads.

Ken Wong's paper describes the algorithm with arguably more clarity than Fortune in the original paper

Ken Wong's presentation has great slides (10, 11) on how to process a site and a vertex

There is an interactive JavaScript demo (Archived version) you can watch to help you visualize the algorithm.

A pdf (Archived version) describes the algorithm as well.

Steven Fortune's original implementation is on his homepage.

This Stony Brook site lists more implementations

Triangle is "A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator."

There is an entire book called "Spatial Tesselations Concepts and Applications of Voronoi Diagrams" by Atsuyuki Okabe, Barry Boots et al on Voronoi diagrams

Exsanguine

Answer 2

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.

Leonelleonelle

He's trying to depict the nearest neighbor visually—overlay a Voronoi diagram on a map, so that one can see at a glance which X is closest to a point of interest. – Dijon

Voronoi diagrams are used to solve nearest neighbor problems: en.wikipedia.org/wiki/Voronoi_diagram#Applications – Agnes

The Voronoi diagram is not just a diagram. It is a planar graph (one where the edges don't cross), with vertices and bidirectional edges. – Exsanguine

Answer 3

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.

Brebner

I understand what you mean. But I have to do it by myself for evaluating. So, I was looking for some simple implementation that I can study and modify/add to my design. – Milicent

Answer 4

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.

Birl

Answer 5

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

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

Biel

It would be great if you can explain how the implementation works or would help since the original question mentions usage of Java or Python and this implementation is in Ruby. – Taddeusz

Answer 6

Obviously, the Fortune's algorithm is not trivial to implement. Especially if you consider numerical robustness issues timeline. You don't say what programming language you want to use to implement it. In case it is C++, you can find the Andriy Sydorchuk's work done for Boost in frame of GSoC 2010 project: Sweepline Algorithm. Andriy's implementation is based on Boost.Polygon library. Both, the Voronoi implementation and the Boost.Polygon rely on integer coordinates in order to provide numerical robustness.

The BoostCon video lecture on Sweep-Line Algorithm for Voronoi Diagrams of Points, Line Segments and Medial Axis of Polygons in the Plane gives a very good explanation of the idea, problems and pitfalls.

Quite a lot of discussion related to this Voronoi project. happened in Boost mailing list in 2010/2011.

Sarcomatosis