计算机图形学(简单多边形裁剪算法)

简单多边形裁剪算法摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前裁剪研究的主要课题。本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。通

简单多边形裁剪算法 摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目 前裁剪研究的主要课题。本文主要介绍了一种基于多边形顶点遍历的简单多边形裁 剪算法，它有效降低了任意多边形裁剪复杂度。通过记录交点及其前驱、后继信 息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算 法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。 关键词：多边形裁剪；交点；前驱；后继；矢量数组 一、技术主题的基本原理 简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于 多边形顶点遍历来实现简单多边形裁剪工作的。其主要的原理是遍历多边形并把多 边形分解为边界的线段逐段进行裁剪，输出结果多边形。 二、发展研究现状 近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪 算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外 相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用 性提出了越来越高的要求。因此,不断简化算法的实现过程,完善细节处理,满足大 量任意多边形的裁剪也就成了当今算法研究的焦点之一。 以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点 的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。为了解 决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形 都可以是一般多边形，且不需要规定多边形输入方向。它采用矢量数组结构，只需 遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效 率高的特点。