确定任意简单多边形平移时碰撞部位的扫描算法

• 作者: 曲吉林
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 计算几何 简单多边形 碰撞部位 算法
• 年，卷（期）: 2000,（7）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 692-698
• 页数: 7页
• 分类号: TP391
• 字数: 6846字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2000.07.004

摘要

设P和Q为平面内任意两个互不相交的简单多边形,若P沿方向d平移时与Q碰撞,采用平面扫描法,通过提取多边形的单调链,给出了求其碰撞部位的算法.最坏情况下,算法的时间复杂性为O((m+n)log(m+n)),其中n和m分别为多边形P与Q的边数,与现有的算法相比,降低了时间复杂性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曲吉林	山东财政学院计算机科学与工程系	20	253	8.0	15.0