Easiest algorithm of Voronoi diagram to implement?

Question

Hi, What are the easy algorithms to implement Voronoi diagram?

I couldn't find any algorithm specially in pseudo form. Please share some links of Voronoi diagram algorithm, tutorial etc.

Thanks in advance.

Answer 1

The Wikipedia page (http://en.wikipedia.org/wiki/Voronoi_diagram) has an Algorithms section with links to algorithms for implementing Voronoi diagrams.

Answer 2

An easy algorithm to compute the Delaunay triangulation of a point set is flipping edges. Since a Delaunay triangulation is the dual graph of a Voronoi diagram, you can construct the diagram from the triangulation in linear time.

Unfortunately, the worst case running time of the flipping approach is O(n^2). Better algorithms such as Fortune's line sweep exist, which take O(n log n) time. This is somewhat tricky to implement though. If you're lazy (as I am), I would suggest looking for an existing implementation of a Delaunay triangulation, use it, and then compute the dual graph.

In general, a good book on the topic is Computational Geometry by de Berg et al.

Answer 3

There is a freely availble voronoi implementation for 2-d graphs in C and in C++ from Stephan Fortune / Shane O'Sullivan:

VoronoiDiagramGenerator.cpp 

VoronoiDiagramGenerator.h

You'll find it at many places. I.e. at http://www.skynet.ie/~sos/masters/