如何在R中基于曼哈顿距离计算Voronoi图分割

Question

我试图在R中使用曼哈顿距离计算2D Voronoi图。

理想情况下，这将是一个函数，它接受一组二维点并输出分割空间的多边形列表。我不确定Voronoi图的哪些表示是标准的。

当然，有许多方法可以使用欧几里得度量（例如deldir和qhull包），但我没有找到用曼哈顿距离实现的方法。使用sos的findFn('voronoi')进行搜索也没有结果。

- Tom

---

要明确的是 - findFn（'voronoi'）会产生大量结果，只是似乎没有与曼哈顿距离一起使用的结果。 - Tom

Answer 1

信息：taxicabgeometry.net

交互式：曼哈顿度量的Voronoi图（点击版本）

我一直在使用Python编写我的版本，并可以在此概括基础知识： 在相邻的中心点之间是一条垂直线，在曼哈顿度量中-两条光线和一个45度对角线最有可能发生，如果中心点是随机生成的，但是也可能产生一条直的水平、垂直或45度对角线。给定一组这样的线对于每个中心点对，分隔区域的边缘就在它们之间。收集每对等距（在epsilon内），在曼哈顿度量中，离它的3个最近中心点的每一对线的交点。还要收集同样等距到最近的两个中心点的45度对角线的两个中点。外部多边形不会闭合。如何处理它们取决于您需要什么。多边形边界和边界顶点需要排序，以使您的多边形不是弯弯曲曲的混乱。绕组顺序可以确定应该顺时针或其他方向。可以做更多的事情，只取决于您的需要。

不幸的是，涉及的点越多，这个方法的速度就会指数级下降。每个双垂线与其他双垂线的相交是瓶颈。我一直在尝试插入方法，有些成功，但...现在我想尝试首先创建中心点之间的最近邻链接。如果已知邻居，则要相交的双垂线将是最小的，并且可以快速计算许多中心点。

无论如何，暴力方法确实可行：

光标��近的点实际上是一个微小对角线的2个点。这是一种精确的方法，但比起首次看来要复杂得多。上面的交互式链接中的Java代码可能更快，但很难获得坚实而准确的几何信息。

抱歉，我不懂R。

- Chronocide

---

Java代码太糟糕了 :/。有数十个无用的实例变量，奇怪的函数重新实现（如Math.abs和Math.pow），大量的庞大代码块，到处都是死代码和无用变量...如果对任何人有用的话，我在https://gist.github.com/phlummox/95dfc36f500f2fce4f7033c67d46e4fc上有一个*稍微*整洁一点的版本。编辑：哦，曼哈顿距离的方法被标记为“欧几里得距离”。天哪。 - phlummox

Answer 2

也许这个问题是关于寻找一个最大面积的正方形，它匹配在三角形的外接圆内。这样一个正方形的方程是 abs(x)+abs(y)=r (www.mathematische-basteleien.de/taxicabgeometry.htm)。当你有一个三角形网格时，沃罗诺伊图是对偶图。

- Micromega