Voronoi diagram algorithm (Fortune’s sweepline)

[Robert Kern]

On 2009-06-11 14:56, Captain___nemo wrote:
> 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.

Yup. It is complex.

> Please advice me very simple implementation of voronoi diagram (given
> coordinates). Please advice me simple python code preferably without-
> hash, multi-threading, Delaunay Traingulation,

You can't really do the Voronoi diagram without Delaunay Triangulation. They are 
two ways of looking at the same thing.

> fancy colors etc (which
> are confusing).

You can see a mild modification of Fortune's original C code here:

http://svn.scipy.org/svn/scikits/trunk/delaunay/scikits/delaunay/VoronoiDiagramGenerator.cpp

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

It's possible to do it without multithreading, of course, but Fortune's 
algorithm does require some sophisticated data structures. Computational 
geometry is rarely a simple matter.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco