Pou*_*BCD 16 algorithm geometry distance computational-geometry
我想找到两个多边形之间的最小距离.我必须找到第一个形状的每个顶点与另一个顶点的所有顶点之间的最小最短距离.类似于Hausdorff距离,但我需要最小值而不是最大值.
Yas*_*man 22
也许你应该看看(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(米 + Ñ)算法,用于计算顶点之间的最小欧氏距离p 我在P和一个顶点q Ĵ在Q.