我想找出两个多边形之间的最小距离。我必须找到第一个形状的每个顶点与另一个形状的所有顶点之间最短距离的最小值。比如“AA>”，但我需要最小值而不是最大值。
最佳答案
也许你应该看看（pdf警告！还请注意，由于某些原因，图桑和巴塔查亚将页面顺序颠倒为“Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets”：
本文表明
两个有限之间的最小距离
如果[sic]n点可以是
在o（n logn）最坏情况下计算
运行时间，这是最佳的
在一个常数因子内。
此外，当集合形成
凸多边形这种复杂性可以
还原为o（n）。
如果两个多边形相交于凸多边形，也许您还应该查看（pdf警告！同样，图桑将页的顺序颠倒为“An Optimal Algorithm for Computing the Minimum Vertex Distance Between Two Crossing Convex Polygons”：
设p={p1，
p2，…，pm}和q={q1，q2，…，
qn}是指定顶点的两个相交多边形
它们的笛卡尔坐标
命令。最优o（m+n）
提出了计算算法
最小欧氏距离
p和a中的顶点pi
q中的顶点qj。