平面内多边形沿曲线定姿态刚体移动时的碰撞判定算法研究

RESEARCH ON ALGORITHM FOR COLLISION TEST OF POLYGON IN RIGID BODY DISPLACEMENT ALONG A CURVE

研究了简单多边形Ｐ沿正则曲线σ作刚体运动时是否与平面上另一固定的简单多边形Ｑ碰撞的判断问题，给出了在最坏情况下最优时间复杂度的完备算法，并在Ｐ为凸多边形时。

Collision with a fixed simple polygon Q may occur while a simple polygon P takes a rigid body displacement along regular curve σ . An optimal algorithm in worst case for collision test is given on O(mn) time, where m and n are sizes of P and Q . When P is a convex polygon, another practical algorithm for this collision test is designed by boundary combination operation of polygons and winding number with its algebraic properties.