判定凸多边形可碰撞的最优算法

OPTIMAL ALGORITHM FOR DECIDING POSSIBLE COLLISION OF CONVEX POLYGONS

设P与Q是平面内任意二互不相交的凸多边形,d为任一给定方向,本文研究P沿d以平移方式运动可否与Q碰撞的判定问题.文中定义了凸多边形顶点集上的偏序关系,给出了判定可碰撞性的新的充分必要条件,据此采用四分搜索方法构造了判定可碰撞的算法.在最坏情况下算法的复杂度为O(logn),在不计常数因子的情况下,这是最优的.

Let P and Q be two arbitrary disjoint convex polygons, and d an arbitrary direction in plane. This paper studies the problem of deciding whether P collides against Q when P moves parallelly in the direction of d. A partial ordering on the set of convex polygon vertexes is defined, and a new sufficient and necessary condition for deciding possible collision is given, and on these grounds the algorithm for deciding possible collision is constructed by the quartered search In the worst case the time-complexity of the algorithm is O(logn), and it is optimal without regard for constant factors.