analitics

Pages

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 = Image.new("RGB", (w, h))
 putpixel = image.putpixel
 img_x, img_y = image.size
 nx = []
 ny = []
 nr = []
 ng = []
 nb = []
 for i in range(cells):
  nx.append(random.randrange(img_x))
  ny.append(random.randrange(img_y))
  nr.append(random.randrange(256))
  ng.append(random.randrange(256))
  nb.append(random.randrange(256))
 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]))
 image.save("output.png", "PNG")
 image.show()

Use the function to make the output.png image.


gen_voronoi(200, 200, 55)

The result is :