确定凸多边形可碰撞区域的快速算法

被引：10

作者：

李庆华

机构：

[1] 华中理工大学计算机科学与工程系武汉

来源：

中国科学(A辑数学物理学天文学技术科学) | 1992年 / 07期

关键词：

凸多边形; 可碰撞性; 斜支撑线; 可碰撞区域; 可移动区域;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

设P=(p0,p1,…,pn-1)与Q=(q0,q1,…,qn-1)是任二互不相交的凸多边形,本文研究了如何快速确定它们的可碰撞区域和可移动区域的问题. 文中提出了可碰撞性判定的新方法,研究了斜支撑线的基本性质,利用这些性质构造出了求斜支撑线的快速算法,其时间复杂度为O(log2（n+m）),在此基础上给出了确定可碰撞区域和可移动区域的时间复杂度为O(log2（n+m）)的快速算法.

引用

页码：753 / 762

页数：10