平面线段相交问题的渐缩规整包围盒过滤规则

• 作者: 肖子枫 贺劲 韩冀中 韩承德
• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: 线段相交 平面扫描 包围盒 渐缩规整包围盒 过滤规则
• 年，卷（期）: 2008,（10）
• 所属期刊栏目: 图形算法与技术
• 页码范围: 1345-1352
• 页数: 8页
• 分类号: TP391
• 字数: 5627字
• 语种: 中文

摘要

平面线段相交是计算几何的基本问题之一,通常采用基于包围盒过滤规则的平面扫描方法求解.但这些过滤规则没有利用算法执行过程中线段有效部分逐渐缩短的性质,导致候选集和冗余计算增加.通过量化包围盒的主对角线斜率,并使量化后的包围盒逐渐缩小,提出更加严格的渐缩规整包围盒过滤规则.实验数据表明,相比于包围盒过滤规则,文中提出过滤规则的候选集和计算量平均分别减少16%和14%.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	韩承德	中国科学院计算技术研究所系统结构部	53	704	14.0	24.0
2	肖子枫	中国科学院计算技术研究所系统结构部	3	13	2.0	3.0
6	韩冀中	中国科学院计算技术研究所系统结构部	24	166	6.0	12.0
7	贺劲	中国科学院计算技术研究所系统结构部	6	44	3.0	6.0