render Voronoi diagram to numpy array

Question

I'd like to generate Voronoi regions, based on a list of centers and an image size.

I'm tryed the next code, based on https://rosettacode.org/wiki/Voronoi_diagram

def generate_voronoi_diagram(width, height, centers_x, centers_y):
    image = Image.new("RGB", (width, height))
    putpixel = image.putpixel
    imgx, imgy = image.size
    num_cells=len(centers_x)
    nx = centers_x
    ny = centers_y
    nr,ng,nb=[],[],[]
    for i in range (num_cells):
        nr.append(randint(0, 255));ng.append(randint(0, 255));nb.append(randint(0, 255));

    for y in range(imgy):
        for x in range(imgx):
            dmin = math.hypot(imgx-1, imgy-1)
            j = -1
            for i in range(num_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("VoronoiDiagram.png", "PNG")
    image.show()

I have the desired output:

But it takes too much to generate the output.

I also tried https://stackoverflow.com/a/20678647 It is fast, but I didn't find the way to translate it to numpy array of img_width X img_height. Mostly, because I don't know how to give image size parameter to scipy Voronoi class.

Is there any faster way to have this output? No centers or polygon edges are needed

Thanks in advance

Edited 2018-12-11: Using @tel "Fast Solution"

The code execution is faster, it seems that the centers have been transformed. Probably this method is adding a margin to the image

Answer 1

Fast solution

Here's how you can convert the output of the fast solution based on scipy.spatial.Voronoi that you linked to into a Numpy array of arbitrary width and height. Given the set of regions, vertices that you get as output from the voronoi_finite_polygons_2d function in the linked code, here's a helper function that will convert that output to an array:

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.backends.backend_agg import FigureCanvasAgg as FigureCanvas

def vorarr(regions, vertices, width, height, dpi=100):
    fig = plt.Figure(figsize=(width/dpi, height/dpi), dpi=dpi)
    canvas = FigureCanvas(fig)
    ax = fig.add_axes([0,0,1,1])

    # colorize
    for region in regions:
        polygon = vertices[region]
        ax.fill(*zip(*polygon), alpha=0.4)

    ax.plot(points[:,0], points[:,1], 'ko')
    ax.set_xlim(vor.min_bound[0] - 0.1, vor.max_bound[0] + 0.1)
    ax.set_ylim(vor.min_bound[1] - 0.1, vor.max_bound[1] + 0.1)

    canvas.draw()
    return np.frombuffer(canvas.tostring_rgb(), dtype='uint8').reshape(height, width, 3)

Testing it out

Here's a complete example of vorarr in action:

from scipy.spatial import Voronoi

# get random points
np.random.seed(1234)
points = np.random.rand(15, 2)

# compute Voronoi tesselation
vor = Voronoi(points)

# voronoi_finite_polygons_2d function from https://stackoverflow.com/a/20678647/425458
regions, vertices = voronoi_finite_polygons_2d(vor)

# convert plotting data to numpy array
arr = vorarr(regions, vertices, width=1000, height=1000)

# plot the numpy array
plt.imshow(arr)

Output:

As you can see, the resulting Numpy array does indeed have a shape of (1000, 1000), as specified in the call to vorarr.

If you want to fix up your existing code

Here's how you could alter your current code to work with/return a Numpy array:

import math
import matplotlib.pyplot as plt
import numpy as np

def generate_voronoi_diagram(width, height, centers_x, centers_y):
    arr = np.zeros((width, height, 3), dtype=int)
    imgx,imgy = width, height
    num_cells=len(centers_x)

    nx = centers_x
    ny = centers_y

    randcolors = np.random.randint(0, 255, size=(num_cells, 3))

    for y in range(imgy):
        for x in range(imgx):
            dmin = math.hypot(imgx-1, imgy-1)
            j = -1
            for i in range(num_cells):
                d = math.hypot(nx[i]-x, ny[i]-y)
                if d < dmin:
                    dmin = d
                    j = i
            arr[x, y, :] = randcolors[j]

    plt.imshow(arr.transpose(1, 0, 2))
    plt.scatter(cx, cy, c='w', edgecolors='k')
    plt.show()
    return arr

Example usage:

np.random.seed(1234)

width = 500
cx = np.random.rand(15)*width

height = 300
cy = np.random.rand(15)*height

arr = generate_voronoi_diagram(width, height, cx, cy)

Example output: