Thursday, September 13, 2012

Simple python script - Voronoi diagram

Today I show you how to make Voronoi diagram using python.

I use this to make textures for underwater.

This is just one example. But you can improve to control all cells of voronoi diagram.

The theory say:

In mathematics, a Voronoi diagram is a special kind of decomposition of a metric space, determined by distances to a specified family of objects (subsets) in the space. These objects are usually called the sites or the generators...Source : wikipedia.

I used the euclidean distance to make the Voronoi diagram because it's the most familiar case.

About wikipedia - Euclidean_distance: In mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula...

My python script use the next python modules:

PIL - this allow me to use image functions.

random - this module give me... random numbers.

math - some math functions.

Let's see the source code :

from PIL import Image
import random
import math

Now I make the function named gen_voronoi.

This take the height and width of the output image and the number of cells.

The function has some random variables for red , green , blue - nr,ng,nb.

The function hypot is not accessible directly so we need to import math module and using math static object.

The return value is the Euclidean norm : sqrt(x*x + y*y).

def gen_voronoi(w, h, cells):
 image ="RGB", (w, h))
 putpixel = image.putpixel
 img_x, img_y = image.size
 nx = []
 ny = []
 nr = []
 ng = []
 nb = []
 for i in range(cells):
 for y in range(img_y):
  for x in range(img_x):
   dmin = math.hypot(img_x-1, img_y-1)
   j = -1
   for i in range(cells):
    d = math.hypot(nx[i]-x, ny[i]-y)
    if d < dmin:
     dmin = d
     j = i
   putpixel((x, y), (nr[j], ng[j], nb[j]))"output.png", "PNG")

Use the function to make the output.png image.

gen_voronoi(200, 200, 55)

The result is :