Day 07 - Voronoi Diagrams


Definition(s)

Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane.

Algorithm(s)


In [1]:
from PIL import Image, ImageDraw
from IPython.display import Image as PImage
import numpy as np
import math

In [14]:
def generate_voronoi_diagram(width, height, ncells, metric):
    image = Image.new("RGB", (width, height))
    imgx, imgy = image.size
    putpixel = image.putpixel
    draw = ImageDraw.Draw(image)
    
    points = []
    for i in range(ncells):
        x = np.random.randint(imgx)
        y = np.random.randint(imgy)
        r, g, b = np.random.randint(256, size=3)
        points.append((x, y, r, g, b))
        
    for xx in range(imgx):
        for yy in range(imgy):
            best, ind = float('inf'), -1
    
            for i in range(ncells):
                x, y, r, g, b = points[i]
                d = metric(x - xx, y - yy)
                
                if d < best:
                    best = d
                    ind = i
                    
            x, y, r, g, b = points[ind]            
            putpixel((xx, yy), (r, g, b))
            
    for point in points:
        x, y, r, g, b = point
        draw.ellipse((x-2, y-2, x+2, y+2), fill=(255,255,255))
    
    image.save("VoronoiDiagram.png", "PNG")

Run(s) using the Euclidean distance


In [16]:
generate_voronoi_diagram(500, 400, 30, math.hypot)
PImage("VoronoiDiagram.png")


Out[16]:

In [4]:
generate_voronoi_diagram(1000, 1000, 100, math.hypot)
PImage("VoronoiDiagram.png")


Out[4]:

In [5]:
generate_voronoi_diagram(1000, 1000, 500, math.hypot)
PImage("VoronoiDiagram.png")


Out[5]:

In [9]:
generate_voronoi_diagram(300, 300, 3, math.hypot)
PImage("VoronoiDiagram.png")


Out[9]:

In [12]:
generate_voronoi_diagram(600, 400, 10, math.hypot)
PImage("VoronoiDiagram.png")


Out[12]:

Run(s) using Manhattan distance


In [19]:
generate_voronoi_diagram(600, 400, 10, lambda x, y: abs(x) + abs(y))
PImage("VoronoiDiagram.png")


Out[19]:

In [20]:
generate_voronoi_diagram(1000, 1000, 500, lambda x, y: abs(x) + abs(y))
PImage("VoronoiDiagram.png")


Out[20]:

In [28]:
generate_voronoi_diagram(500, 500, 10, lambda x, y: abs(x) + abs(y))
PImage("VoronoiDiagram.png")


Out[28]:

Art ?


In [25]:
generate_voronoi_diagram(500, 500, 10, lambda x, y: abs(x) * abs(y))
PImage("VoronoiDiagram.png")


Out[25]:

In [29]:
generate_voronoi_diagram(700, 500, 10, lambda x, y: abs(x) * abs(y))
PImage("VoronoiDiagram.png")


Out[29]:

In [35]:
generate_voronoi_diagram(500, 500, 10, lambda x, y: abs(x) ** abs(y))
PImage("VoronoiDiagram.png")


Out[35]:

In [36]:
generate_voronoi_diagram(500, 500, 250, lambda x, y: abs(x) * abs(y))
PImage("VoronoiDiagram.png")


Out[36]:

In [37]:
generate_voronoi_diagram(500, 500, 250, lambda x, y: max(abs(x), abs(y)))
PImage("VoronoiDiagram.png")


Out[37]:

In [39]:
generate_voronoi_diagram(800, 600, 25, lambda x, y: max(abs(x), abs(y)))
PImage("VoronoiDiagram.png")


Out[39]:

In [40]:
generate_voronoi_diagram(800, 600, 25, lambda x, y: min(abs(x), abs(y)))
PImage("VoronoiDiagram.png")


Out[40]:

In [42]:
generate_voronoi_diagram(850, 600, 100, lambda x, y: min(abs(x), abs(y)))
PImage("VoronoiDiagram.png")


Out[42]: