一种任意多边形的裁剪算法

论文摘要

线段裁剪和多边形裁剪作为图形裁剪中最基础、最常用的操作之一,其算法始终是计算机图形学研究的热点。近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。本文首先对目前国外经典线段裁剪和多边形裁剪算法作了概述,介绍了Cohen-Sutherland裁剪算法、直线段的中点分割裁剪算法、Liang-barsky算法、Sutherland-Hodgman算法,Weiler-Atherton算法的基本思路,也描述了国内在相关领域提出的一些典型算法,如刘勇奎、蔡志杰等人在Weiler-Atherton算法基础上提出的改进算法。接着,本文对现有算法的适用性进行了比较,重点分析了Weiler-Atherton算法。在此基础上,通过对多边形按照指定顶点顺序正向和逆向遍历,查找出全部最小多边形,再通过位置判断来得出最终裁剪结果多边形的算法进行了描述。随后,以伪代码和流程图的形式,进一步说明了该算法的结构。最后,根据算法特征,显然较适用于地质构图和地图比较算法。本文以地层结果图的绘制为例,用折线和多边形裁剪的算法,推断了地层逐条裁剪构图的过程,证明了该算法在处理此类运算时,算法计算量较小,时间较快,结果正确。本文又通过对有湖心岛的湖泊面积进行对比,用两个有环多边形之间的裁剪算法,推断了不并列且互不包含的两个带环多边形的裁剪步骤,证明了该算法不但裁剪结果正确,而且每个结果多边形在裁剪前包含于哪个多边形的属性可以得到准确描述,非常利于裁剪结果的再处理,比如分层染色。从而通过以上两个工程模拟背景,验证了算法的有效性。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 课题背景
• 1.1.1 课题的目的
• 1.1.2 课题的意义
• 1.1.3 现实需求
• 1.2 国内外研究情况综述
• 1.3 本文的主要工作和研究内容
• 第二章 二维裁剪的基本原理
• 2.1 二维裁剪概念
• 2.2 常用的直线段裁剪算法
• 2.2.1 Cohen-Sutherland 裁剪算法
• 2.2.2 直线段的中点分割裁剪算法
• 2.2.3 Liang－barsky 算法
• 2.3 常用的多边形裁剪算法
• 2.3.1 Sutherland-Hodgman 逐边裁剪算法
• 2.3.2 Weiler-Atherton 双边裁剪算法
• 2.4 小结
• 第三章 任意多边形之间的裁剪算法
• 3.1 算法基本原理
• 3.1.1 不带环多边形之间的裁剪过程
• 3.1.2 带环多边形之间的裁剪过程
• 第四章 软件设计及实现
• 4.1 软件需求
• 4.2 类的描述和实现
• 4.3 设计流程图
• 4.4 伪代码实现
• 第五章 算法测试及实例
• 5.1 多边形与折线裁剪在地层结构图绘制中的应用方向
• 5.2 两个带环多边形间裁剪在湖泊面积比对中的应用方向
• 第六章 结论
• 致谢
• 参考文献