确定简单多边形旋转时碰撞部位的扫描算法

给定平面内任意两个互不相交的简单多边形Ｐ是Ｑ。若Ｐ在平面内绕０点旋转时与ＡＱ碰撞，讨论其碰撞部位的判定问题，通过分析多边形关于０点的单调边，在平面扫描算法的榧耻提出了曲线扫描法，给这一总理２的Ｏ（（ｍ＋ｎ）ｌｏｇ（ｍ＋ｎ））算法，与现有的算法相比，降低了时间复杂性，这一方法在计算几何和计算机图形学等领域具有一定的理论和实吓价值。

PLANE-SWEEP ALGORITHM FOR FINDING THE TOUCH PARTS OF ROTATING SIMPLE POLYGONS

Let P and Q be two nonintersecting simple polygons in the plane. If P moves around a point and collides with Q , the problem of finding the touch parts of them is discussed. By analyzing the monotone edges of the polygons relative to the point, a method of curves sweep is proposed based on the plane sweep technique, and then an algorithm to solve the problem is given, which runs in time O((m n )log( m n )) in the worst case and has lower time complexity compared with the present algorithm. The method is valuable to the theory and practice in the field of computational geometry and computer graphics.