Voronoi diagram algorithm (Fortune’s sweepline)
robert.kern at gmail.com
Thu Jun 11 23:01:37 CEST 2009
On 2009-06-11 14:56, Captain___nemo wrote:
> 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:
> 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.
"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
More information about the Python-list