确定凸多边形平移时最初碰撞部位的最优算法  

AN OPTIMAL ALGORITHM OF DETERMINING THE TOUCH PARTS BETWEEN TWO COLLIDING CONVEX POLYGONS

作　　者：覃中平[1] 张焕国[2] 

机构地区：[1]华中理工大学数学系,武汉430074 [2]武汉大学计算机科学系,武汉430072

出　　处：《计算机学报》1992年第3期171-177,共7页Chinese Journal of Computers

摘　　要：本文提出在图形学,机器人学,VLSI设计与CAD/CAM等众多领域中具有广泛应用的下述基本问题:设P与Q为平面内分别具有m与n个顶点的凸多边形,若P沿给定方向d移动将与Q相碰撞,如何根据P与Q的顶点坐标事先确定P与Q相碰撞时两者上的最初碰撞的顶点和边.利用折半搜索技术,本文给出了求解此基本问题的时间复杂度为O(logm+logn)的算法并证明这一算法在时间上是最优的.Let P and Q be two disjoint convex polygons in a plane. An algorithm is described that determines the touch parrs of P and Q when P translates along a specified direction and collides with Q in O(logm + logn) time, where m and n denote the number of vertices of P and Q, respectively. This is optimal in the worst case.

关 键 词：图形学 算法 多边形 碰撞部位 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]