Voronoi diagram algorithm (Fortune’s sweepline)

[Captain___nemo]

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.

Please advice me very simple implementation of voronoi diagram (given
coordinates). Please advice me simple python code preferably without-
hash, multi-threading, Delaunay Traingulation, fancy colors etc (which
are confusing).

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

Thanks in advance.

 

[Bearophile]

Captain___nemo:

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

Multi-threading isn't part of Fortune's algorithm.
Multi-threading can be confusing, but it's better for you to learn to
feel at home using hash maps (named dicts in Python), because they are
both essential in computer science and in Python.
Ask if you need some help regarding dicts and sets.

Bye,
bearophile

 

[Robert Kern]

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

 

[Bearophile]

Robert Kern:

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

http://svn.scipy.org/svn/scikits/trunk/delaunay/scikits/delaunay/Voro...

That's C++; C++ makes simple things hard and hard things possible
In Python that code may become much shorter (and slower).

Bye,
bearophile

 

[Robert Kern]

Robert Kern:

That's C++; C++ makes simple things hard and hard things possible

The actual algorithm implementation is just Fortune's original C code. The C++
is mostly just wrapped around it.

In Python that code may become much shorter (and slower).

Doubtful. The algorithm would mostly be the same. The data structure doesn't
really translate to Python very well; it's very pointer-based.

Yes, I've tried.

--
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

 

[dorzey]

Found this python implementation:

http://www.oxfish.com/python/voronoi.py

From what I understand, not my area of expertise, it would seem to be
correct.

 

[dorzey]

Found this python implementation:

http://www.oxfish.com/python/voronoi.py

From what I understand, not my area of expertise, it would seem to be
correct.

 

[dorzey]

Found this python implementation:

http://www.oxfish.com/python/voronoi.py

From what I understand, not my area of expertise, it would seem to be
correct.

 

[Carl Banks]

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

You might not be able to calculate the exact points of a Voronoi
without Delaunay triangulation but you can certainly draw one without
it. For instance, this code does that:


import numpy
from PIL import Image

def voronoi(points,shape=(500,500)):
depthmap = numpy.ones(shape,numpy.float)*1e308
colormap = numpy.zeros(shape,numpy.int)

def hypot(X,Y):
return (X-x)**2 + (Y-y)**2

for i,(x,y) in enumerate(points):
paraboloid = numpy.fromfunction(hypot,shape)
colormap = numpy.where(paraboloid < depthmap,i+1,colormap)
depthmap = numpy.where(paraboloid <
depthmap,paraboloid,depthmap)

for (x,y) in points:
colormap[x-1:x+2,y-1:y+2] = 0

return colormap

def draw_map(colormap):
shape = colormap.shape

palette = numpy.array([
0x000000FF,
0xFF0000FF,
0x00FF00FF,
0xFFFF00FF,
0x0000FFFF,
0xFF00FFFF,
0x00FFFFFF,
0xFFFFFFFF,
])

colormap = numpy.transpose(colormap)
pixels = numpy.empty(colormap.shape+(4,),numpy.int8)

pixels[:,:,3] = palette[colormap] & 0xFF
pixels[:,:,2] = (palette[colormap]>>8) & 0xFF
pixels[:,:,1] = (palette[colormap]>>16) & 0xFF
pixels[:,:,0] = (palette[colormap]>>24) & 0xFF

image = Image.fromstring("RGBA",shape,pixels)
image.save('voronoi.png')

if __name__ == '__main__':
draw_map(voronoi(([100,100],[356,301],[400,65],[324,145],
[200,399])))



Carl Banks

 

[Bearophile]

dorzey:

Found this python implementation:
http://www.oxfish.com/python/voronoi.py

Looks very nice, and it may be ShedSkin-compilable too.

Bye,
bearophile