曼哈顿度量的 Voronoi 图

Question

我正在使用scipy.spatialVoronoi 图的可视化。然而，这里使用的距离度量是欧几里德（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 存储库，其中包含一个名为的 Python 包voronoiz，其中包含函数voronoi_l1（用于计算 L1 Voronoi 图的多边形）和voronoi_grid（用于计算支持的任何距离度量的 Voronoi 图的图像scipy.spatial.cdist）。

\n

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

\n

例如，这些由 10 个点组成的 Voronoi 图的动画，其中一个绕圈移动，是结合voronoi_grid库write_apng中的制作的numpngw：

\n

L1 指标：

\n

\n

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

\n

\n

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

\n

\n

这是生成动画的脚本：

\n

import numpy as np\nfrom voronoiz import voronoi_grid\nfrom numpngw import write_apng\n\n\nxmin = 0\nxmax = 5\nymin = 0\nymax = 5\n\npoints = np.array([[0.00, 0.00],\n                   [1.00, 4.51],\n                   [1.20, 0.30],\n                   [2.50, 2.60],\n                   [2.40, 0.80],\n                   [4.40, 3.30],\n                   [1.95, 3.00],\n                   [3.71, 1.90],\n                   [4.50, 3.66],\n                   [4.67, 0.21]])\n\ngridsize = 299\n\nfor kwargs in [dict(metric=\'cityblock\'),\n               dict(metric=\'minkowski\', p=2),\n               dict(metric=\'minkowski\', p=4)]:\n    imgs = []\n    for theta in np.linspace(0, 2*np.pi, 250, endpoint=False):\n        # points[0] will travel about a circle.\n        points[0] = 2.5 + 1.5*np.array([np.cos(theta), np.sin(theta)])\n        img = voronoi_grid(points, xmin, xmax, ymin, ymax,\n                           gridsize=(gridsize, gridsize),\n                           **kwargs)\n        img = (160//(len(points)+1)*img + 64).astype(np.uint8)\n        img[img == 64] = 0\n        for x, y in points:\n            i = int(gridsize*(x - xmin)/(xmax - xmin))\n            j = int(gridsize*(y - ymin)/(ymax - ymin))\n            img[j-1:j+2, i-1:i+2] = 255\n        img = np.pad(img, pad_width=1, mode=\'constant\', constant_values=255)\n        imgs.append(img)\n\n    tag = \'_\'.join(f"{key}_{value}" for key, value in kwargs.items())\n    write_apng(f\'animation_{tag}.png\', imgs, delay=100)\n

\n