python - 曼哈顿度量中的 Voronoi 图

Question

我正在使用 scipy.spatial用于 Voronoi 图的可视化。但是，这里使用的距离度量是欧几里得 (L2)。我正在我的 Voronoi 图上寻找一种曼哈顿 (L1) 度量方式。有没有一种简单(或多或少)的方法来做到这一点？

import numpy as np
import matplotlib.pyplot as plt

points = np.array([[1.5, 1.], [3.5, 1.], [5., 2.], [2.5, 3.], [3.5, 1.], [4., 4.]])
    
from scipy.spatial import Voronoi, voronoi_plot_2d
vor = Voronoi(points)

fig = plt.figure()
ax = fig.add_subplot('111')
ax.plot(points[:, 0], points[:, 1], 'o', color='k')
ax.set_xlim([-1, 9])
ax.set_ylim([-1, 9])
voronoi_plot_2d(vor, ax)

基本上我想得到类似的东西，但在 L1 指标中。

我找到了 scipy.spatial.distance.cityblock可以处理感兴趣的指标，但不完全确定如何实现它才能使其正常工作？

Answer 1

我创建了一个 github 存储库，其中包含一个名为 voronoiz 的 Python 包。包括函数 voronoi_l1 (用于计算 L1 Voronoi 图的多边形)和 voronoi_grid (用于为 scipy.spatial.cdist 支持的任何距离度量计算 Voronoi 图的图像)。
这些实现使用蛮力 O(n²) 算法，因此如果您将它与数百万个点一起使用，它可能不会很好地工作，但是对于少量到中等数量的点，您可以使用它来制作漂亮的图。
例如，一组 10 个点的 Voronoi 图的这些动画是用 voronoi_grid 制作的，其中一个点在圆圈中移动。结合write_apng来自 numpngw 图书馆:
L1 指标:

Minkowksi 度量，p=2(即标准欧几里德度量):

闵可夫斯基度量，p=4:

这是生成动画的脚本:

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 = 299

for 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] = 0
        for 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)