一种判定一般多边形相交的快速算法

摘要：

本文提出一种基于单调链相交测试的平面多边形碰撞算法。算法首先将多边形对象进行结构分解，确定优先进行比较的分支对，进行单调链相交测试，大大减少了边-边相交测试的运算量，从而提高多边形相交判断的速度。针对一般多边形对象，算法在最坏情形下的复杂度为(M+N)，为一个很小的正数，其中M，N为多边形P，Q的边数。

关键词： 简单多边形 单调链相交测试 有向边 包围盒 碰撞检测

作者: 周之平 张飒兵 吴介一

作者单位: 东南大学 CIMS中心,江苏南京 210096

会议类型: 国内会议

会议名称: 第二届全国几何设计与计算学术会议

会议地点: 合肥

会议语种:中文

页码: 269-273

在线出版日期: 2005-04-16（万方平台首次上网日期，不代表论文的发表时间）