摘要
本文讨论多边形旋转时是否发生碰撞及在发生碰撞时确定最初碰撞顶点和边的问题，给出了相应的最优判定算法与求解算法．
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.
出处
《计算机学报》
EI
CSCD
北大核心
1994年第1期52-57,共6页
Chinese Journal of Computers
关键词
可移动性
多边形
计算机图形
Computational Geometry
movability
collision
algorithm
polygon.
