我想找到具有百万个顶点的两个多边形之间的最小距离（而不是它们顶点之间的最小距离）。我必须找到第一个形状的每个顶点与另一个形状的所有顶点之间的最短距离的最小值。类似于Hausdorff Distance，但我需要最小值而不是最大值。
问问题
19375 次
2 回答
24
也许您应该查看（PDF 警告！另请注意，由于某种原因，页面的顺序是颠倒的）“计算两个有限平面集之间最小距离的最佳算法”，作者 Toussaint 和 Bhattacharya：
本文表明，如果 [ sic ] n 点可以在 O( n log n ) 最坏情况运行时间内计算，则两个有限平面集之间的最小距离在一个常数因子内是最优的。此外，当这些集合形成一个凸多边形时，这种复杂性可以降低到 O( n )。
如果这两个多边形与凸多边形相交，也许您还应该查看（PDF 警告！再次，页面顺序颠倒）“计算两个交叉凸多边形之间最小顶点距离的最佳算法”，作者 Toussaint：
令P = { p 1 , p 2 ,..., p m } 和 Q = { q 1 , q 2 ,..., q n } 是两个相交的多边形，其顶点由它们的笛卡尔坐标按顺序指定。提出了一种最优O( m + n )算法来计算P中的顶点p i和Q中的顶点q j之间的最小欧式距离。
于 2010-09-13T15:29:04.290 回答
0
有一个使用 Minkowski 加法的简单算法，它允许计算两个凸多边形的最小距离并在 O(n + m) 中运行。
链接：
algoWiki、boost.org、neerc.ifmo.ru（俄语）。
如果两个凸多边形的 Minkowski 减法覆盖 (0, 0)，则它们相交
于 2021-07-04T16:06:31.813 回答