Voronoi diagram algorithm (Fortune’s sweepline)
Robert Kern
robert.kern at gmail.com
Thu Jun 11 17:01:37 EDT 2009
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
More information about the Python-list
mailing list