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