# Re: Voronoi diagram algorithm (Fortune’s sweepline)

Carl Banks pavlovevidence at gmail.com
Thu Jun 11 18:28:30 EDT 2009

```On Jun 11, 2:01 pm, Robert Kern <robert.k... at gmail.com> wrote:
> On 2009-06-11 14:56, Captain___nemo wrote:
> > Please advice me very simple implementation of voronoi diagram (given
> > 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

```