确定任意简单多边形平移时碰撞部位的扫描算法

Plane-Sweep Algorithm for Determining the Colliding Parts of Simple Polygons

设 P和 Q为平面内任意两个互不相交的简单多边形 ,若 P沿方向 d平移时与 Q碰撞 ,采用平面扫描法 ,通过提取多边形的单调链 ,给出了求其碰撞部位的算法 .最坏情况下 ,算法的时间复杂性为 O((m +n) log(m+n) ) ,其中 n和 m分别为多边形 P与 Q的边数 ,与现有的算法相比 ,降低了时间复杂性 .

Let P and Q be two nonintersecting simple polygons in the plane,if P translates in indirection d and collides with Q , the touch parts of them can be found by using the plane sweep technique. The plane sweep algorithm in this paper runs in time O((m+n) log (m+n) ) in worst presented case,where n and m are the edge number of polygons P and Q .