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([ 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 -- http://mail.python.org/mailman/listinfo/python-list