文献类型：期刊文章

作　　者：刘勇奎[1] 高云[2] 黄有群[2]

机构地区：[1]大连民族学院计算机科学与工程系,辽宁大连116600 [2]沈阳工业大学信息科学与工程学院,辽宁沈阳110023

出　　处：《软件学报》

基　　金：国家民委科技基金;辽宁省科技基金~~

年　　份：2003

卷　　号：14

期　　号：4

起止页码：845-856

语　　种：中文

收录情况：AJ、BDHX、BDHX2000、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、ZMATH、核心刊

摘　　要：多边形裁剪与线剪裁相比具有更广泛的实用意义,因此它是目前裁剪研究的主要课题.提出了一个多边形裁剪多边形的有效算法.其中的多边形都可以是一般多边形,既可以是凹多边形,也可以是有内孔的多边形.该算法不仅可以求多边形的交(多边形裁剪),而且可以求多边形的并和差.它是以所提出的一系列新方法和新技术为基础而形成的.首先,该算法使用单线性链表数据结构,与其他使用双链表或树结构的算法相比,具有 占用空间少及处理速度快的特点;其次,找到了两个多边形之间进、出点之间的关系.再通过合理的数据结构处理,减少了算法对多边形链表的遍历次数,而且允许多边形既可以按顺时针方向也可以按逆时针方向输入.最后,判断和计算交点是裁剪算法的主要工作.提出了一个具有最少计算量的交点判断和计算方法,进一步加快了算法的运行速度.与其他同类算法进行了比较,结果表明,新算法具有最简单的结构和最快的执行速度.

关 键 词：多边形裁剪算法 计算机图形学 凹多边形 数据结构 图形处理  

分 类 号：TP391.41]