平面上简单多边形平移时确定碰撞部位的最优算法

被引：25

作者：

汪嘉业

机构：

[1] 浙江大学CAD＆CG重点实验室杭州山东大学计算机科学系,济南

来源：

关键词：

多边形; 碰撞部位; 时间复杂性;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

本文提出一种时间复杂性为O(m+n)的算法,在一个多边形的凸包不和另一个多边形相交的条件下,该算法可确定二个多边形是否相撞,在相撞时可确定全部碰撞部位.本文还证明了确定碰撞部位问题算法的时间复杂性的下界为O(m+n),因而本文提出的算法是最佳的.

引用

页码：582 / 588

页数：7