摘要
设Ｐ＝（Ｐ＿０，Ｐ＿１，…，Ｐ＿（ｍ－１））与Ｑ（ｑ＿０，ｑ＿１，…，ｑ＿（ｎ－１））为平面内互不相交的两个凸多边形，本文研究如何快速确定它们的可碰撞区域和可移动区域的问题。本文研究了凸多边形支撑线的性质，把支撑线进行分类，据此得出一种求斜支撑线的新算法，其时间复杂度为Ｏ（ｌｏｇｍ·ｌｏｇｎ）．在此基础上构造出确定凸多边形可碰撞区域的时间复杂度为Ｏ（ｌｏｇｍ·ｌｏｇｎ）的快速算法。
Let p={P_0,P_1,…,P_(m-1)}and Q={q_0 ,q_1,…,q_(n-1)}are two nonoverlapping convex polygons,Theatithor sttidies the problem to determine their collision area and moving area fastly.In this paper,the author sttidies the properties of the supporting lines of two convex polygons and classifiesthem into four types.The author gives an algorithm for finding out the oblique supporting lines.The algorithm runs in time O(logm·logn).According to this,author can determine the collisionaiid nioving area of convex polygons in time O(logm·logn).
出处
《华南师范大学学报（自然科学版）》
CAS
1995年第4期39-48,共10页
Journal of South China Normal University(Natural Science Edition)
关键词
凸多边形
支撑线
黄金分割法
可碰撞区域
:convex polygon
stipporting line
golden break method
collision area
moving area
