平面点集凸壳的快速算法_赵军

格式：pdf
大小：238.17 KB
文档页数：3

下载文档原格式

平面点集凸壳的快速算法

平面点集凸壳的快速算法
赵军;曲仕茹
【期刊名称】《计算机工程与应用》
【年(卷),期】2009(045)001
【摘要】提出一种计算平面点集凸壳的快速算法.利用极值点划分出四个矩形,它们包含了所有凸壳顶点,通过对矩形中的点进行扫描,排除明显不是凸壳顶点的点,剩余的点构成一个简单多边形.再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳.整个算法简洁明了,避免了乘法运算(除最坏情况外),从而节省计算时间.
【总页数】3页(P56-58)
【作者】赵军;曲仕茹
【作者单位】兰州交通大学,数理与软件工程学院,兰州,730070;西北工业大学,自动化学院,西安,710072
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.一种平面点集凸壳的快速算法 [J], 陈学工;黄石峰;李源;曹建
2.海量平面点集凸壳的快速算法 [J], 樊广佺;张桂云;杨炳儒
3.基于二维凸壳的平面点集Delaunay三角网算法 [J], 毕硕本;陈东祺;颜坚;郭忆
4.平面点集凸壳的快速近似算法 [J], 樊广俭;马丽平;杨炳儒
5.平面点集凸壳的一种快速算法 [J], 樊广佺;马丽平;杨炳儒
因版权原因，仅展示原文概要，查看原文内容请购买。

GIS中散乱点集凸包的快速算法及编程_李军辉

[收稿日期] 2009-06-16[作者简介] 李军辉(1981)),男,山东潍坊人,南京市东南大学学生,硕士研究生,主要研究方向为地图制图学与地理信息工程。

GIS 中散乱点集凸包的快速算法及编程李军辉1,李紫阳2(1.东南大学交通学院,南京 210096; 2.沈阳军区某部司令部,沈阳 110000)[摘要] 在地理信息系统(GIS)中,不规则三角网(TI N)的生成及数字地面模型(D TM)的建立都会用到点集凸包的计算。

通过研究了传统凸包算法,并对其进行改进,提出简单快速的点集凸包改进算法。

经过验证,新算法可准确快速地求出点集凸包。

[关键词] GIS;凸包;算法;编程[中图分类号] P 208 [文献标识码] A [文章编号] 1005-0310(2009)03-0032-03A Quick Algorithm and Programm ing to Determ ine Convex Hullfor Planar Scattered Point Set in GISLI Jun -hui 1,LI Z-i yang2(1.Transportation College,Southeast Uni versity,Nanjing 210096,China;2.Shenyang Mili tary Region Command,Shenyang 110000,China)Abstract :In GIS,the convex hull algorithms of a point set are always applied in the generation of TI N and the building of DTM.The paper discusses the traditional convex hull algorithms and puts forward a faster algorithm.It has been proved that the ne w algorithm can acquire conve x hull quickly and accurately.Key words :GI S;convex hull;algorithm;programming 在地理信息系统(Geograghic Information System,GIS)应用中,原始数据经常是一些离散数据,比如雨量分布数据等,由于数据的采集、传输和录入的顺序不同,一般是一些散乱的数据记录,称其为散乱点集[1]。

一种平面点集凸包与三角网格综合生成的算法

一种平面点集凸包与三角网格综合生成的算法
孔德慧;马春玲
【期刊名称】《计算机研究与发展》
【年(卷),期】2000(037)007
【摘要】平面点集作为一种常见数学模型,其上常做的运算是求其凸包和三角网格.目前二者的研究是独立进行的.鉴于在很多情形下这两种处理结果均需要,提出了一
种综合算法:在对离散点集进行delaunay剖分的过程中,增加对三角形边界的判别、管理功能,记录其中作为点集凸包边界的线段,使得在实现剖分的同时产生出点集的
凸包,从而提高了算法效率.且当该算法实现单一的点集剖分或凸包功能或是用于简
单多边形的凸包与剖分时效果也很好.
【总页数】6页(P891-896)
【作者】孔德慧;马春玲
【作者单位】北京工业大学计算机学院,北京,100022;北京工业大学计算机学院,北京,100022
【正文语种】中文
【中图分类】TP391.72
【相关文献】
1.一种平面点集的高效凸包算法 [J], 刘凯;夏苗;杨晓梅
2.一种平面点集的高效凸包算法 [J], 刘凯;夏苗;杨晓梅
3.计算平面点集凸包的实时插入算法 [J], 刘萍
4.一种高效的平面点集凸包递归算法 [J], 刘斌;王涛
5.环状分布平面点集的凸包快速生成算法 [J], 陈明;张丰;杜震洪;刘仁义
因版权原因，仅展示原文概要，查看原文内容请购买。

