摘要
本文提出一种时间复杂性为O(m+n)的算法,在一个多边形的凸包不和另一个多边形相交的条件下,该算法可确定二个多边形是否相撞,在相撞时可确定全部碰撞部位.本文还证明了确定碰撞部位问题算法的时间复杂性的下界为O(m+n),因而本文提出的算法是最佳的.
The problem of finding first contact is investigated when one polygon translates along specified direction and collides with another. If the convex hull of one polygon does not intersect with another, an algorithm is presented, with the . time complexity O(m + n), where m and n are the numbers of vertexes of the two polygons respectively. It is proved that the algorithm is optimal.
出处
《计算机学报》
EI
CSCD
北大核心
1992年第8期582-588,共7页
Chinese Journal of Computers
基金
国家自然科学基金
