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

摘要

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