论文总字数：24006字

摘 要

本文提供了一种扫描线法对平面离散点群进行外包，并用C#实现了这个算法。所谓扫描线法，在计算机图形学中是指按扫描线顺序，对逐个象素进行操作。由于本文要处理的是离散点群，所以不需要依照显示器像素逐行扫描，而只需要依照单点的坐标值逐坐标扫描。文中给出的算法就是同时进行x方向上的和y方向上的扫描，逐坐标扫描点群中的点，并运用向量叉积判断点的分区，将点群分类，再按照顺序将点连接起来，这样就可以得到平面离散点群的外包。文章最后还分析了算法的可行性及其应用前景

关键词：计算机图形学；离散点群；外包；扫描线

Building the Hull of a Set of Points

Abstract

This paper presents a vector algorithm for constructing the hull of a set of discrete points with a scan-line, and enables it in C#. net environment. Scan-line is one of regular way to reach every pixel of a graph in Computer Graphics. Here we use it to get every point in the set of discrete points. Since we’re dealing with discrete points, not pixels, we’d rather turn the scan-lines according to the coordinate of the points, than to the pixels. The algorithm in this paper uses a scan-line turned by the x-coordinate and y-coordinate of the points simultaneously, then put the points on the scan-line into cross product, in order to categorize them. Then link the categorized points in a specific order, to get the hull of the set of discrete points. At the end of the paper, the feasibility of the algorithm is discussed, and the prospect of it is also told.

Key words: Computer Graphics; Set of Discrete Points; Hull; Scan-line

目 录

摘要 II

Abstract III

第一章 绪论 2

1.1引言

1.1.1 问题的提出

1.1.2 本课题的研究手段及研究意义

1.2基本概念

第二章 基本原理 7

2.1扫描线算法

2.1.1基本概念

2.1.2具体原理

2.2 扫描线算法生成离散点群的外包多边形

2.3 单点和奇异多边形的情况以及解决方案

第三章 算法描述 11

3.1 平面离散点群输入

3.2 平面离散点群的分区

3.2.1 求最小外包矩形

3.2.2 求拐点

3.2.3 根据拐点给P中的点分区

3.3 沿x方向扫描

3.3.1 对点列进行排序

3.3.2 沿x方向扫描有序点列list3

3.3.3 取出外包顺序点列中的上部点和下部点

3.4 沿y方向扫描

3.4.1 对点列进行排序

3.4.2 沿y方向扫描有序点列list4

3.4.3 取出外包顺序点列中的左部点和右部点

3.5 平面离散点群外包多边形生成

第四章 程序实现 16

4.1 用到的变量定义

4.2 平面离散点群输入

4.2.1 通过鼠标点击输入离散点

4.2.2 通过坐标值输入离散点

4.3基本算法

4.3.1 排序算法

4.3.2 扫描算法

4.3.3 分部算法

4.3.4 连接算法

4.4平面离散点群的外包生成

4.4.1 求最小外包矩形

4.4.2 求拐点

4.4.3 将P分区

4.4.4 生成外包

4.5 程序截图

4.5.1 普通情况下平面离散点群外包多边形生成

4.5.2 特殊情况下平面离散点群外包多边形生成

第五章 应用前景 25

5.1 扫描线算法的合理性分析

5.2 应用前景

结论 28

参考文献 29

致谢 31

第一章 绪论

1.1引言

1.1.1 问题的提出

计算机图形学(Computer Graphics，简称CG)是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。

1986年，美国科学基金会（NSF）专门召开了一次研讨会，会上提出了“科学计算可视化（VISC）”。第二年，美国计算机成像专业委员会向NSF提交了“科学计算可视化的研究报告”后，VISC就迅速发展起来了。随着科学技术的迅猛发展，现实世界也变得五彩缤纷。

计算机图形学始于计算机出现后不久，1963年，伊凡·苏泽兰在麻省理工学院发表了名为《画板》的博士论文，它标志着计算机图形学的正式诞生，至今已有三十多年的历史，但是由于当时的硬件十分昂贵，而且缺乏易用和廉价的基于图形的应用程序，因此只能用计算机来表示一些简单的图形。随着计算机图形学以及计算机技术的不断发展，开发出了很多经济实用的专门的硬件系统，比如三维扫描仪硬件设备，使得获取物体表面的几何数据信息和表面纹理颜色信息更加容易，再加上计算机运算能力和存储能力的大幅度提高以及各种图形加速卡的出现，使得在个人计算机上处理离散点数据成为当今的热点研究问题之一。

计算机图形学是伴随着电子计算机及其外围设备而产生和发展起来的。它是近代计算机科学与雷达、电视及图像处理技术的发展汇合而产生的硕果。在造船、航空航天、汽车、电子、机械、土建工程、影视广告、地理信息、轻纺化工等领域中的广泛应用，推动了这门学科的内容。计算机出现不久，为了在绘图仪和阴极射线管（CRT）屏幕上输出图形，计算机图形学随之诞生了。现在它已发展为对物体的模型和图像进行生成、存取和管理的新学科。而简单多边形的构造是计算机几何学中的一个基本问题，在计算机图形学、图形图像处理、实体造型等领域有着广泛应用，如符号识别、地理信息系统、地理信息系统传感器网络等。目前，构造简单多边形的方法可分为离散点集构造法和线段集构造法。其中离散点集构造法主要包括二分排序法、坐标平移判断角法、重心方位角法、凸壳构造法和可视区法。而常见的平面多边形有简单多边形、复杂多边形及凸多边形和凹多边形等^[1]。

通过平面的点集构建外包在计算机图形学、模式识别、人工智能等领域有着广泛的应用。该课题一直是国内外学者研究的主要对象之一，虽然目前已有不少外包算法，但人们始终在致力于寻求更好的方法。确定平面点集外包通常要解决两个问题：其一，要从大量的离散点中判断哪些点是外包多边形的顶点，其二，要解决这些点的连接关系。由此产生很多各具特色的算法，综合所有凸包算法的目的是，从大量点集中快速寻找外包多边形顶点，来提高构建速度。离散点群外包多边形的生成，是计算机图形学具体应用。离散点群凸包多边形、离散点群外包多边形在地震预报和经济损失估计中具有重要意义^[2]。

请支付后下载全文，论文总字数：24006字