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

关键词: CAD/CAM, 计算机图形学, 算法, 可移动性, 碰撞

中图分类号: 

• TP391.7