曼哈顿度量下的沃罗诺伊图

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可以处理我们感兴趣的度量，但不确定如何实现它以使其正常工作？

- bajun65537

---

这里有一个曼哈顿 Voronoi 的 Python 实现：https://github.com/bobbysoon/TaxiVoronoi 。我没有检查它是否有效或如何运作，但或许它对你有所帮助。（我是通过这个 StackOverflow 回答找到的：https://dev59.com/Uo3da4cB1Zd3GeqPyVbz#31623208） - Alexander S. Brunmayr

是的，我没能让它工作。 - bajun65537

@bajun65537，不知道下面的解决方案是否对您有用？ - lifezbeautiful

Answer 1

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

实现使用暴力O(n²)算法，所以如果您使用数百万个点，它可能无法正常工作，但对于少量到中等数量的点，您可以使用它制作漂亮的图表。

例如，这些Voronoi图形的动画是使用voronoi_grid与numpngw库中的write_apng组合而成的，该图形显示了一组10个点的Voronoi图形，其中一个点在圆中移动：

L1度量：

Minkowksi度量，p=2（即标准欧几里德度量）：

Minkowski度量，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)

- Warren Weckesser

---

太棒了！我相信它可以运行。 - bajun65537

Answer 2

如果您只需要可视化和计算区域，可以使用我们之前做过的基于蒙特卡罗采样的 pip 库 mcvoronoi。我添加了一个选项来更改距离度量。更新版本（带有距离度量选项）尚未在 pip 上发布，但您可以使用 github 主分支。使用方法如下：

• 在当前目录中克隆 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种颜色通常就足够了。

- lifezbeautiful