Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 包含点集的最小圆
发信站: 哈工大紫丁香 (2002年09月21日22:41:46 星期六), 站内信件

文章编号:1001-9081(2000)Ｓｕｐｐｌ.-0065-02
求包含点集的最小圆的算法汪　
卫1,汪嘉业2(1.复旦大学计算机系,上海200433;　2.山东大学计算机系,济南山东250000
)
摘　要:求包含点集的最小圆是计算机图形学中的一个重要问题,本文提出了一种
时间复杂性最差为ｏ(ｎ2)的算法,并证明了其正确性。
关键词:边界盒;最小圆;点集中图分类号:ＴＰ391.41　　文献标识码:Ａ1　
引言求包含点集的最小圆计算机图形学[1-3]和空间数据库[5,6]中是十分有用的。
因为在图形学和空间数据库中常用它作为边界盒去减少不必要的计算量,或建立空
间数据的索引以提高查询速度。同时由于圆的中心是到点集各点最长距离最短的点。
因而在规划上也有其应用价值。这个问题的算法在计算几何的书上及论文中未见报
道。直观的做法是求遍三个点及两个点的组合,将每三个点和两个点生成的圆且能
包含所有点的找出,然后求其最小的一个,即为所求。这种算法的计算复杂性为
ｏ(ｎ4)。ｎ为点集中点的个数。本文给出了一个新的算法,证明这种算法的时间复
杂性为ｏ(ｎ2)。2　包含点集的凸多边形的求法由于包含点集的凸边形的顶点数远
小于点集中的点的个数,因此对包含点集的凸多边形求最小覆盖圆的计算复杂性将远
小于直接对点集中的点求最小覆盖圆。求包含点集的凸多边形的算法可分成两步:第
一步求覆盖点集的任意多边形;第二步求任意多边形的凸包。求包含点集的任意多边
形的算法的基本思路是:将点集中的点按照与点集覆盖范围内的一点形成的角度进行
排序。形成一个通过顶点为点集中所有点的任意多边形。具体见算法1。
算法1(见图1ａ):
1)任取点集中的两点ａ和ｂ,求这两点形成线段的中点ｏ。
2)对点集中每个点ｐ求角ａｏｐ。将点集中的点按照角度的大小排序,形成一个队列。
3)对队列列中的点ａ1,ａ2,…,ａｎ对应的角度相同,找出与ｏ距离最远的点ａ′。将其
它的点从队列中删除。4)将队列中的相邻的点用线段连接在一起。形成一个任意多边
形。求任意多边形的凸包的算法[4]。其计算复杂性为ｏ(ｎ)。　　
3　凸多边形的最小覆盖圆求凸多边形的最小覆盖圆算法的基本思想是首先求一个通
过圆上相邻两个顶点且覆盖凸多边形其它所有顶点的圆,然后逐步缩小该圆,并保证每
次新生成的圆都覆盖所有的顶点,直到找到最小的圆。图1在算法中将凸包的顶点分为
两部分,一部分为已处理区,另一部分为未处理区。已处理区中的点在后面的循环中不
再考虑。ｐ1ｐ2为两个区的分界点。使用数组ｒ存储算法中每次计算的未处理区中的
点与ｐ1ｐ2构成的圆的半径。算法1:
1）将凸多边形的顶点按顺时针的次序排成一个环。
2）任选多边形的一个边ｐ1ｐ2。将ｐ1ｐ2加入定为已处理区。
3）ｄｏ
4）｛将数组ｒ清零。
5）ｆｏｒ（已处理区外的所有顶点ｑｉ）
6）｛计算线段ｑｉｐ1的垂直平分线与ｐ2ｐ1的垂直平分线的交点ｓ；
7）　ｉｆ（ｓ和已处理区中的顶点在ｐ2ｐ1的两边）　　　
将ｓ与ｑｉ之间的距离存入数组ｒ［ｉ］；　　
ｅｌｓｅ　　　ｒ［ｉ］=0；　｝
8）从数组ｒ中读取最大值，设对应的顶点为ｐ3；
9）如上一步选出的最大值为0，则算法结束，最小圆为以ｐ1ｐ2为直径的圆。
／／做以ｐ1，ｐ2为直径的圆。
10）如ｐ3ｐ1和ｐ1ｐ2的垂直平分线的交点与已处理顶点在ｐ1ｐ3或ｐ2ｐ3的同一侧，
则算法结束，最小圆为通过ｐ1，ｐ2，ｐ3的圆。／／做通过ｐ1，ｐ2，ｐ3的圆。
11）设ｐ1′，ｐ2′为原来ｐ1，ｐ2，ｐ3中距离最远的两个点。ｐ1′，ｐ2′间包含
另外一点的部分为已处理区。这时ｐ1，ｐ2，ｐ3（或ｐ2，ｐ1，ｐ3）仍处在一个劣弧
（弧度<180）上。把劣弧的两个端点ｐ1，ｐ3（或ｐ2，ｐ3）定为新的ｐ1和ｐ2。
在多边形上从ｐ1到ｐ3并包含ｐ2（或从ｐ2到ｐ3并包含ｐ1）那一部分的所有顶点定
为已处理点。／／做通过ｐ1，ｐ2，ｐ3的圆。12）Ｗｈｉｌｅ（ｔｒｕｅ）算法的执
行过程见例1。例1　求包含图2(ａ)中5个点的最小的圆。在第3-12步的第一次循环中
算法从右下方的两个实心点出发寻找到一个新点(空心点)这三个点构成的圆可包含其它
的两个点。然后将图2(ｂ)中的空心点和最右边的实心点之间的点定义为已处理区。从
这两个点出发开始在第3-12步的第二次循环。在第3-12步的第二次循环中算法从图2
(ｃ)中两个实心点出发寻找到一个新点(空心点)这三个点构成的圆可包含另外一个不处
于已处理区中的点。由于这三个点(两个实心点和一个空心点)处在圆的一个处在一个优
弧(弧度>180)上所以算法结束。最后一次生成的圆就是包含包含图2(ａ)中5个点的最
小的圆。通过上面的例子可以看到算法1中第3-12步的循环的具体执行次数和凸包的顶
点的空间分布情况有较大的关系。我们在其它的例子中发现第3-12步的循环最少执行
次数和点集中点的个数无关。下面我们将证明算法1的最大计算复杂性。算法的正确性
见[7]。定理1算法的计算复杂性最差为ｏ(ｎ2)(ｎ为点集中点的个数)。
证明:对算法1可得算法的计算复杂性为ｏ(ｎ ｌｏｇｎ)。而从任意多边形求凸多边形的
计算复杂性为ｏ(ｎ)[4]。对算法2:由于3)开始的ｄｏ语句每次执行时均从未处理部分
中取点加入已处理部分,未处理部分的点会越来越少,且当剩下最后两个点时算法一定会
结
束,所以ｄｏ语句最多执行ｏ(ｎ)次。而5)到11)的计算复杂性为ｏ(ｎ)。所以算法2的计
算复杂性最差为ｏ(ｎ2)。所以算法的计算复杂性最差为ｏ(ｎ2)。(ａ)(ｂ)(ｃ)图24　
总结我们在ＰＣ机上实现了上述算法,并进行了测试,我们发现在很多情况下,特别是在凸
多边形本身的形状与一个圆有较大差别的时候,算法2的3)到13)的大循环只执行很少的几
次就能找到最小的圆。因此算法具有较高的效率。以后我们将对多维空间内点的最小包
含
问题进行进一步的研究。
--
如果你一分钟之内收到二十个call，不是证明你是女的，而是证明，他是男的。

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.249.224]