1999年2月
第25卷第1期北京航空航天大学学报
Journal of Beijing University of Aeronautics and Astronautics February 1999Vol . 25 No . 11)
简单快速的平面散乱点集凸包算法
金文华
(北京航空航天大学
何 涛 唐卫清唐荣锡
制造工程系) (中科院计算所CAD 室) (北京航空航天大学制造工程系)
摘 要 凸包问题是计算几何的基本问题之一, 在许多领域均有应用. 传统点集凸包算法和简单多边形凸包算法平行发展, 互不相干. 文中将简单多边形凸包算法应用于散乱点集凸包问题中, 提出了新的点集凸包算法. 新算法不仅达到了O (n log n )
的理论时间复杂度下限, 而且极其简单, 易于实现. 该算法已应用于工厂设计软件PDSOFT 中, 实践证明效果很好.
关键词 凸包; 多边形; 算法; 管道; 平面点集; 平剖图分类号 TP 301. 6; TP 391. 72
平面点集凸包的快速求取是计算几何的基本问题之一[1, 2], 在计算机图形学, 图象处理, 设计自动化, 模式识别和运筹学等领域应用较广[1～5]. 虽然目前已有不少凸包算法
在致力于寻求更好的方法.
[3, 6, 7, 8]
边形顶点已按某个方向(顺时针或逆时针) 串连起来的特点. 本文算法综合了这两种优点, 首先用某种排序算法对散乱点集进行排序, 再把排序后的点列按某种规则串连成一个简单多边形. 此时的简单多边形与任意简单多边形不同, 其顶点是有序排列的, 如果简单套用一般的简单多边形凸包算法, 则不能充分利用顶点有序排列的优势. 因此, 本文利用Sklansky 算法的核心, 借鉴陈氏算法的栈结构处理方式, 设计了专门针对顶点有序排列简单多边形的凸包算法, 以此解决了平面点集的凸包求取问题.
, 但人们始终
平面点集凸包是指包含平面点集内所有点并且顶点属于平面点集的最小简单凸多边形. 平面
点集凸包算法可分为两类, 一类是需要对点集中的点按某种原则(如按x 坐标递增的原则) 进行排序, 如Graham 算法
[3]
[1, 3, 6, 9][7]
、Pr eparata -Hong 算
法、Akl -Toussaint 算法等, 这类算法的时间复杂度一般取决于排序算法; 另一类算法无需排序, 但其时间复杂度往往较高, 如Chand -Kapur 算法、Jarvis 算法、Bykat 算法等, 目前已证明了O (n log n ) 是所有平面点集凸包算法时间复杂度的下限[10].
另一类凸包问题是关于简单多边形凸包的求取问题. 简单多边形凸包问题是平面点集凸包问题的特殊情况. 虽然现有许多简单多边形凸包算法均能达到线性时间复杂度, 但由于任意简单多边形的顶点并不是有序地排列(如按x 坐标递增的原则排列) , 从而导致算法复杂且易于出错, 如:Bykat 发现Sklansky 算法的反例[4, 8]; Mc -Callum 和Avis 发现Sha mos 算法的反例[4]; 吴中海发现陈氏算法法[5].
[4]
[2, 4, 5]
[1, 3]
[3, 6]
[8]
1 概念定义
定义1 设P ={V i :i =1, 2, …, n }为散乱点集, P 中x 坐标最小的点称为P 的最左点, 记为M L . 如果P 中有多个点具有最小x 坐标, 则取其中y 坐标最小的点为M L ; 同样, P 中x 最大的点称为P 的最右点, 记为M R . 如果P 中有多个点具有最大x 坐标, 则取其中y 坐标最大的点为M R .
定义2 从M L 指向M R 的有向线段称为P 的分界线.
定义3 非自交的多边形称为简单多边形. 本文假设多边形顶点以逆时针方向串连.
定义4 对于简单多边形内任一顶点, 连接其前后相邻顶点, 产生一个新的简单多边形. 如果该顶点位于新多边形内、新多边形外或相连的线段上时, 分别称该顶点为原简单多边形的凹点、凸点或中性点. 中性点的存在与否不影响简单多边
的细节错误并提出了改进的算
散乱点集凸包算法中处于主流的排序凸包算法的许多优势源自于其对点集的预处理, 即点集的排序; 而简单多边形凸包算法的优势源自于多
收稿日期: 1997-09-01
1) 国家自然科学基金(69673001) 资助项目
第一作者 男 27岁 博士生 现为中科院计算所CAD 室博士后 100080 北京
形的形状, 因此完全可以将其删掉. 本文把中性点当作凹点看待, 为了简洁起见, 把凹点和中性点统称为凹点.
采用矢量叉积法判断顶点凹凸性. 设多边形为逆时针方向, V i =(x i , y i ) 为其任一顶点, V i +1=(x i +1, y i +1) 和V i -1=(x i -1, y i -1) 为V i 的前后相邻顶点. 作矢量叉积:
T =V i -1V i ×V i V i +1
取T 的z 坐标分量, 可得点的凹凸性判断函数:
S (V i -1, V i , V i +1)=[T ]z =(x i -x i -1) ×(y i +1-y i )-(x i +1-x i ) ×(y i -y i -1)
根据S 的正负号可以判断V i 点的凹凸性:
①如果S >0, V i 为凸点;
②如果S =0, V i 为中性点; ③如果S
如图1所示, 顶点4的S 值为负, 故为凹点. 其余顶点的S 值均为正, 故为凸点
.
(y A -y B ) ·x +(x B -x A ) ·y +
(x A ·y B -x B ·y A )
根据F 的正负号可以判断V 与A B 的相对位置关系, 如图2所示.
①如果F >0, V 在A B 的左半平面内; ②如果F =0, V 在所在的直线上; ③如果F
.
图2 点与直线的相对位置判断
2 算法描述
下面以图3a 所示的散乱点集为例介绍凸包算法的基本思路:步骤1:首先用某种排序算法对散乱点集按x 坐标递增的方向进行排序. 如果存在多个点有相同的x 坐标, 则只保留具有最大和最小y 坐标的两个点, 且两点按y 坐标增加的方向排列. 排序完成之后, 可得到点集的最左点M L 和点集的最右点M R . 很显然M L 和M R 肯定在点集的凸包上. 如图3b 所示.
图1 点的凹凸性判断
定义5 设A =(x A , y A ) 和B =(x B , y B ) 为xy 平面内任意不同的两点, A B 为由A 指向B 的有向线段, A B 所在的直线把平面分为两个半平面. 求z 轴的单位矢量与A B 的叉积, 得到的矢量所指向的半平面称为A B 的左半平面, 而另一个称为A B 的右半平面.
如果用齐次坐标表示直线和点, 则可以很容易地判断出点与直线的位置关系.
例如, A 和B 用齐次坐标表示为A =(x A , y A , 1) B =(x B , y B , 1) 所在直线用齐次坐标表示为
A B =(y A -y B , x B -x A , x A ·y B -x B ·y A ) 设V =(x , y , 1) 为平面内任一点, 计算V 与A B 的点积, 可得点与直线的位置判断函数:
F (V , A B )=(x , y , 1) ·
(y A -y B , x B -x A , x A ·y B -x B ·y A )=
步骤2:M L 和M R 所在分界线将点集分为上下两个子集. 位于分界线上方的子集为P U 子集, 其中的点位于分界线的左半平面; 位于分界线下方的子集为P D 子集, 其中的点位于分界线的右半平面. 可用函数F 来进行分类. 设V 为点集中的任一点. 如果F >0, V 点划入P U 子集; 如果F =0, V 点在分界线上, 应当删除; F
在子集分割中, 需要注意的是, 应当使两个子集中的点均按逆时针方向串连起来形成一个不自交且封闭的简单多边形. 本文用单向链表结构表示简单多边形. 子集分割后, 得到的简单多边形的顶点已是有序排列, 即P U 子集中的点集按x 坐标递减的方向排列; P D 子集中的点集按x 坐标递增的方向排列. 此时算法分别对P U 子集和P D 子集作“前趋”和“后退”两种处理.
步骤3:对P U 子集作如下处理:
1) 以最右点M R 为当前凸点;
2) 如果当前凸点为点集的最左点M L , 则停止处理P U 子集, 转向处理P D 子集.
否则, 从当前凸点出发往前搜索凹点, 如果搜索到点M L 时仍未发现凹点, 则停止处理P U 子集, 转向处理P D 子集. 否则, 以所遇到的第一个凹点的后续点为当前基点, 删除当前凹点, 并往前继续搜索所有相邻凹点, 直至遇到另一个凸点或点集最左点M L 为止. 每搜索到一个凹点, 立即将其从链表中删除. 这个过程称为“前趋”处理. 新搜索到的凸点或点M L 置为当前凸点. 点的凹凸性采用函数S .
3) 如果对当前基点作了“前趋”处理, 则应立即作“后退”处理, 即:从当前凸点出发, 往后搜索所有相邻凹点, 直至遇到另一个凸点或点集最右点M R 为止. 同样, 每搜索到一个凹点, 立即将其从链表中删除. “后退”处理完毕后, 转向步骤2) . 如果没有“前趋”处理, 则径直转向步骤2) , 而无需作“后退”处理.
步骤4:对P D 子集的处理与步骤3十分类似, 在此不赘述.
应当注意的是, 每次从链表中删除一个顶点后, 多边形形状将要改变, 此时无论是“前趋”处理还是“后退”处理, 其中点的凹凸性均要以改变后的多边形为基准进行判断.
如图3c 所示, 首先以点0(即M R ) 为当前凸点, 从点0开始搜索, 发现第一个凹点4, 以点4的后续点3为当前基点, 作“前趋”处理:删除点4, 继续往前搜索, 发现点5为凸点, 置点5为当前凸点. 随后作“后退”处理:从点5出发, 往后搜索, 删除点3和点2. 如图3d 所示. 然后从点5出发往前搜索, 发现第一个凹点7, 以点7的后续点6为当前基点, 作“前趋”处理:删除点7, 继续往前搜索, 删除凹点8, 置点9为当前凸点. 此后作“后退”处理:从点9出发, 往后搜索, 发现点6已经为凸点. 如图3e 所示. 然后从点9出发往前搜索, 发现点10为M L , 停止处理P U 子集. 对P U 子集处理所得的结果如图3f 所示. 类似地可处理P D 子集
.
图3 点集凸包算法图例
3 算法分析
在前趋后退处理过程中, 采用栈结构: struct stac k { 顶点指针:pnt ; }H [];
其中, pnt 是指顶点在简单多边形链表中的指针. 算法基于三种基本操作:PUSH 、POP 和DELE TE . “PUSH V i ”是指将顶点V i 的指针压入栈中; “POP V i ”是指将顶点V i 的指针弹出栈; “DELETE V i ”是指将顶点V i 从简单多边形单向链表中删掉.
在现有的内部排序算法中, QICKSORT 算法是速度最快的方法, 其平均时间复杂度为O (n log n ) , 但其最坏时间复杂度为O (n ) . 完全二叉树排序算法的平均时间复杂度和最坏时间复杂度均为O (n log n ) , 但其辅助存储空间较大且存在与“最大值”进行多余比较的缺点. 堆排序采用树形排序的思想, 但利用的是堆的结构而非完全二叉树结构, 其平均时间复杂度和最坏时间复杂度也均为O (n log n ) , 但其辅助存储空间为O (1) . 因此, 由目前排序算法理论可知, 对散乱点集进行排
[3, 7, 11]
序的算法最坏时间复杂度为O (n log n ) .
2
当点集排序完成后, 对每一个点只须作一次判断和一次插入链表操作, 即可将其归入P U 子集或P D 子集, 因此子集分割的时间复杂度为O (n ) .
由陈诚林[4]和吴中海[5]对其算法时间复杂度的分析可知, 前趋后退算法的时间复杂度也为O (n ) . 因为P U 子集或P D 子集中的每个顶点, 在前趋后退处理过程中, 最多只有一次PUSH 操作, 一次POP 操作和一次DELETE 操作, 而这三类操作所需时间均可看作常数, 所以前趋后退算法的时间复杂度也为O (n ) .
综上分析, 本文提出的平面散乱点集凸包算法的最坏时间复杂度为O (n log n ) .
包特征轮廓, 而无需使用复杂的方法求取元件精确的特征轮廓. 实践证明, 用凸包算法求取的凸包
轮廓进行平剖图消隐, 不但提高了系统的运行速度, 而且消隐结果完全满足工程需要.
参 考 文 献
1 周之英. 平面点集凸壳的实时算法. 计算机学报, 1985, 8(2) :
136～142
2 孔宪庶, 蔡洪学. 简单多边形凸包的双动线检测算法. 计算机
学报, 1994, 17(8) :596～600
3 Preparata F P , Hong S J . Convex hulls of finite sets of points in t wo
and three dimensions . CACM , 1977, 20(2) :87～93
4 Chen Chern Lin . Computing the convex hull of a s imple pol ygon . Pat -tern Recognition , 1989, 22(5) :561～565
5 吴中海, 叶澄清, 潘云鹤. 一个改进的简单多边形凸包算法.
计算机辅助设计与图形学学报, 1997, 9(1) :9～13
6 Jarvis R A . On the identification of the convex hull of a finite set of
points in the plane . Inf Proc Lett , 1973, 2(1) :18～21
7 Akl S G , Toussaint G T . A fas t convex hull algorithm . Inf Proc Lett ,
1978, 7(5) :219～222
8 Bykat A . Convex hull of a finite s et of points in t wo dimensions . Inf
Proc L ett , 1978, 7(6) :296～298
9 Graham R L . An efficient algorithm for determining the convex hull of
a finite planar s et . Inf Proc Lett , 1972, 1(5) :132～133
10 Y ao A C . A lower bound to finding c onvex hulls . J ACM , 1981, 28
(4) :780～787
11 严蔚敏, 吴伟民. 数据结构. 北京:清华大学出版社, 1987
4 结束语
本文提出的平面散乱点集凸包算法利用排序算法与简单多边形凸包算法相结合的方式, 可以简单而又快速地求出点集凸包. 本文算法时间复杂度为O (n log n ) , 达到了平面点集凸包算法时间
复杂度的理论下限, 但算法思路非常简单而且极易实现. 本文算法已应用于工厂设计软件PDSOFT 的平剖子系统图纸消隐模块中. 在管道设计专业的平立剖面图纸(简称平剖图) 的自动消隐中, 需要求取上位元件的特征轮廓. 当元件图形非常小时, 可以采用本文的凸包算法快速求取元件的凸
Simple Fast Convex Hull Algorithm of Planar Poin t Set
Jin Wenhua
(Beijing University of Aeronautics and Astronautics , Dept . of Manufacturing Engineering )
He Tao Tang Weiqing
(Chinese Academy of Sciences , Institute of Computing Technology CAD Lab . )
Tang Rongxi
(Beijing University of Aeronautics and Astronautics , Dept . of Manufacturing Engineering )
Abstract Convex hull pr oblem is one of the fundamental problems incomputational geometr y , and used in many fields . The traditional c onvex hull algorithms of point set and that of simple polygons have parallelly developed without any combination . In this paper , a new algorithm is proposed based on combining the c onvex hull algorithms of simple polygons into solving the problem of point set . The algorithms in this paper not only reaches the lower bound of O (n log n ) , but also is ver y simple and easy to be realized . The presented algorithms has been applied in plantdesign system of PDSOFT . The results obtained by the method areremarkable .
Key words convex hulls ; polygons ; algorithms ; pipelines ; planar point set ; orthographic drawings
1999年2月
第25卷第1期北京航空航天大学学报
Journal of Beijing University of Aeronautics and Astronautics February 1999Vol . 25 No . 11)
简单快速的平面散乱点集凸包算法
金文华
(北京航空航天大学
何 涛 唐卫清唐荣锡
制造工程系) (中科院计算所CAD 室) (北京航空航天大学制造工程系)
摘 要 凸包问题是计算几何的基本问题之一, 在许多领域均有应用. 传统点集凸包算法和简单多边形凸包算法平行发展, 互不相干. 文中将简单多边形凸包算法应用于散乱点集凸包问题中, 提出了新的点集凸包算法. 新算法不仅达到了O (n log n )
的理论时间复杂度下限, 而且极其简单, 易于实现. 该算法已应用于工厂设计软件PDSOFT 中, 实践证明效果很好.
关键词 凸包; 多边形; 算法; 管道; 平面点集; 平剖图分类号 TP 301. 6; TP 391. 72
平面点集凸包的快速求取是计算几何的基本问题之一[1, 2], 在计算机图形学, 图象处理, 设计自动化, 模式识别和运筹学等领域应用较广[1～5]. 虽然目前已有不少凸包算法
在致力于寻求更好的方法.
[3, 6, 7, 8]
边形顶点已按某个方向(顺时针或逆时针) 串连起来的特点. 本文算法综合了这两种优点, 首先用某种排序算法对散乱点集进行排序, 再把排序后的点列按某种规则串连成一个简单多边形. 此时的简单多边形与任意简单多边形不同, 其顶点是有序排列的, 如果简单套用一般的简单多边形凸包算法, 则不能充分利用顶点有序排列的优势. 因此, 本文利用Sklansky 算法的核心, 借鉴陈氏算法的栈结构处理方式, 设计了专门针对顶点有序排列简单多边形的凸包算法, 以此解决了平面点集的凸包求取问题.
, 但人们始终
平面点集凸包是指包含平面点集内所有点并且顶点属于平面点集的最小简单凸多边形. 平面
点集凸包算法可分为两类, 一类是需要对点集中的点按某种原则(如按x 坐标递增的原则) 进行排序, 如Graham 算法
[3]
[1, 3, 6, 9][7]
、Pr eparata -Hong 算
法、Akl -Toussaint 算法等, 这类算法的时间复杂度一般取决于排序算法; 另一类算法无需排序, 但其时间复杂度往往较高, 如Chand -Kapur 算法、Jarvis 算法、Bykat 算法等, 目前已证明了O (n log n ) 是所有平面点集凸包算法时间复杂度的下限[10].
另一类凸包问题是关于简单多边形凸包的求取问题. 简单多边形凸包问题是平面点集凸包问题的特殊情况. 虽然现有许多简单多边形凸包算法均能达到线性时间复杂度, 但由于任意简单多边形的顶点并不是有序地排列(如按x 坐标递增的原则排列) , 从而导致算法复杂且易于出错, 如:Bykat 发现Sklansky 算法的反例[4, 8]; Mc -Callum 和Avis 发现Sha mos 算法的反例[4]; 吴中海发现陈氏算法法[5].
[4]
[2, 4, 5]
[1, 3]
[3, 6]
[8]
1 概念定义
定义1 设P ={V i :i =1, 2, …, n }为散乱点集, P 中x 坐标最小的点称为P 的最左点, 记为M L . 如果P 中有多个点具有最小x 坐标, 则取其中y 坐标最小的点为M L ; 同样, P 中x 最大的点称为P 的最右点, 记为M R . 如果P 中有多个点具有最大x 坐标, 则取其中y 坐标最大的点为M R .
定义2 从M L 指向M R 的有向线段称为P 的分界线.
定义3 非自交的多边形称为简单多边形. 本文假设多边形顶点以逆时针方向串连.
定义4 对于简单多边形内任一顶点, 连接其前后相邻顶点, 产生一个新的简单多边形. 如果该顶点位于新多边形内、新多边形外或相连的线段上时, 分别称该顶点为原简单多边形的凹点、凸点或中性点. 中性点的存在与否不影响简单多边
的细节错误并提出了改进的算
散乱点集凸包算法中处于主流的排序凸包算法的许多优势源自于其对点集的预处理, 即点集的排序; 而简单多边形凸包算法的优势源自于多
收稿日期: 1997-09-01
1) 国家自然科学基金(69673001) 资助项目
第一作者 男 27岁 博士生 现为中科院计算所CAD 室博士后 100080 北京
形的形状, 因此完全可以将其删掉. 本文把中性点当作凹点看待, 为了简洁起见, 把凹点和中性点统称为凹点.
采用矢量叉积法判断顶点凹凸性. 设多边形为逆时针方向, V i =(x i , y i ) 为其任一顶点, V i +1=(x i +1, y i +1) 和V i -1=(x i -1, y i -1) 为V i 的前后相邻顶点. 作矢量叉积:
T =V i -1V i ×V i V i +1
取T 的z 坐标分量, 可得点的凹凸性判断函数:
S (V i -1, V i , V i +1)=[T ]z =(x i -x i -1) ×(y i +1-y i )-(x i +1-x i ) ×(y i -y i -1)
根据S 的正负号可以判断V i 点的凹凸性:
①如果S >0, V i 为凸点;
②如果S =0, V i 为中性点; ③如果S
如图1所示, 顶点4的S 值为负, 故为凹点. 其余顶点的S 值均为正, 故为凸点
.
(y A -y B ) ·x +(x B -x A ) ·y +
(x A ·y B -x B ·y A )
根据F 的正负号可以判断V 与A B 的相对位置关系, 如图2所示.
①如果F >0, V 在A B 的左半平面内; ②如果F =0, V 在所在的直线上; ③如果F
.
图2 点与直线的相对位置判断
2 算法描述
下面以图3a 所示的散乱点集为例介绍凸包算法的基本思路:步骤1:首先用某种排序算法对散乱点集按x 坐标递增的方向进行排序. 如果存在多个点有相同的x 坐标, 则只保留具有最大和最小y 坐标的两个点, 且两点按y 坐标增加的方向排列. 排序完成之后, 可得到点集的最左点M L 和点集的最右点M R . 很显然M L 和M R 肯定在点集的凸包上. 如图3b 所示.
图1 点的凹凸性判断
定义5 设A =(x A , y A ) 和B =(x B , y B ) 为xy 平面内任意不同的两点, A B 为由A 指向B 的有向线段, A B 所在的直线把平面分为两个半平面. 求z 轴的单位矢量与A B 的叉积, 得到的矢量所指向的半平面称为A B 的左半平面, 而另一个称为A B 的右半平面.
如果用齐次坐标表示直线和点, 则可以很容易地判断出点与直线的位置关系.
例如, A 和B 用齐次坐标表示为A =(x A , y A , 1) B =(x B , y B , 1) 所在直线用齐次坐标表示为
A B =(y A -y B , x B -x A , x A ·y B -x B ·y A ) 设V =(x , y , 1) 为平面内任一点, 计算V 与A B 的点积, 可得点与直线的位置判断函数:
F (V , A B )=(x , y , 1) ·
(y A -y B , x B -x A , x A ·y B -x B ·y A )=
步骤2:M L 和M R 所在分界线将点集分为上下两个子集. 位于分界线上方的子集为P U 子集, 其中的点位于分界线的左半平面; 位于分界线下方的子集为P D 子集, 其中的点位于分界线的右半平面. 可用函数F 来进行分类. 设V 为点集中的任一点. 如果F >0, V 点划入P U 子集; 如果F =0, V 点在分界线上, 应当删除; F
在子集分割中, 需要注意的是, 应当使两个子集中的点均按逆时针方向串连起来形成一个不自交且封闭的简单多边形. 本文用单向链表结构表示简单多边形. 子集分割后, 得到的简单多边形的顶点已是有序排列, 即P U 子集中的点集按x 坐标递减的方向排列; P D 子集中的点集按x 坐标递增的方向排列. 此时算法分别对P U 子集和P D 子集作“前趋”和“后退”两种处理.
步骤3:对P U 子集作如下处理:
1) 以最右点M R 为当前凸点;
2) 如果当前凸点为点集的最左点M L , 则停止处理P U 子集, 转向处理P D 子集.
否则, 从当前凸点出发往前搜索凹点, 如果搜索到点M L 时仍未发现凹点, 则停止处理P U 子集, 转向处理P D 子集. 否则, 以所遇到的第一个凹点的后续点为当前基点, 删除当前凹点, 并往前继续搜索所有相邻凹点, 直至遇到另一个凸点或点集最左点M L 为止. 每搜索到一个凹点, 立即将其从链表中删除. 这个过程称为“前趋”处理. 新搜索到的凸点或点M L 置为当前凸点. 点的凹凸性采用函数S .
3) 如果对当前基点作了“前趋”处理, 则应立即作“后退”处理, 即:从当前凸点出发, 往后搜索所有相邻凹点, 直至遇到另一个凸点或点集最右点M R 为止. 同样, 每搜索到一个凹点, 立即将其从链表中删除. “后退”处理完毕后, 转向步骤2) . 如果没有“前趋”处理, 则径直转向步骤2) , 而无需作“后退”处理.
步骤4:对P D 子集的处理与步骤3十分类似, 在此不赘述.
应当注意的是, 每次从链表中删除一个顶点后, 多边形形状将要改变, 此时无论是“前趋”处理还是“后退”处理, 其中点的凹凸性均要以改变后的多边形为基准进行判断.
如图3c 所示, 首先以点0(即M R ) 为当前凸点, 从点0开始搜索, 发现第一个凹点4, 以点4的后续点3为当前基点, 作“前趋”处理:删除点4, 继续往前搜索, 发现点5为凸点, 置点5为当前凸点. 随后作“后退”处理:从点5出发, 往后搜索, 删除点3和点2. 如图3d 所示. 然后从点5出发往前搜索, 发现第一个凹点7, 以点7的后续点6为当前基点, 作“前趋”处理:删除点7, 继续往前搜索, 删除凹点8, 置点9为当前凸点. 此后作“后退”处理:从点9出发, 往后搜索, 发现点6已经为凸点. 如图3e 所示. 然后从点9出发往前搜索, 发现点10为M L , 停止处理P U 子集. 对P U 子集处理所得的结果如图3f 所示. 类似地可处理P D 子集
.
图3 点集凸包算法图例
3 算法分析
在前趋后退处理过程中, 采用栈结构: struct stac k { 顶点指针:pnt ; }H [];
其中, pnt 是指顶点在简单多边形链表中的指针. 算法基于三种基本操作:PUSH 、POP 和DELE TE . “PUSH V i ”是指将顶点V i 的指针压入栈中; “POP V i ”是指将顶点V i 的指针弹出栈; “DELETE V i ”是指将顶点V i 从简单多边形单向链表中删掉.
在现有的内部排序算法中, QICKSORT 算法是速度最快的方法, 其平均时间复杂度为O (n log n ) , 但其最坏时间复杂度为O (n ) . 完全二叉树排序算法的平均时间复杂度和最坏时间复杂度均为O (n log n ) , 但其辅助存储空间较大且存在与“最大值”进行多余比较的缺点. 堆排序采用树形排序的思想, 但利用的是堆的结构而非完全二叉树结构, 其平均时间复杂度和最坏时间复杂度也均为O (n log n ) , 但其辅助存储空间为O (1) . 因此, 由目前排序算法理论可知, 对散乱点集进行排
[3, 7, 11]
序的算法最坏时间复杂度为O (n log n ) .
2
当点集排序完成后, 对每一个点只须作一次判断和一次插入链表操作, 即可将其归入P U 子集或P D 子集, 因此子集分割的时间复杂度为O (n ) .
由陈诚林[4]和吴中海[5]对其算法时间复杂度的分析可知, 前趋后退算法的时间复杂度也为O (n ) . 因为P U 子集或P D 子集中的每个顶点, 在前趋后退处理过程中, 最多只有一次PUSH 操作, 一次POP 操作和一次DELETE 操作, 而这三类操作所需时间均可看作常数, 所以前趋后退算法的时间复杂度也为O (n ) .
综上分析, 本文提出的平面散乱点集凸包算法的最坏时间复杂度为O (n log n ) .
包特征轮廓, 而无需使用复杂的方法求取元件精确的特征轮廓. 实践证明, 用凸包算法求取的凸包
轮廓进行平剖图消隐, 不但提高了系统的运行速度, 而且消隐结果完全满足工程需要.
参 考 文 献
1 周之英. 平面点集凸壳的实时算法. 计算机学报, 1985, 8(2) :
136～142
2 孔宪庶, 蔡洪学. 简单多边形凸包的双动线检测算法. 计算机
学报, 1994, 17(8) :596～600
3 Preparata F P , Hong S J . Convex hulls of finite sets of points in t wo
and three dimensions . CACM , 1977, 20(2) :87～93
4 Chen Chern Lin . Computing the convex hull of a s imple pol ygon . Pat -tern Recognition , 1989, 22(5) :561～565
5 吴中海, 叶澄清, 潘云鹤. 一个改进的简单多边形凸包算法.
计算机辅助设计与图形学学报, 1997, 9(1) :9～13
6 Jarvis R A . On the identification of the convex hull of a finite set of
points in the plane . Inf Proc Lett , 1973, 2(1) :18～21
7 Akl S G , Toussaint G T . A fas t convex hull algorithm . Inf Proc Lett ,
1978, 7(5) :219～222
8 Bykat A . Convex hull of a finite s et of points in t wo dimensions . Inf
Proc L ett , 1978, 7(6) :296～298
9 Graham R L . An efficient algorithm for determining the convex hull of
a finite planar s et . Inf Proc Lett , 1972, 1(5) :132～133
10 Y ao A C . A lower bound to finding c onvex hulls . J ACM , 1981, 28
(4) :780～787
11 严蔚敏, 吴伟民. 数据结构. 北京:清华大学出版社, 1987
4 结束语
本文提出的平面散乱点集凸包算法利用排序算法与简单多边形凸包算法相结合的方式, 可以简单而又快速地求出点集凸包. 本文算法时间复杂度为O (n log n ) , 达到了平面点集凸包算法时间
复杂度的理论下限, 但算法思路非常简单而且极易实现. 本文算法已应用于工厂设计软件PDSOFT 的平剖子系统图纸消隐模块中. 在管道设计专业的平立剖面图纸(简称平剖图) 的自动消隐中, 需要求取上位元件的特征轮廓. 当元件图形非常小时, 可以采用本文的凸包算法快速求取元件的凸
Simple Fast Convex Hull Algorithm of Planar Poin t Set
Jin Wenhua
(Beijing University of Aeronautics and Astronautics , Dept . of Manufacturing Engineering )
He Tao Tang Weiqing
(Chinese Academy of Sciences , Institute of Computing Technology CAD Lab . )
Tang Rongxi
(Beijing University of Aeronautics and Astronautics , Dept . of Manufacturing Engineering )
Abstract Convex hull pr oblem is one of the fundamental problems incomputational geometr y , and used in many fields . The traditional c onvex hull algorithms of point set and that of simple polygons have parallelly developed without any combination . In this paper , a new algorithm is proposed based on combining the c onvex hull algorithms of simple polygons into solving the problem of point set . The algorithms in this paper not only reaches the lower bound of O (n log n ) , but also is ver y simple and easy to be realized . The presented algorithms has been applied in plantdesign system of PDSOFT . The results obtained by the method areremarkable .
Key words convex hulls ; polygons ; algorithms ; pipelines ; planar point set ; orthographic drawings