Voronoi!

voronoi.py

#!/usr/bin/python

import math
import pygame
import random
import time


class Coord:
  def __init__(self, x=0, y=0):
    self.x = int(x)
    self.y = int(y)
    self.color = int(random.random()* (2<<32))

def distance((selfx, selfy), (otherx, othery)):
  dx, dy = (selfx - otherx) ** 2, (selfy - othery) ** 2
  real_dist = dx * (1.0 + math.sin(dx * 0.001) * 0.2) + dy * (1.0 + math.cos(dy * 0.001) * 0.2)
  return real_dist
  #return abs(self.x - other.x) + abs(self.y - other.y)
  #return math.sqrt((self.x + other.x)**2 + (self.y + other.y)**2)


pygame.init()
size = WIDTH, HEIGHT = 500, 500
scr = pygame.display.set_mode(size)

sites = []

def add_site(site):
  beg = time.time()
  array = pygame.surfarray.pixels2d(scr)
  for x in range(WIDTH):
    for y in range(HEIGHT):
      here = (x, y)
      (near_site, site_dist) = nearestsites[x][y]
      here_distance = distance(here, (site.x, site.y))
      if here_distance <= site_dist:
          nearestsites[x][y] = (site, here_distance)
          array[x][y] = site.color

    for dx in [-1, 0, 1]:
      for dy in [-1, 0, 1]:
        if dx == 0 and dy == 0:
          continue
        array[site.x+dx][site.y+dy] = 0
  del array
  pygame.display.flip()
  print "done freshening up", time.time() - beg

nearestsites = []
random.seed("frame release mind control virus")
def init_all():
    global nearestsites
    scr.fill((0x80, 0x80, 0x80))
    first_site = Coord(random.random()*WIDTH, random.random()*HEIGHT)
    nearestsites = [[(first_site, distance((first_site.x, first_site.y), (x, y))) for y in range(HEIGHT)] for x in range(WIDTH)]
    add_site(first_site)
    sites.append(first_site)

init_all()

for _ in range(2):
  site = Coord(random.random()*WIDTH, random.random()*HEIGHT)
  add_site(site)
  sites.append(site)

while 1:
  event = pygame.event.wait()
  if event.type == pygame.QUIT: break
  if event.type == pygame.KEYDOWN:
    if event.unicode == u'x':
      sites = []
      init_all()
  if event.type == pygame.MOUSEBUTTONDOWN:
      newsite = Coord(*event.pos)
      add_site(newsite)
      sites.append(newsite)
  if event.type == pygame.VIDEOEXPOSE:
    pass
  
 

Fantastic! I was looking for something just like this, and with pygame no less! Question though: can this be modified (if it doesn't already) to just return the vertices of the cells? Thanks!

This is a naive implementation of voronoi for display more than anything. You're going to need delaunay triangulation with flipping or fortunes algorithm for it to be useful data-wise