r - 如何根据R中的曼哈顿距离计算Voronoi镶嵌

Question

我正在尝试使用 在 2D 中计算 Voronoi 分割。曼哈顿 距离在 R .

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

当然，有很多方法可以使用欧几里得度量来做到这一点(像 deldir 和 qhull 这样的包使这很容易)，但我还没有找到一种方法来为曼哈顿距离做到这一点。使用 sos 进行搜索的 findFn('voronoi')也没有结果。

Answer 1

信息:taxicabgeometry.net

互动:Manhattan-metric Voronoi diagram(Click version)

我一直在滚动my own in python ，并可以在这里总结基础知识:
相邻质心之间是一条垂直线，以曼哈顿公制表示 - 如果质心是随机生成的，则最有可能是两条射线和 45 度对角线，但也可能出现水平、垂直或 45 度对角线。给定每个质心对的一组这样的线，分隔区域的边就在其中。收集每对线的交点，这些交点以曼哈顿公制为单位等距(在一个 epsilon 内)到它的 3 个最近的质心。还收集 45 度对角线的两个中点，它们与它们最近的两个质心等距。外层不会关闭。如何处理它们取决于您的需求。多边形边框和边框顶点需要排序，所以你的多边形不是锯齿状的困惑。绕线顺序可以确定是顺时针还是其他。可以做更多的事情，这取决于您需要什么。

不幸的是，涉及的点越多，速度就会呈指数级增长。每个平分线与所有其他平分线的相交是瓶颈。我一直在尝试一种插入方法，取得了一些成功，但是 .现在我想首先尝试在质心之间创建最近邻链接。如果邻居是已知的，相交的平分线将是最小的，并且可以快速计算出许多质心。

无论如何，蛮力方法确实有效:


光标附近的点实际上是一条小对角线的 2 个点。这是一种精确的方法，但比最初看起来更复杂。上面交互式链接中的 java 代码可能会更快，但很难从中获得实体和精确的几何图形。

抱歉，我不知道 R。