基于顶点编码的多边形窗口线裁剪高效算法

• 作者: 彭群生 邢世海 陆国栋
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 多边形窗口 线裁剪 顶点编码 线段编码 线段求交
• 年，卷（期）: 2002,（9）
• 所属期刊栏目: 图形学专辑
• 页码范围: 987-993
• 页数: 7页
• 分类号: TP391
• 字数: 4175字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2002.09.014

摘要

从多边形窗口线裁剪的本质特征出发,首次提出窗口顶点编码的新概念.以被裁剪直线为参照系,将多边形窗口划分为正区、负区和近零区三类区域,从而快速完成多边形窗口顶点编码.通过窗口顶点编码与传统的线段编码相结合,无须求交即可快速排除大部分窗外线段;进一步可以直接得到与直线相交的窗口边,加快了求交进程.更有意义的是,通过窗口顶点编码还可以准确判断并高效处理如下两类特殊相交情况:裁剪直线通过多边形的顶点、裁剪直线通过多边形的边.实验结果表明,新算法提高了裁剪效率并具有很好的稳定性.