我想找到两个多边形之间的最小距离 . 我必须找到第一个形状的每个顶点与另一个顶点的所有顶点之间的最小最短距离 . 类似于Hausdorff Distance，但我需要最小值而不是最大值 .
也许你应该看看（PDF警告！还要注意，由于某种原因，页面的顺序是相反的）“Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets”由Toussaint和Bhattacharya：
本文显示，如果[sic] n点可以在O（n log n）最坏情况运行时间内计算两个有限平面集之间的最小距离，并且这是在常数因子内的最佳值 . 此外，当这些组形成凸多边形时，这种复杂性可以降低到O（n） .
如果两个多边形正在交叉凸起，也许你也应该检查出来（PDF警告！再次，页面的顺序颠倒了）“An Optimal Algorithm for Computing the Minimum Vertex Distance Between Two Crossing Convex Polygons”作者：Toussaint：
设P = {p1，p2，...，pm}和Q = {q1，q2，...，qn}是两个相交的多边形，其顶点按顺序由笛卡尔坐标指定 . 提出了一种最优O（m n）算法，用于计算P中的顶点pi与Q中的顶点qj之间的最小欧氏距离 .
1 回答
也许你应该看看（PDF警告！还要注意，由于某种原因，页面的顺序是相反的）“Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets”由Toussaint和Bhattacharya：
如果两个多边形正在交叉凸起，也许你也应该检查出来（PDF警告！再次，页面的顺序颠倒了）“An Optimal Algorithm for Computing the Minimum Vertex Distance Between Two Crossing Convex Polygons”作者：Toussaint：