# 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]:

``````