圆与椭圆对多边形裁剪算法研究

论文摘要

裁剪是计算机图形学中的一个重要技术。裁剪有多种类型,其中,二维多边形裁剪是目前裁剪研究的主要课题。矩形(或多边形)对多边形裁剪已有许多经典的算法。由于没有完全避免求解一元二次方程或开方运算,圆和椭圆对多边形裁剪效率较低。本文对圆和椭圆对多边形裁剪进行深入研究,设计出快速可行的算法。圆对多边形裁剪是研究的重点,做到完全避免求解一元二次方程和开方运算。应用区域编码技术将完全可见或显然完全不可见的多边形判别出来。对于既不是完全可见也不是显然完全不可见的多边形,需要用圆对多边形各边进行裁剪。主要通过区域编码技术并借助于距离平方判别法判别出圆和多边形各边的位置关系;采用中点分割算法求圆和多边形边的近似交点;通过交点和位于圆内的多边形顶点逆时针顺序的邻接关系,确定裁剪结果的直线边界;通过对交点的排序和配对,确定裁剪结果的曲线边界。圆是一种特殊的椭圆,椭圆不具有圆的所有特性。圆对多边形裁剪算法不能简单地移植到椭圆对多边形裁剪上,找出圆对多边形裁剪算法中不适合椭圆对多边形裁剪的地方,设法修改得到完全适合椭圆对多边形裁剪的有效算法。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题的来源及意义
• 1.1.1 课题的来源
• 1.1.2 课题研究的目的及意义
• 1.2 国内外裁剪研究的现状及发展趋势
• 1.2.1 点裁剪
• 1.2.2 矩形窗口的线段裁剪
• 1.2.3 多边形窗口的线段裁剪
• 1.2.4 圆和椭圆窗口的线段裁剪
• 1.2.5 矩形窗口的多边形裁剪
• 1.2.6 多边形窗口的多边形裁剪
• 1.2.7 圆和椭圆窗口的多边形裁剪
• 1.2.8 其它方面的裁剪
• 1.3 裁剪研究的分析与总结
• 1.3.1 裁剪主要的工作
• 1.3.2 二维裁剪为基础
• 1.3.3 关于线段裁剪
• 1.3.4 关于矩形、多边形对多边形的裁剪
• 1.3.5 圆对多边形裁剪算法的相关情况
• 1.3.6 椭圆对多边形裁剪算法的相关情况
• 1.4 圆或椭圆对多边形裁剪的相关技术
• 1.5 本文的组织结构
• 第2章 主要研究内容与数学基础
• 2.1 主要研究内容及拟采用的技术路线
• 2.1.1 主要研究内容
• 2.1.2 技术路线
• 2.2 数学基础
• 2.2.1 两点间的距离
• 2.2.2 直线的方程及其对平面的分割
• 2.2.3 圆的方程及图形的范围
• 2.2.4 椭圆的方程及曲线范围
• 2.3 多边形的描述
• 2.4 链表
• 2.5 本章小结
• 第3章 圆对多边形裁剪算法
• 3.1 圆与多边形的位置关系及其分类
• 3.1.1 圆与多边形的位置关系
• 3.1.2 圆与多边形位置关系的分类及其判别
• 3.2 区域编码技术
• 3.2.1 区域编码的规则及求法
• 3.2.2 区域编码的应用
• 3.3 圆对多边形边的中点分割裁剪算法
• 3.3.1 圆与边位置关系的分类及判别
• 3.3.2 距离平方判别方法
• 3.3.3 中点分割算法
• 3.3.4 圆对边的中点分割裁剪算法
• 3.4 圆对多边形裁剪的基本思想及过程
• 3.4.1 圆对多边形裁剪的基本思想
• 3.4.2 圆对多边形裁剪的方法与理论
• 3.4.3 圆心在多边形内部的判别
• 3.5 圆对多边形裁剪算法
• 3.5.1 数据结构
• 3.5.2 圆对多边形裁剪算法
• 3.5.3 算法分析
• 3.5.4 与相应算法的对比
• 3.5.5 应用前景
• 3.6 本章小结
• 第4章 椭圆对多边形裁剪算法
• 4.1 基本思想与区域编码技术
• 4.1.1 椭圆对多边形裁剪的基本思想
• 4.1.2 椭圆与多边形及边的位置关系分类
• 4.1.3 区域编码技术
• 4.1.4 距离平方判别法和中点分割算法的应用
• 4.2 椭圆对第四类边的裁剪
• 4.3 椭圆对多边形裁剪算法
• 4.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢
• 个人简介