确定简单多边形旋转时碰撞部位的扫描算法

摘要：

给定平面内任意两个互不相交的简单多边形P和Q,若P在平面内绕o点旋转时与Q碰撞,讨论其碰撞部位的判定问题.通过分析多边形关于o点的单调边,在平面扫描算法的基础上提出了曲线扫描法,给出了解决这一问题的O((m+n)log(m+n))算法.与现有的算法相比,降低了时间复杂性.这一方法在计算几何和计算机图形学等领域具有一定的理论和实践价值.

关键词：简单多边形、旋转、碰撞部位、算法

所属期刊栏目：37

分类号：TP301;TP391(计算技术、计算机技术)

资助基金：财政部科研规划项目96075

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：564-569