曼哈顿度量中的 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

如果区域的可视化和计算是您唯一的要求，您可以使用这个名为 mcvoronoi 的 pip 库，我们之前做过。这是基于蒙特卡洛抽样。我添加了一个选项来更改此答案的距离度量。更新版本（带有距离度量选项）尚未在 pip 上发布，但您可以使用 github master 分支。用法如下图：

克隆当前目录中的 repository
运行 python example.py

example.py 由以下基本行组成：

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

图片保存如下图：

你当然可以通过增加采样点的数量来让它们变得超级脆。还会生成显示面积计算误差的误差图。

您可能想要使用更多颜色，但如果您有足够多的区域，通常略多于 4 colors 就足够了。

Answer 2

我创建了一个 github 存储库，其中包含一个名为 voronoiz 的 Python 包，其中包含函数 voronoi_l1（用于计算 L1 Voronoi 图的多边形）和 voronoi_grid（用于计算 scipy.spatial.cdist 支持的任何距离度量的 Voronoi 图图像）。

这些实现使用蛮力，O(n²) 算法，因此如果您将它用于数百万个点，它可能不会很好地工作，但对于少量到中等数量的点，您可以使用它来制作漂亮的情节。

例如，一组 10 个点的 Voronoi 图的这些动画是用 voronoi_grid 结合 write_apng 来自 [=19] =]图书馆：

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)

曼哈顿度量中的 Voronoi 图

Voronoi diagram in Manhattan metric

python

voronoi

scipy