Voronoi Diagram In Manhattan Metric

I am using scipy.spatial for visualizations of Voronoi diagrams. However, the distance metric that is used here is Euclidean (L2). I am looking for a way of Manhattan (L1) metric o

Solution 1:

I created a github repo containing a Python package called voronoiz that includes the functions voronoi_l1 (for computing the polygons of an L1 Voronoi diagram) and voronoi_grid (for computing an image of the Voronoi diagram for any distance metric supported by scipy.spatial.cdist).

The implementations use brute-force, O(n²) algorithms, so it probably won't work well if you use it with millions of points, but for a small to moderate number of points, you can use it to make nice plots.

For example, these animations of a Voronoi diagram for a set of 10 points, one of which moves around in a circle, are made with voronoi_grid combined with write_apng from the numpngw library:

L1 metric:

Minkowksi metric, p=2 (i.e. standard Euclidean metric):

Minkowski metric, p=4:

Here's the script that generates the animations:

import numpy as np
from voronoiz import voronoi_grid
from numpngw import write_apng


xmin = 0
xmax = 5
ymin = 0
ymax = 5

points = np.array([[0.00, 0.00],
                   [1.00, 4.51],
                   [1.20, 0.30],
                   [2.50, 2.60],
                   [2.40, 0.80],
                   [4.40, 3.30],
                   [1.95, 3.00],
                   [3.71, 1.90],
                   [4.50, 3.66],
                   [4.67, 0.21]])

gridsize = 299for kwargs in [dict(metric='cityblock'),
               dict(metric='minkowski', p=2),
               dict(metric='minkowski', p=4)]:
    imgs = []
    for theta in np.linspace(0, 2*np.pi, 250, endpoint=False):
        # points[0] will travel about a circle.
        points[0] = 2.5 + 1.5*np.array([np.cos(theta), np.sin(theta)])
        img = voronoi_grid(points, xmin, xmax, ymin, ymax,
                           gridsize=(gridsize, gridsize),
                           **kwargs)
        img = (160//(len(points)+1)*img + 64).astype(np.uint8)
        img[img == 64] = 0for x, y in points:
            i = int(gridsize*(x - xmin)/(xmax - xmin))
            j = int(gridsize*(y - ymin)/(ymax - ymin))
            img[j-1:j+2, i-1:i+2] = 255
        img = np.pad(img, pad_width=1, mode='constant', constant_values=255)
        imgs.append(img)

    tag = '_'.join(f"{key}_{value}"for key, value in kwargs.items())
    write_apng(f'animation_{tag}.png', imgs, delay=100)

Solution 2:

If visualisation and computation of areas are your only requirements you can use this pip library called mcvoronoi we did a while back. This is based on monte-carlo sampling. I added an option to change the distance metric for this answer. The updated version (with distance metric option) is not published on pip yet, but you can use the github master branch. The usage is shown below:

• Clone the repository in your current directory
• Run python example.py

The example.py consists of this basic line:

lat_lon_area, mean_percentage_error = voronoi_area(points,voronoi_plot_enabled=True, NUM_COLORS=5, metric='manhattan')

The images are saved as shown below:

You can of course make them super crisp by increasing the number of points in sampling. An error plot showing the error in area calculation is generated as well.

You might want to use more colors but if you have a sufficiently large number of regions, slightly more than 4 colors are usually enough.