我正在尝试使用R中的曼哈顿距离来计算2D中的Voronoi镶嵌。
理想情况下，这将是一个函数，它需要一组二维点并输出划分空间的多边形列表。我不确定Voronoi镶嵌的代表形式是标准的。
当然，有很多方法可以使用欧几里德度量标准（像deldir和qhull这样的软件包很容易做到这一点），但是我还没有找到针对曼哈顿距离的方法。使用sos的findFn('voronoi')进行搜索也没有结果。
最佳答案
信息：taxicabgeometry.net
互动式：Manhattan-metric Voronoi diagram(Click version)
我一直在滚动my own in python，可以在这里总结基础知识：
相邻质心之间是以曼哈顿度量单位的垂直线-如果质心是随机生成的，则最有可能产生两条射线和45度对角线，但是也可能会出现水平，垂直或45度直对角线。给定每个质心对的一组这样的线，将区域分开的边就在其中。收集每对线的相交点，以曼哈顿度量标准，它们等距（在epsilon内）与其3个最接近的质心。还要收集45度对角线的两个中点，它们的等距距离与其最近的两个质心相似。外部多边形不会关闭。如何处理它们取决于您的需求。多边形边界和边界顶点将需要排序，因此多边形不会是锯齿状的混乱。可以确定绕线顺序是顺时针方向还是其他方向。根据您的需求，可以做更多的事情。
不幸的是，涉及的点越多，速度就成倍地缓慢。每个等分线与其他等分线的相交是瓶颈。我一直在尝试一种插入方法，但取得了一些成功，但是。现在，我正在考虑首先尝试在质心之间创建最近邻居链接。如果知道邻居，则相交的平分线将是最小的，并且可以快速计算许多质心。
无论如何，蛮力方法确实有效：
光标附近的点实际上是微小对角线的2点。这是一种精确的方法，但是比最初看起来要复杂。上面的交互式链接中的Java代码可能更快，但很难从中获得可靠而精确的几何图形。
抱歉，我不认识R。