作　　者： ; ; ;

机构地区： 中国科学院计算技术研究所

出　　处： 《计算机学报》 1994年第1期52-57,共6页

摘　　要： 本文讨论多边形旋转时是否发生碰撞及在发生碰撞时确定最初碰撞顶点和边的问题，给出了相应的最优判定算法与求解算法． This paper investigates the following two problems:(1)giventwo polygons A and B,point w in the plane,determine whether or not A collides with B when A rotates around w;(2)find the first collided venices and edges of A and B when A rotating around w collides with B. Two O(m+n) time algorithms are presented for problems (1)and (2)when A and B are simplepolygons,an O(max{m+logn,n+logm})time algorithm is also presented for problem(1)when A and B are convex polygons,where m and n are numbers of venices of A and B,respectively. All the algorithms presented here are optimal in the worst case.

关 键 词： 可移动性 多边形 计算机图形

领　　域： [自动化与计算机技术] [自动化与计算机技术]