Re: Voronoi diagram algorithm (Fortune’s sweepline)

[Carl Banks]

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