我想找到两个多边形之间的最小距离。我的意思是，我必须找到最小的第一形状的每个顶点之间的最短距离与其他一体的全方位的顶点。像豪斯多夫距离，但我需要的最低，而不是最大的。我AP preciate任何建议。谢谢你。

I wanna find the minimum distance between two polygon. I mean, I have to find the minimum of shortest distance between each vertex of first shape with the all the vertexes of the other one. Something like Hausdorff Distance but I need minimum instead of maximum. I appreciate any suggestion. Thank you.

推荐答案

也许你应该检查（ PDF警告！还要注意的是，由于某些原因，这些页面的顺序颠倒的） 优化算法计算两有限平面的最小距离由杜桑和巴特查亚集

Perhaps you should check out (PDF warning! Also note that, for some reason, the order of the pages is reversed) "Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets" by Toussaint and Bhattacharya:

有示于本文的   两个有限之间的最小距离   平面设置，如果[原文的] n个点即可   计算在O（ N 的日志的 N 的）最坏情况   运行时间并认为这是最佳的   内恒定的因素。   此外，当套形成一   凸多边形这种复杂性可   降低到O（ N 的）。

It is shown in this paper that the minimum distance between two finite planar sets if [sic] n points can be computed in O(n log n) worst-case running time and that this is optimal to within a constant factor. Furthermore, when the sets form a convex polygon this complexity can be reduced to O(n).

如果两个多边形穿越凸的，也许你应该还检查了（ PDF警告再次，页面的顺序颠倒的！）的