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

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

给定平面内任意两个互不相交的简单多边形 P和 Q,若 P在平面内绕 o点旋转时与 Q碰撞 ,讨论其碰撞部位的判定问题 .通过分析多边形关于 o点的单调边 ,在平面扫描算法的基础上提出了曲线扫描法 ,给出了解决这一问题的 O((m+n) log(m+n) )算法 .与现有的算法相比 ,降低了时间复杂性 .这一方法在计算几何和计算机图形学等领域具有一定的理论和实践价值 .

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.