computational-geometry - 非欧几里德距离 Voronoi 图

Question

作为一名 CG 新手，我想知道是否存在不仅仅基于站点之间的欧几里德距离而是基于其他一些度量的 Voronoi 分区，并且这种分区是否仍然保留 Voronoi 图的属性？

在阅读教科书时，我遇到过一个 Voronoi 图的示例，其中 2D 平面上的站点代表足球运动员，如果球恰好位于某个球员的 Voronoi 区域，则意味着他应该朝球走去，因为他距离球最近。现在，如果我们不仅考虑玩家之间的欧几里德距离，还考虑他们的速度，速度更快的玩家拥有更大的沃罗诺伊单元，会怎样呢？

我们失去二等分的事实会破坏 Voronoi 图本身的结构吗？

Answer 1

看看Power Diagrams和 Weighted Voronoï Diagrams 。它们是广义的 Voronoï 图，具有与每个站点关联的权重(在功率图的情况下为圆半径)。

您可以使用它来衡量每个站点的速度或改变距离的概念以包含速度。通过这样做，您将失去平分线的直线属性，因为它们可能会根据新的距离计算而变得弯曲( look here )。

就足球运动员而言，从点 p 到地点 p_i 且球员速度 v_i 的新距离函数为:

d(p, p_i) = 欧几里得距离(p, p_i)/v_i

这可以更好地解释为玩家以 v_i 速度奔跑时到达该点所需的时间。这可以生成这样的图表，其中显示的数字是权重1/v_i: