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

r - 如何计算基于曼哈顿距离的Voronoi tesselation,第1张

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

理想情况这是一个函数,它接受一组二维点并输出一个分区空间的多边形列表。我不确定Voronoi tesselations的标志是什么。

使用欧几里德指标当然有很多方法可以做到这一点(deldirqhull这样的包很容易),但我还没有找到办法做到这一点曼哈顿距离。使用sos' findFn('voronoi')的搜索也没有产生任何结果。

最佳答案:

2 个答案:

答案 0 :(得分:3)

信息:taxicabgeometry.net

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

我一直在滚动my own in python,可以总结一下这里的基础知识: 在相邻质心之间是垂直线,以曼哈顿度量 - 如果质心是随机生成的话,最可能是两条光线和45度对角线,但也可能出现直线水平,垂直或45度对角线。给定每个质心对的一组这样的线,分隔区域的边缘就在它们之中。将曼哈顿度量中等距离(在epsilon内)的每对线的交叉点收集到它最近的3个质心。同时收集45度对角线的两个中点,它们与最近的两个质心相等。外部政策不会被关闭。如何处理它们取决于你需要什么。 poly边界和边界顶点将需要排序,因此你的政治不是一个锯齿状的混乱。绕组顺序可以确定顺时针或其他顺序。可以做的更多,只取决于你需要的东西。

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

无论如何,蛮力方法确实有效: r - 如何计算基于曼哈顿距离的Voronoi tesselation,enter image description here,第2张

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

对不起,我不知道R。

答案 1 :(得分:0)

也许问题是找到一个正方形(三角形)外围的正方形的最大面积。这种方形abs(x) abs(y)= r的等式(www.mathematische-basteleien.de/taxicabgeometry.htm)。当你有一个三角形网格时,voronoi图是双重的。

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复