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

被引：10

作者：

曲吉林

机构：

[1] 山东财政学院计算机科学与工程系!济南

来源：

计算机学报 | 2000年 / 07期

关键词：

计算几何; 简单多边形; 碰撞部位; 算法;

D O I：

暂无

中图分类号：

TP391.4 [模式识别与装置];

学科分类号：

0811 ; 081101 ; 081104 ; 1405 ;

摘要：

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

引用

页码：692 / 698

页数：7

共 5 条

[1] 任意连通多边形的靠接算法 [J].