求平面点集凸壳算法

如图像处理、式识别等中应用较多．模传统求平面点集凸壳的算法较多，主要有卷包裹法、雷厄姆算法、治算法、增量算法、格分求实
时算法等．由于在计算几何学中凸壳问题有着基
础作用和重要地位，家都在不断的研究较快的大平面点集凸壳算法．通过对传统的平面点集凸壳算法的分析，本文给出了一种新的平面点集凸壳算法．实验验经证求平面海量散乱点集的凸壳应用此算法效果非
求平面点集凸壳算法
李旭朝
（兰州交通大学数理与软件工程学院，甘肃７０７）３００
摘要：分析传统平面点集凸壳算法的基础上，出了一种新的平面点集凸壳算法，在给对算法步骤进
行了详细说明，并对此算法可行性进行了验证，最后对算法时间复杂度进行了分析探讨，到了很得
面点集凸壳生成算法．
第２期
李旭朝：求平面点集凸壳算法
・ｌ７・
定义５平面点集Ｓ＝｛，Ｉ ≤ｉＺＰ（Ｙ） ≤／１，
Ｐ．Ｙ＜Ｙ｝子区间３中的点Ｍ＝｛，Ｙ＜ｍ；ｍ（
Ｙ）Ｘｉ＜ｉＹｉ＜Ｙ＜Ｐ．｝子区间４ｌ＜Ｐ．ｍ，Ｙ；
ｎ｝ ≥３中
，
，ｉｉ应的点叫做平面点ｍ，对
集．的极值点．ｓ
２平面点集的凸壳生成算法

一种平面点集凸壳的快速算法

能使得计算凸壳的时间复杂度为０ｎｇ）（ｌｎ。由于计算ｏ平面上ｎ个点的凸壳的时间复杂度的下界为Ｑ
（ｌｎ，ｎｇ）这种凸壳技术可以称为最优凸壳技术。本文ｏ
１基本概念
定义１对一个给定的平面点集Ｓ，包含ＳＰＰ的最小凸多边形称为Ｊ的凸壳。ｓＪｐ本文规定这个凸多边形
ｓｒｅｎｓａｎｅ，ｃｎｔｃｅｉｉａｃｎｅｕｌｈｎａｄｔｅｒｓｏｈｉｒｔｏｎｏｔｅｃｎｅｕｌｗｈｃｏｔｄｉｃｎｍａｎｒｏｓｕｔｔｎｔｌｏｖｘｈｌｒｈｉ，ｔｅｄｈｅｔｆｔｅｄｓｅｅｐｉｔｔｈｏｖｘｈｌｃｓｉｈ
的算法基本思想是：首先对所有Ｊ中的点按照扫描线ｓＪｐ方式排序为Ｐ然后｛，，），ｐＰ …ｐ。。：生成第一个凸壳（凸
ｈｓｂｅｃｅｔｄａｄｇｎｒｔｗｏｎｘｕ１ａｅｎｒａｅｎｅｅａｅａｎｅｃｖｅｈｌ．Ｅｘｒｍｅｔｈｐｅｉｎｓｏｗｈｔｔｌｏｒｔｍａｇｏｄｅｉｉｎｃ．ｓｔａｈｅａｇｉｈｈａｏｆｃｅｙｓＫｅｒ：ｃｎｘｈｕｌｃｐａｉａｅｙｗｏｄｓｏｖｅｌ；ｏｍｕｔｔｏｎｌｏｍｅｒ；ｕｉｋｓｒｇｔｙｇｃｏｔ
维普资讯
第１第３期６卷
２００８年６月
电
脑
与
信
息
技
术

