如何计算基于曼哈顿距离的Voronoi tesselation

Question

我正在尝试用2D中的曼哈顿距离计算Voronoi tesselation R.

理想情况下,这将是一个函数,它采用一组二维点并输出一个分隔空间的多边形列表.我不确定Voronoi tesselations的标志是什么.

当然也有很多方法可以做到这与欧几里德度量(包像deldir和qhull使这很容易),但我还没有找到一种方法,为曼哈顿距离做到这一点.使用sos's 的搜索findFn('voronoi')也没有产生任何结果.

Answer 1

信息：taxicabgeometry.net

互动：曼哈顿度量Voronoi图（点击版本）

我一直在 python 中滚动自己，并且可以在这里总结基础知识：相邻质心之间是一条垂直线，以曼哈顿公制表示 - 如果质心是随机生成的，则最有可能是两条射线和 45 度对角线，但一条直线也可能出现水平、垂直或 45 度对角线。给定每个质心对一组这样的线，分隔区域的边就在其中。收集每对直线到其 3 个最近的质心等距离（在 epsilon 内）的交点（以曼哈顿度量单位）。还收集 45 度对角线的两个中点，它们与最近的两个质心的距离同样相等。外部政策不会关闭。如何处理它们取决于您的需要。多边形边界和边界顶点需要排序，这样您的多边形就不会是锯齿形的混乱。可以确定缠绕顺序是顺时针还是其他。可以做更多的事情，仅取决于您需要什么。

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

无论如何，暴力方法确实有效：

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

抱歉，我不认识R。