下载文档原格式
求解简单多边形和平面点集凸包的新算法
刘光惠;陈传波
【期刊名称】《计算机科学》
【年(卷),期】2007(34)12
【摘要】沿一定方向遍历凸多边形的边,其内部在边的同一侧.本文依据凸多边形的这一特性,提出求解简单多边形凸包的新算法,进而扩展得到求解平面点集凸包的新
算法.新点集凸包算法先找到点集的极值点,得到极值点间的候选点子集,再求得相邻极值点间的有序凸包点列,最后顺序连接极值点间的有序凸包点列,得到凸包.新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O(n log h),其中,n为平
面点集的点数,h为平面点集凸包的顶点数.相比相同复杂度的凸包算法,新算法简单、易于实现.又由于是顺序求得凸包上的点,新算法还具有更易于实现基于其上的有效
空间算法的优点.
【总页数】5页(P222-226)
【作者】刘光惠;陈传波
【作者单位】华中科技大学计算机学院,武汉,430074;华中科技大学计算机学院,武汉,430074
【正文语种】中文
【中图分类】TP3
【相关文献】
1.一种平面点集的高效凸包算法 [J], 刘凯;夏苗;杨晓梅
2.基于凸包求解的简单多边形方向判断新算法 [J], 吕福起;赵丹
3.基于凸包求解的简单多边形方向判断新算法 [J], 吕福起;赵丹
4.基于有序简单多边形的平面点集凸包快速求取算法 [J], 金文华;何涛;刘晓平;唐卫清;唐荣锡
5.基于有序点列的平面点集凸包的新算法 [J], 陈平;汪国昭
因版权原因，仅展示原文概要，查看原文内容请购买。
matlab里的convhull算法中括号（[ ]）在MATLAB中有许多用途，其中之一是用于表示矩阵、向量和行向量。
在本文中，我们将探讨MATLAB中的convhull算法，该算法可用于计算给定点集的凸包。
我们将逐步回答以下问题：1. 什么是convhull算法？Convhull算法是一种用于计算平面上给定点集的凸包的常用算法。
凸包是包含点集的最小凸多边形或凸壳。
Convhull算法的目标是找到一组最小的边界点，这些点可以用来构建凸包。
2. 如何使用MATLAB的convhull函数？在MATLAB中，我们可以使用convhull函数来计算给定点集的凸包。
该函数的语法如下：K = convhull(X,Y)或K = convhull(X,Y,Z)其中，X、Y和Z是包含点集的向量，K是构成凸包的点的索引。
如果只提供X和Y向量，那么将计算平面上的凸包。
如果提供X、Y和Z向量，那么将计算三维空间中的凸包。
3. 如何可视化凸包？我们可以使用plot函数来可视化凸包。
以下是一个简单的例子：X = [0 1 1 0];Y = [0 0 1 1];K = convhull(X,Y);plot(X(K), Y(K))在此示例中，我们定义了一个平面上的四个点，并计算了它们的凸包。
然后，我们使用plot函数绘制了凸包的边界线段。
4. 如何计算包含多个点集的凸包？在MATLAB中，我们可以使用convhulln函数来计算包含多个点集的凸包。
该函数的语法如下：K = convhulln(X)其中，X是一个包含多个点集的矩阵，每个点集占据矩阵的一行。
K是一个包含凸包边界点的索引的矩阵。
5. 如何通过凸包计算点集的面积？凸包可以用来计算点集的面积。
在MATLAB中，我们可以使用convhull函数得到凸包的边界点的索引，然后使用polyarea函数计算多边形的面积。
以下是一个示例：X = [0 1 1 0];Y = [0 0 1 1];K = convhull(X,Y);area = polyarea(X(K),Y(K))在此示例中，我们计算了平面上四个点的凸包，并使用polyarea函数计算了凸包的面积。
＊)国家863项目(2004AA420100)。
刘光惠 博士研究生,主要研究方向为计算机图形学、图像处理和算法优化;陈传波 博士生导师,主要研究方向为计算机图形学、图像处理、模式识别与计算机网络及应用技术。
计算机科学2007V ol .34№.12 求解简单多边形和平面点集凸包的新算法＊)刘光惠 陈传波(华中科技大学计算机学院 武汉430074)摘 要 沿一定方向遍历凸多边形的边,其内部在边的同一侧。
本文依据凸多边形的这一特性,提出求解简单多边形凸包的新算法,进而扩展得到求解平面点集凸包的新算法。
新点集凸包算法先找到点集的极值点,得到极值点间的候选点子集,再求得相邻极值点间的有序凸包点列,最后顺序连接极值点间的有序凸包点列,得到凸包。
新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O (n log h ),其中,n 为平面点集的点数,h 为平面点集凸包的顶点数。
相比相同复杂度的凸包算法,新算法简单、易于实现。
又由于是顺序求得凸包上的点,新算法还具有更易于实现基于其上的有效空间算法的优点。
关键词 计算几何,凸包,极值点,有序凸包点列,有效空间 New Algorithms for C omputing the Convex Hulls of a Simple Polygon and a Planar Point SetLI U G uang -Hui CH EN Chuan -Bo(H uazhong University of S cience and Techn ology ,Wu han 430074)A bstract Based o n o ne of the cha racteristics of co nv ex po ly go ns ,i .e .when the edges o f a co nve x po lyg o n a re trav -e rsed along one direction ,the inte rio r of the convex polyg on is alway s o n the same side of the se edg es ,a new alg orithm for co mputing the convex hull of a simple polyg on is pro po sed first ,w hich is then ex tended to a new algo rithm for com -puting the convex hull o f a plana r point set .T o compute the co nv ex hull of a planar po int se t ,fir st to find the ex treme points of the planar po int se t and ge t the sub co llec tions o f points candidate for v ertices of the co nv ex hull betweenthem .T hen the sor ted convex hull point arr ay s betw een ex treme po ints a re co nst ruc ted separa tely and concatena ted by remov ing redundant ex treme po ints to ge t the convex hull .T he time comple xity of the new plana r co nv ex hull alg o -rithm is O (nlo gh ),w hich is equal to the time co mplexity o f best output -sensitive planar convex hull algo rithms .Com -pared w ith the same time complexity algo rithms ,the new alg o rithm is simple and ea sy to be impleme nted ,and o wing to its seque ntially computing the ver tices on the co nv ex hull ,it is easier to g et a space -efficient planar convex hull alg o -rithm based on the new planar convex hull algo rithm than o ther s .Keywords Computational geomet ry ,Co nv ex hull ,Ex treme points ,So r ted convex hull point ar ray ,Space -efficient 1 引言凸包问题是计算几何的一个基本问题,凸包算法在计算机图形学、图像处理、设计自动化、模式识别等领域应用较广[1]。
初识平面点集与凸包在计算几何学中，平面点集和凸包是两个重要的概念。
平面点集是指在平面上的一个点的集合，而凸包是指包含该平面点集所有点的最小凸多边形。
本文将介绍平面点集和凸包的定义、性质以及相关算法。
一、平面点集的定义和性质平面点集是指在平面上的一个点的集合。
假设平面点集为S，S中的点可以用二维平面上的坐标表示，例如S={(x1, y1), (x2, y2), ...}。
平面点集有一些重要的性质：1. 包含关系：平面点集可以包含其他的点集。
例如，如果T是一个平面点集，且T的所有点都包含在S中，则称T为S的子集。
2. 联接线段：平面点集中的两个点可以通过一条线段连接。
例如，如果S包含点A和点B，则可以通过线段AB将这两个点连接起来。
3. 凸性：平面点集中的任意两点之间的线段都完全包含在该点集内部。
即平面点集中的任意三个点A、B、C满足AB和BC的直线段上的所有点也都在S内部，那么S是一个凸点集。
二、凸包的定义和性质凸包是指包含平面点集中所有点的最小凸多边形。
凸包具有以下重要的性质：1. 唯一性：给定一个平面点集S，它的凸包是唯一的，不受点的排序或排列顺序的影响。
2. 极点：凸包上的顶点称为极点，极点是凸包边界上的点。
3. 凸包边界：凸包的边界由连接凸包上各个极点的线段组成。
4. 凸包面积：凸包的面积是凸包边界上所有三角形面积的总和，它也可以用来判断凸包的大小。
三、计算凸包的算法计算凸包的算法有多种，其中比较常用的是Graham扫描算法和Jarvis步进算法。
这里简要介绍这两种算法：1. Graham扫描算法：该算法的基本思想是先找到平面点集中的一个最低点作为参考点，然后按照相对于参考点的极角进行排序。
从排序后的点集中取出前两个点作为凸包的起始边，然后按照逆时针方向逐个添加点，如果添加点导致凸包内部有凹陷，则将凸包内的点逐个删除，最后得到凸包。
2. Jarvis步进算法：该算法的基本思想是先找到平面点集中的一个最左点作为参考点，然后从该点出发，按照逆时针方向依次选取下一个点，直到回到起始点形成封闭的凸包。
求平面点集凸壳算法
李旭朝
【摘要】在分析传统平面点集凸壳算法的基础上,给出了一种新的平面点集凸壳算法,对算法步骤进行了详细说明,并对此算法可行性进行了验证,最后对算法时间复杂度进行了分析探讨,得到了很好的效果.
【期刊名称】《兰州工业学院学报》
【年(卷),期】2011(018)002
【总页数】3页(P16-18)
【关键词】极值点;夹角;子集;凸壳算法
【作者】李旭朝
【作者单位】兰州交通大学数理与软件工程学院,甘肃730070
【正文语种】中文
【中图分类】TP301.6
0 引言
凸壳即最小凸包，是包含集合D中全部对象的最小凸集，平面点集的凸壳是计算几何学中较重要、较基础的问题.在计算几何学中凸壳自身据有很多特点，也是构造其它较复杂几何形体的工具，也是基本单元.平面点集凸壳作为一种基本的结构不但在计算几何学中有很重要的作用，而且在分析GIS数据等问题时有很重要的作用，在空间分析等诸多问题中也多次用到平面点集的凸壳算法.
包含D中所有点的最小凸多边形即平面点集D的凸壳，其所有顶点均为D中的点.凸壳算法可以将许多问题归纳起来处理和解决，它在计算机图形学中有较为广泛的应用，也在一些实际技术如图像处理、模式识别等中应用较多.
传统求平面点集凸壳的算法较多，主要有卷包裹法、格雷厄姆算法、分治算法、求增量算法、实时算法等.由于在计算几何学中凸壳问题有着基础作用和重要地位，
大家都在不断的研究较快的平面点集凸壳算法.
通过对传统的平面点集凸壳算法的分析,本文给出了一种新的平面点集凸壳算法.经
实验验证求平面海量散乱点集的凸壳应用此算法效果非常好.许多实际应用问题都
可以总结为平面点集的凸壳问题来解决，如地理信息系统中的区域裁剪等实际问题. 该算法的时间复杂度是O(nlogn)，无法突破最坏情况下的理论下限，但此算法也
可以向三维或者高维空间进行拓展.
1 平面点集凸壳描述及相关定义
定义1 设多边形P的顶点是给定平面内的点p1(x1，y1)，p2(x2，y2)，… pn(xn，yn)，若线段pipj(i≠j，1≤i≤n，1≤j≤n)在多边形P内或者在多边形P上，则称P
为凸多边形.
定义2 设平面点集S={pi(xi，yi)|1≤i≤n}由平面上的点构成.若凸多边形Q的所有
顶点Qi∈S，并且Q是可以覆盖S中所有点的最小凸多边形，则称凸多边形Q为平面点集的凸壳.
定义3 求给定平面点集S={pi(xi，yi)|1≤i≤n}的平面凸壳的方法和过程称为平面点集凸壳算法.
定义4 凡能生成给定平面点集S={pi(xi，yi)|1≤i≤n, n≥3}的平面凸壳的算法，均
称为平面点集凸壳生成算法.
定义5 平面点集S={pi(xi，yi)|1≤i≤n，
n≥3}中各点的位置分布区域，称为S分布域.
定义6 平面点集S={pi(xi，yi)|1≤i≤n，
n≥3}中Xmax，Ymax，Xmin，Ymin对应的点叫做平面点集S的极值点.
2 平面点集的凸壳生成算法
此算法是研究平面散乱点集最小凸壳的算法，首先找出平面散乱点中的四个极值点(即Xmax,Ymax,Xmin,Ymin)用这四个极值点将平面点集划分为四个相对的子集，其次在这四个子集的范围内从每一个极值点分别查找与基准线的夹角，求出使该夹角最大的点，循环查找，不断的缩小求集区间，直至四个子集都查找完毕，然后顺次连接所查找出的点得到的凸多边形即为平面点集的凸壳，这种求平面点集凸壳的算法即为凸壳算法.
若存在由m个点组成的平面点集P={pi(xi，yi)|1≤i≤m}，采用该凸壳算法求平面点集凸壳的算法步骤如下：
Input：m个点所组成的平面点集P={pi(xi，yi)|1≤i≤m}；
Output：平面点集S的凸壳P；
step1：求点集S中的点的个数m，如果m≤3 则P=S，即S中的平面点全部为凸壳点.否则，step2；
step2：找出平面点集的所有极值点，即Xmax，Ymax，Xmin，Ymin所对应的点，则这四个极值点肯定是平面凸壳上的点.对Xmax对应的点均按Y轴的升序进行排序，求出其中Y最大的点和最小的点，如果二者相等，则取其一，另一个则舍去；对Xmin对应的点采用相同的办法.对Ymax对应的点均按X轴的升序进行排序，求出其中X最大的点和最小的点，如果二者相等，则取其一，另一个则舍去.对Ymin对应的点采用相同的办法.将这四个结果保存到数组Q中.
step3：分别在所有对应的点中取一个点，记录为Pxmin，Pymax，Pxmin，Pymin，将平面点集划分为四个子区间1，2，3，4.同时定义子区间1中的点
A={αi(xi，yi)| Xmin≤xi≤Pymax.x，Pxmin .y≤yi≤Ymax}；子区间2中的点
C={ci(xi，yi)|Pymax .x<xi<Xmax，Pxmax.y<yi<Ymax}；子区间3中的点
M={mi(xi，yi)|Xmin<xi<Pymin .x，Ymin<yi<Pxmin .y}；子区间4中的点
N={ni(xi，yi)|Pymin.y≤xi≤Xmax，Ymin≤yi≤Pxmax .y}.
step4：删除子区间1中PxminPymax右边的点，记录Pxmin.在剩余的点中求每个点与Pxmin的连线，并找出其与X轴夹角最大的点，这个点将作为新的凸壳点记录.删除新的凸壳点和Pymax连线右边的点，在剩余的点中求每个点与新的凸壳点的连线，并找出其与X轴夹角最大的点，这个点将作为新的凸壳点记录.迭代查找直至子区间1查找完毕.
step5：在子区间2、3、4中分别进行step4，直至这四个子区间全部查找完毕. step6：顺次连接P中的点即生成平面点集的凸壳.
3 算法思想可行性验证
本文所述的思想和求平面点集凸壳的过程和步骤在Visual C++ 6.0编程环境下经过多次求证是可行的，部分程序源代码如下：
//差错函数，查找是否有错误的凸点
function checkerror,points
n=size(points)
istrue=1
for i=0,n[2]-3 do begin
if
mutiply
(points[0,i],points[1,i],points[0,i+1],points[1,i+1],points[0,i+2],points[1,i+2]) It 0 then begin
istrue=0 ;有凹点
break
endfor
return,istrue
end
//对排序后的点集先进行判断，是否有凹点，如果有则修改，否则不进行处理
if check eq 1 then bgin
m=1
while (m) do begin
if checkerror(points eq 0 then begin
points=modify(points)
endif else begin
break
endelse
endif else begin
points=modify(points)
endelse
图1所示为其运行效果.
图1 算法运行效果
4 算法的时间复杂度讨论
平面点集中包括n个平面散乱点，在step2中查找Xmax，Ymax，Xmin，Ymin 这四个极值点所对应的点的过程，时间复杂度应为O(n)，从step4到step6是对子区间1、2、3、4分别求平面点集凸壳，因为其它很多无关的点在每次求出一个凸壳上的点后都将被删除，所以其消耗的时间主要是在判断点与直线的位置关系上，因此该算法的时间复杂度是O(nlogn).
本文所提出的平面点集的凸壳算法，对一些计算效率要求较高并且对计算精度要求较低的情况或者海量数据的情形下特别适合.对一些有固定计算精度的情况，我们可以先对各个方向的相关参数进行计算，将现成的方向列表先存储到算法中，这样加快了计算近似凸壳的过程。
所有快速求平面点集凸壳算法当中，都先要迅速得到一个初始凸壳，因此越精确的初始凸壳，后续的过程中对点集进行全面扫描将有较多的内点被删除，这样整个算法的效率将得到提高.所以作为快速凸壳算法的第一步，此算法通过对精度控制参数n的合适选择，计算近似凸壳的计算效率将得到进一步的提高.
参考文献：
[1] 周启海，黄涛，吴红玉，张元新.基于最大基线倾角智能逼近的凸壳新算法[J].计算机科学, 2007,34(9):206-208.
[2] 周培德.计算几何: 算法分析与设计[M].北京：清华大学出版社，2005.
[3] 江健.寻找平面上点的凸壳[J].重庆工学院学报，2007,21(17):15-17.
[4] 柳忠校，陈辉.一种新的求平面点凸壳算法[J].计算机与信息技术,2009(9):52-53.
[5] 樊广佺,马丽平,杨炳儒.平面点集凸壳的一种快速算法[J].地理与地理信息科
学,2006,22(6):38-41.
[6] 樊广佺,王小牛,杨炳儒.平面点集凸壳的一种近似算法[J].计算机工程与应
用,2007,43(12):40-41,76.
[7] 樊广佺.平面点集凸壳的快速近似算法[J].系统工程与电子技术,2008,30(4):649-651.
[8] 沈映政.居民地自动综合技术研究与软件开发[D].昆明：昆明理工大学，2008.。