初识平面点集与凸包

初识平面点集与凸包在计算几何学中，平面点集和凸包是两个重要的概念。

平面点集是指在平面上的一个点的集合，而凸包是指包含该平面点集所有点的最小凸多边形。

本文将介绍平面点集和凸包的定义、性质以及相关算法。

一、平面点集的定义和性质平面点集是指在平面上的一个点的集合。

假设平面点集为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步进算法：该算法的基本思想是先找到平面点集中的一个最左点作为参考点，然后从该点出发，按照逆时针方向依次选取下一个点，直到回到起始点形成封闭的凸包。

平面散乱点集凸包算法

平面散乱点集凸包算法详解摘要：本文旨在详细介绍一种用于计算平面上散乱点集的凸包的算法。

凸包算法是计算几何中的一个重要问题，它在图形学、机器学习、图像处理等领域有着广泛的应用。

本文档将详细阐述凸包的概念、性质以及几种常用的凸包算法，包括Graham 扫描法和Chan算法，并对每种算法的时间复杂度进行分析。

1. 引言在计算几何中，凸包问题是研究如何找到一组点的最小凸多边形，该多边形包含了所有的点。

这个问题在很多领域都有应用，比如在机器人学中的碰撞检测、计算机图形学中的渲染优化、以及数据分析中的数据可视化等。

2. 凸包的定义与性质凸包是指包含所有给定点集的最小凸多边形。

凸包具有以下性质：- 凸包是唯一的。

- 凸包的边界上的点（极点）按顺序连接可以构成一个凸多边形。

- 任何不在凸包边界上的点都位于由边界点构成的某个三角形内部。

3. 凸包算法概述有多种算法可以计算凸包，包括Graham扫描法、Chan算法、Andrew算法等。

这些算法各有特点，但大多数都是基于分治策略或贪心策略。

4. Graham扫描法Graham扫描法是一种效率较高的凸包算法，其基本思想是从最低的点开始，按照每个点相对于基准点的极角进行排序，然后依次检查每个点是否会使当前的凸包发生变化。

步骤如下：a. 找到所有点中y坐标最小的点P，如果这样的点有多个，则取x坐标最小的一个。

b. 将其他点按照与P点的极角排序。

c. 从排序后的点集中依次取出点，检查是否会影响当前的凸包。

d. 重复步骤c，直到所有点都被检查过。

5. Chan算法Chan算法是对Graham扫描法的一种改进，它通过减少不必要的比较来提高效率。

Chan算法使用了一个堆栈来存储可能会成为凸包顶点的点。

步骤如下：a. 将所有点按照x坐标排序。

b. 从左到右扫描排序后的点集，使用堆栈来记录可能的凸包顶点。

c. 当扫描到一个新的点时，更新堆栈顶部的点，确保堆栈顶部的点是当前扫描线左侧最远的点。

求平面点集凸壳算法

