共 2 条
判定凸多边形可碰撞的最优算法
被引：13
作者：
李庆华
机构：
[1] 华中理工大学计算机科学与工程系武汉
来源：
关键词：
凸多边形;
可碰撞性;
四分搜索法;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
设P与Q是平面内任意二互不相交的凸多边形,d为任一给定方向,本文研究P沿d以平移方式运动可否与Q碰撞的判定问题.文中定义了凸多边形顶点集上的偏序关系,给出了判定可碰撞性的新的充分必要条件,据此采用四分搜索方法构造了判定可碰撞的算法.在最坏情况下算法的复杂度为O(logn),在不计常数因子的情况下,这是最优的.
引用
收藏
页码：589 / 596
页数：8
相关论文