如何找到具有特定距离函数的Voronoi图？

Question

用欧氏距离求Voronoi图有很多算法。然而，我还没有找到任何其他距离函数的算法，例如曼哈顿距离(可能是因为没有实际应用)。

你可以在维基百科上看到这样的例子：

Diagram.svg

曼哈顿Voronoi图也由多边形(但不是凸的)组成，所以我想可以构造类似于“财富”算法的算法。然而，使用更复杂的距离函数，边界将不再是多边形。需要不同的数据结构和算法。

是否有任何算法可以找到具有特定距离函数的Voronoi图(为了简单起见，在2D中)？

注意：--我不需要与像素一起工作的算法，它非常简单，我需要算法，它创建单元格的边界。

注2实际上我需要带距离函数abs(dx)^3 + abs(dy)^3的Voronoi图，但理论上，我感兴趣的是如何为其他距离函数建立一个算法。这是Voronoi和abs(dx)^3 + abs(dy)^3的样子。站点是连续的，它们的边类似于y=x^3图(只是假设)。

​

​

Answer 1

最有可能的是，您可以使用像素出租车voronoi，并给每个多边形不同的颜色。然后，可以使用像素颜色测试来检查边界。