离散点中云凸包多边形是指包含点群中所有点的最小简单多边形,简单多边形顶点也属于离散点群，大体上有凸包和凹包两种方式。其中凸包是比较常见的外包，通常将其定义为：给定n个点的坐标，求一个包含所有点的最小凸多边形，该多边形称为这个离散点群的凸包，最小凹多边形称为该离散点群的凹包。

云凸包多边形的快速生成是计算几何的基本问题之一,在计算机图形学,图象处理,设计自动化,模式识别和运筹学等领域应用较广.虽然目前已有不少算法,但人们始终在致力于寻求更好的方法.

云凸包多边形是指包含平面点集内所有点并且顶点属于平面点集的最小简单凹凸多边形. 云凸包多边形算法可分为两类,一类是需要对点集中的点按某种原则(如按x 坐标递增的原则) 进行排序, 如Graham 算法、Preparata2Hong 算法、Akl2Toussaint 算法等,这类算法的时间复杂度一般取决于排序算法;另一类算法无需排序,但其时间复杂度往往较高, 如Chand2Kapur 算法、Jarvis 算法、Bykat 算法等，具体的数学原理有以下几种：

1、Graham法：此法由Graham在1972年的提出，首先，找到所有点中最左边的（y坐标最小的），如果y坐标相同，找x坐标最小的；以这个点为基准求所有点的极atan2(y-y0,x-x0)），并按照极角对这些点排序，前述基准点在最前面，设这些点为P[0]..P[n-1]；建立一个栈，初始时P[0]、P[1]、P[2]进栈，对于P[3..n-1]的每个点，若栈顶的两个点与它不构成”向左转”的关系，则将栈顶的点出栈，直至没有点需要出栈以后将当前点进栈；所有点处理完之后栈中保存的点就是凹凸多边形了。

2、基于网络管理离散点来选取参与云凸包多边形构建的方法：首先找出给定离散点x、y方向坐标的最大值和最小值，由此可确定出离散点的最小包围盒。将包围盒沿x、y轴方向分成m、n等份，这样就形成了一个覆盖离散点的m#215;n格的方格网，然后逐一将离散点投入到这个方格网中，这时就可以以格为单位对离散点进行管理。对离散点的选取可以转换为对格的选取，由于格的数量通常比离散点的数目要少得多且查找容易，因此，对格的操作比点要容易得多。在此基础上，对该方格网逐列进行处理，只要找出每列中要参加构建云凸包多边形的格，就可达到将内点剔除的目的，从而得到云凸包多边形的顶点[10]。

3、云凸包多边形与三角网格综合生成的算法：对平面点集进行X或Y方向的筛选, 得到一个凸边界点（如Y值最小的点），记为P0，称其为云凸包多边形边界的当前”生长点”。找到所有以该点为顶点的满足优化条件的网格三角形, 定义了区域aera. 因为P0是凸包边界点, 可设aera 边界为P0Q1Q2#8943;Qn，则易知Q1，Q2两点均为点集的凸边界点（否则aera不是由所有以P0为顶点的网格三角形组成，与假设矛盾）。任选Q1为当前生长点如上处理, 又得到下一凸边界点P3。如此继续，随着网格三角形的不断生成，逐渐”生长”出云凸包边界顶点，当云凸包边界点列闭合时，即得到点集的云凸包边界[6]。

4、第一步从离散点群S中找出三个不共线的点，以这三个点构成三角形，显然此三角形是凸多边形，以其为初始凸包、以其形心作为星点O＇，连接其中亮点与星点，即可生成一个凹包；第二步以O＇为坐标原点，以分别平行于x轴及y轴的直线作为x'及y'轴，以和原坐标系相同的方向建立相对坐标系x'O'y'．按x'O'y'坐标系的象限将平面分为四个区，建立初始的凸包顶点信息表及顶点分区信息表；第三步根据Pi在x'O'y'坐标系的相对坐标来判断其所属的分区m，第四步找到两个支撑点，第五步将支撑点间的原凸包的与星点相连的两点间的线段去掉，就得到了需要的凹凸多边形]。

另一类问题是关于简单云凸包多边形的求取问题. 简单多边形云凸包多边形问题是平面点集云凸包多边形问题的特殊情况. 虽然现有许多简单多边形凸包算法均能达到线性时间复杂度,但由于任意简单多边形的顶点并不是有序地排列(如按x 坐标递增的原则排列) ,从而导致算法复杂且易于出错,如: Bykat 发现Sklansky 算法的反例;Mc2Callum和Avis 发现Shamos 算法的反例;吴中发现陈氏算法的细节错误并提出了改进的算法.散乱点集凸包算法中处于主流的排序凸包算法的许多优势源自于其对点集的预处理,即点集的排序;而简单多边形凸包算法的优势源自于多边形顶点已按某个方向(顺时针或逆时针) 串连起来的特点. 本文算法综合了这两种优点,首先用某种排序算法对散乱点集进行排序,再把排序后的点列按某种规则串连成一个简单多边形. 此时简单多边形与任意简单多边形不同,其顶点是有序排列的,如果简单套用一般的简单多边形凸包算法,则不能充分利用顶点有序排列的优势. 因此,本文利用Sklansky 算法的核心,借鉴陈氏算法的栈结构处理方式,设计了专门针对顶点有序排列简单多边形的凸包算法,以此解决了云凸包多边形的生成问题.

总之，对于离散点中云凸包多边形生成的研究有很多值得参考的成果，但同时也有更大的空间，是一个很有价值的课题。