Re: Voronoi diagram algorithm (Fortune’s sweepline )
dorzey: Found this python implementation: http://www.oxfish.com/python/voronoi.py Looks very nice, and it may be ShedSkin-compilable too. Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list
Voronoi diagram algorithm (Fortune’s sweepline)
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Voronoi diagram algorithm (Fortune’s sweepline )
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Voronoi diagram algorithm (Fortune’s sweepline )
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Voronoi diagram algorithm (Fortune’s sweepline )
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Voronoi diagram algorithm (Fortune’s sweepline )
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Voronoi diagram algorithm (Fortune’s sweepline )
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Voronoi diagram algorithm (Fortune’s sweepline )
On Jun 11, 2:01 pm, Robert Kern robert.k...@gmail.com wrote:
On 2009-06-11 14:56, Captain___nemo wrote:
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.
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([
0x00FF,
0xFFFF,
0x00FF00FF,
0x00FF,
0x,
0xFF00,
0x00FF,
0x,
])
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
--
http://mail.python.org/mailman/listinfo/python-list
