一种判定简单多边形与凸多边形可移动性的算法  

An Algorithm for Deciding Movable Directions of a Polygon and a Convex Polygon

作　　者：杜玉越[1] 

机构地区：[1]聊城师范学院计算中心,山东聊城252059

出　　处：《计算机工程》1995年第S1期130-133,共4页Computer Engineering

摘　　要：设简单多边形P=(P_0,P_1,…,P_(n-1)的凸包和凸多边形Q=(q_0,q_1,…q_(m-1)互不相交。研究了P相对于Q的可移动性问题,提出了一种在最坏情况下时间复杂性为O(n+m)的算法,它在不计常数因子的情况下是最优的。Let the convex hull of a polygon P = (P0, P,1 …, Pn-1)and a convex polygon Q=(q0, q1, … qm-1)be disjoint in a plane, this paper studies the problem of deciding all movable directions when P moves and doesn't collide against Q(or Q moves and doesn't collide against P).An algorithm is described with the time-complexity O(n+m) in the worst case, and it is optimal without ragard for constant factors.

关 键 词：多边形 凸多边形 可移动性 时间复杂性 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]