求平面点集凸壳算法李旭朝【摘要】在分析传统平面点集凸壳算法的基础上,给出了一种新的平面点集凸壳算法,对算法步骤进行了详细说明,并对此算法可行性进行了验证,最后对算法时间复杂度进行了分析探讨,得到了很好的效果.【期刊名称】《兰州工业学院学报》【年(卷),期】2011(018)002【总页数】3页(P16-18)【关键词】极值点;夹角;子集;凸壳算法【作者】李旭朝【作者单位】兰州交通大学数理与软件工程学院,甘肃730070【正文语种】中文【中图分类】TP301.60 引言凸壳即最小凸包，是包含集合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,pointsn=size(points)istrue=1for i=0,n[2]-3 do beginifmutiply(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 beginistrue=0 ;有凹点breakendforreturn,istrueend//对排序后的点集先进行判断，是否有凹点，如果有则修改，否则不进行处理if check eq 1 then bginm=1while (m) do beginif checkerror(points eq 0 then beginpoints=modify(points)endif else beginbreakendelseendif else beginpoints=modify(points)endelse图1所示为其运行效果.图1 算法运行效果4 算法的时间复杂度讨论平面点集中包括n个平面散乱点，在step2中查找Xmax，Ymax，Xmin，Ymin 这四个极值点所对应的点的过程，时间复杂度应为O(n)，从step4到step6是对子区间1、2、3、4分别求平面点集凸壳，因为其它很多无关的点在每次求出一个凸壳上的点后都将被删除，所以其消耗的时间主要是在判断点与直线的位置关系上，因此该算法的时间复杂度是O(nlogn).本文所提出的平面点集的凸壳算法，对一些计算效率要求较高并且对计算精度要求较低的情况或者海量数据的情形下特别适合.对一些有固定计算精度的情况，我们可以先对各个方向的相关参数进行计算，将现成的方向列表先存储到算法中，这样加快了计算近似凸壳的过程。

一种高效的平面点集凸包算法

一种高效的平面点集凸包算法
梁彪;常岑
【期刊名称】《海洋测绘》
【年(卷),期】2024(44)1
【摘要】为了提高凸包计算的效率,针对海岛正射点云的特点,提出了三级过滤措施,将平面点集抽稀至似边缘点集并排序,在此基础上改进了Graham算法,算法的时间复杂度为线性对数阶。

通过对黄海开山岛等6个海岛点云进行计算,在普通、集中、扩散等3种类型情况下与多个经典算法进行对比,结果表明该算法平均运行效率为Quickhull算法的1.68倍、Andrew算法的8.93倍、Graham算法的20.65倍。

因此,该算法可以被作为海岛、海岸、独立建筑物等正射点云凸包计算的关键算法。

【总页数】5页(P53-57)
【作者】梁彪;常岑
【作者单位】江苏省测绘产品质量监督检验站
【正文语种】中文
【中图分类】P23
【相关文献】
1.一种平面点集的高效凸包算法
2.一种平面点集凸包与三角网格综合生成的算法
3.一种高效的平面点集凸包递归算法
4.环状分布平面点集的凸包快速生成算法
因版权原因，仅展示原文概要，查看原文内容请购买。

基于区域正交化分割的平面点集凸包算法

基于区域正交化分割的平面点集凸包算法
李可;高清维;卢一相;孙冬;竺德
【期刊名称】《自动化学报》
【年(卷),期】2022(48)12
【摘要】为解决实际工程应用中具有超大规模的平面点集的凸包计算问题,提出了一种基于点集所在区域正交化分割的新算法.利用点集几何结构的部分极点对平面点集进行正交化分割,以获取不相干的点集子集簇,再对所有点集子集分别计算其凸包极点,最后合并极点得到凸包点集.在不同层级的正交化分割过程中,根据已知极点的信息,逐层舍去对于凸包极点生成没有贡献的无效点,进而提高算法运行效率.在与目前常用凸包算法的对比实验中,该算法处理超大规模的平面点集时稳定性高且速度更快.
【总页数】9页(P2972-2980)
【作者】李可;高清维;卢一相;孙冬;竺德
【作者单位】安徽大学电气工程与自动化学院;安徽大学计算智能与信号处理教育部重点实验室
【正文语种】中文
【中图分类】TP3
【相关文献】
1.基于改进凸包算法的肺区域分割
2.基于均匀分布的平面点集的凸包加速算法研究
3.基于3D区域增长法和改进的凸包算法相结合的全肺分割方法
4.基于有序简单多边形的平面点集凸包快速求取算法
5.基于有序点列的平面点集凸包的新算法
因版权原因，仅展示原文概要，查看原文内容请购买。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

图 1 点集的划分
断其凹凸性，在此过程中如果判断出某个顶点是凹顶点，则删
显然点集凸壳上的点不会超出矩形 M1M2M3M4 的范围，并且凸壳上的点除了 H1 ～H8 外只能出现在小矩形区域
除该顶点，并返回前一个顶点，沿顺时针方向继续判断，直至最后一个顶点。经过如此的判断删除最终会得到一个凸多边形，
在 Pl 子集中 y 坐标最大的点记为 H8，y 坐标最小的点记为 H7；
在 Pr 子集中 y 坐标最大的点记为 H3，y 坐标最小的点记为H4；
在 Pt 子集中 x 坐标最小的子集中 x 坐标最小的点记为 H6，x 坐标最大的点记为 H5。
表 1 利用 4 个极点确定多边形方向的规则
所有 y 坐标小于等于该点 y 坐标的点；然后在 LT 剩余点中再找出一个 x 坐标最小的点如图 2 中 lt2，并将其放入 plt 末尾，删除 LT 中 y 坐标小于等于该点 y 坐标的点，持续搜索删除直至 LT 为空。将 H1 点放入 plt 末尾，得到点列 plt={H8，…，H1}。
Σn λi≡1，λi≥0，λi∈R，i=1，2，…，n}为{pi }i=1 的凸包，包含 S 的
i=1
最小凸多边形为 S 的凸壳。定义 2 对于简单多边形某个顶点，若交于该顶点的相邻
两边所形成的内角（即由该多边形所围成有界区域内所形成的角）小于 180°，称该顶点为凸顶点；否则，称其为凹顶点。所有顶点为凸顶点的多边形称为凸多边形。
ÁM4
H6 H5
M3
最后将 4 个点列按序合并为一个点列{plt，prt，prb，plb}，其中可能会出现重复的 H（i i=1，2，…，8），删除重复点，然后顺次连接各点可得到一个顺时针方向的简单多边形，称其为点集的轮廓多边形，如图 6（a）。对此多边形从第二个点开始（因为第一点 H8 一定是凸顶点），沿着顺时针方向逐点利用极点顺序法判
基金项目：国家自然科学基金（the National Natural Science Foundation of China under Grant No.60134010）；兰州交通大学“青蓝”人才工程资助计划（No.QL-06-11A）。
作者简介：赵军（1975－），男，副教授，博士生，主研方向：计算机图形图像学；曲仕茹（1963-），女，教授，博士生导师，主研方向：交通信息与控制。收稿日期：2008-04-29 修回日期：2008-07-29
NXmin>NXmax 且（NYmax<NXmax 或者 NYmax>NXmin 或者 NXmax<NYmin<NXmin） NXmin>NXmax 且（NYmin<NXmax 或者 NYmin>NXmin 或者 NXmax<NYmax<NXmin）
2 算法原理
对于给定的平面点集，为了提高求其凸壳的效率，应尽可能高效地删除不在凸壳上的点。为此采取了先将点集中可能的凸壳顶点划分在 4 个区域中，然后逐个区域删除明显不在凸壳
摘要：提出一种计算平面点集凸壳的快速算法。利用极值点划分出四个矩形，它们包含了所有凸壳顶点，通过对矩形中的点进行扫描，排除明显不是凸壳顶点的点，剩余的点构成一个简单多边形。再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点，最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了，避免了乘法运算（除最坏情况外），从而节省计算时间。关键词：平面点集；凸壳；简单多边形；凹顶点 DOI：10.3778/j.issn.1002-8331.2009.01.016 文章编号：１００２－８３３１（２００9）01-0056-03 文献标识码：Ａ中图分类号：301.6
H4 rb1
H4 rb1
H4 rb1
H4 rb1
rb2
rb2
rb3
rb2 rb3
H5
H5
H5
H5
图 4 子集 RB 中点的处理
H7
H7
H7 lb3
H7 lb3
lb2 lb1
lb2 lb1
lb2 lb1
H6
H6
H6
H6
图 5 子集 LB 中点的处理
ÁM1
H1
H2
M2
H8 H7
M5 M6 M8 M7
H3 H4
ZHAO Jun，QU Shi-ru.Efficient convex hull algorithm for plane point puter Engineering and Applications，2009， 45（1）：56-58.
Abstract：An efficient algorithm for computing the convex hull of plane point set is proposed.Firstly，according to the extremity point of the point set，the point on the convex hull is restricted in four rectangles.By scanning the point in rectangles the point which is in evidence not on the convex hull is eliminated，and remain points can constitute a simple polygon.Then，the convexityconcavity of polygon’s vertex is recognized by the vertices sequence and all concavity vertexes are stly，a convex polygon is obtained and it is just the convex hull of the point set.Test results show the high efficiency and stability of this terse algorithm. Key words：plane point set；convex hull；simple polygon；concave vertex
根据凸壳顶点在点集中的分布特点提出了一种算法。第一步将点集先分区并删除不包含凸壳顶点的区域，第二步对剩余分区内的点作精简并得到点集的一个外围轮廓多边形，第三步精确删除此多边形中不是凸壳顶点的点，最终得到的凸多边形
即为凸壳。
1 相关定义
n
Σ 定义 1 设 pi∈R2，（i=1，2，…，n），称点集 S={s|s= λi pi， i=1 n
Á 上的点，结果会得到一个点集的外轮廓点列。此点列确定一个
简单平面多边形，通过判断顶点的凹凸性对多边形进行所有凹顶点删除，最终得到一个凸多边形即为所求的凸壳。具体如下：
对平面点集 pi=（xi，y）i ，i=1，2，3，…，n，求出 xmax=max（x）i ， xmin=min（x）i ，ymax=max（y）i ，ymin=min（y）i ，其中所有具有最小 x 坐标值的点构成的子集称为 Pl 子集，具有最大 x 坐标值的点构成的子集称为 Pr 子集，具有最小 y 坐标值的点构成的子集称为 Pt 子集，具有最小 y 坐标值的点构成的子集称为 Pb 子集。
对子集 RT 中的点作如下处理：建立一个点列 prt={H2}，找出 RT 中 y 坐标最大的点，如图 3 中 rt1 点，若这样的点不止一个，取其中 x 坐标最大的点，将其放入 prt 末尾，并删除 RT 中所有 x 坐标小于等于该点 x 坐标的点；然后在 RT 剩余的点中再找出一个 y 坐标最大的点并将其放入 prt 末尾，删除 RT 中 x 坐标小于等于该点 x 坐标的点，持续搜索删除直至 RT 为空，将 H3 点放入 prt 末尾，得到点列 prt＝{H2，…，H3}。
赵军，曲仕茹：平面点集凸壳的快速算法
2009，45（1） 57
角形的方向可按极点顺序法进行判断：设三角形由 p1、p2、p3 顺序构成，分别用 NXmin 表示三个点中 x 坐标最小的点的序号、 NXmax 表示三个点中 x 坐标最大的点的序号、NYmin 表示三个点中 y 坐标最小的点的序号、NYmax 表示三个点中 y 坐标最大的点的序号（显然 NXmin、NXmax、NYmin、NYmax 的值为 1、2 或者 3）。通过 NXmin、NXmax、NYmin、NYmax 的大小关系可确定此三角形的方向，规则[7]见表 1。
H1
H1
H1
lt1 H8
lt2 lt1 H8
lt2 lt1 H8
图 2 子集 LT 中点的处理
多边形为逆时针
多边形为顺时针
NXmin<NXmax 且（NYmin<NXmin 或者 NYmin>NXmax 或者 NXmin<NYmax<NXma）x NXmin<NXmax 且（NYmax<NXmin 或者 NYmax>NXmax 或者 NXmin<NYmin<NXma）x
定义 M1=（xmin，yma）x ，M2=（xmax，yma）x ，M3=（xmax，ymin），M4=（xmin， ymin），M5=（H1x，H8）y （其中 H1x 表示 H1 点的 x 坐标，以下类似）， M6=（H2x，H3）y ，M7=（H5x，H4）y ，M8=（H6x，H7）y ，如图 1。
平面点集的凸壳指的是包含点集中所有点的最小凸多边形，且其顶点必须为点集中的点。平面点集的凸壳问题在计算机图形学、图像处理、模式识别、地理信息等众多领域中有广泛的应用。对于凸壳的计算国内外进行了不少研究，提出过如卷包裹法、格雷厄姆算法、分治算法、增量算法、实时算法、快速算法等。Yao[1]证明了 O（nlogn）是平面点集凸壳算法时间的复杂度下限，因而尽量减少参与构建凸壳的离散点数目成了提高凸壳计算速度的重要途径。刘润涛[2]在对多边形凸壳的计算中利用了多变形的极点进行划分区域，从而删除部分点来节省计算时间，但他忽视了极值点重复的情况。孔宪庶[3]，陈平[4]、金文华[5]、周培德[6]也都分别提出过计算平面点集凸壳的算法。但是这些算法在对点的处理中都免不了要用到乘法运算来确定点与直线的位置关系，用时较多。

平面点集凸壳的快速算法_赵军

合集下载