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

摘要：

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

关键词：多边形窗口、线裁剪、顶点编码、线段编码、线段求交

所属期刊栏目：25

分类号：TP391(计算技术、计算机技术)

资助基金：国家杰出青年科学基金69925204;国家自然科学基金60021201

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：987-993