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

讨论在CAD/CAM、计算机图形学、机器人运动控制等领域都有着相当意义的图形的可移动性问题。我们研究下述典型问题,即:在平面内若多边形P沿曲线σ作定姿态刚体移动,P与障碍多边形Q相碰撞吗?在连通曲线σ关于交点判定正则,P与Q为简单多边形的情况下,本文给出-O(mn)时间的算法来判定上述典型问题中P与Q是否相碰撞。这里m与n分别为P与Q的顶点数。并且所给算法在最坏情形下是最优的。