求解两个简单多边形碰撞距离的最优算法

摘要

提出了求解两个简单多边形在一方向矢量下的碰撞距离的最优算法。对于ｍ边形Ｐ和ｎ边形Ｑ，算法的时间复杂度为Ｏ（Ω（Ｐ）｜ｎ＋｜Ω（Ｑ）｜ｍ），其中｜Ω（Ｑ）｜分别表示多边形Ｐ和Ｑ中凸顶点的个数。