包围n个点的最小圆(100分)

  • 主题发起人 主题发起人 muyirenyan
  • 开始时间 开始时间
一觉醒来，突然想到“求出最小圆（不用判断是否所有点都在圆内）”这句话其实是错的。
反例：
考虑由以下5点：(0,0), (1,1), (1000,1), (1000,-1),(-1,-1)组成的凸包，由(0,0), (1,1), (-1,-1)三点所确定的圆是最小的凸包顶点圆。而(1000,1)与(1000,-1)显然在圆外。因此在使用上面算法时，三三取凸包顶点成圆时，必须判断其他凸包顶点是否在圆内，而不能直接取凸包顶点最小圆
 
谢谢,各位的帮助,一直在关注
 
用收缩法，时间复杂度可以做到为N*LnN（N乘以N的对数）
 
题目有两个条件：
1。包含所有点
2。最小圆。
满足第一个条件的是所有点中的最大最小坐标形成的一个外接矩形。
满足第二条件的最小圆圆心必然在外接矩形的对角线交点上。
有了这两步操作后，根据圆心和各点的最远距离作圆就是最小圆了。
 
dinglj1760 以等腰梯形的下底为直径的圆,一定比你说的那个圆要小
 
最小圆肯定过距离最远的两个点是肯定的
 
回答错误,自己删
 
重新来回答.

1. 找俩个点远的点. 这俩点的连线中心做 圆点.
2.找离"圆点"距离最远的第三点,(排除在同一条直线上的点)

以这三点做圆.


三点确定的三角形 △ABC
边AB、AC的垂直平分线，并交于一点O，O为圆心。
以OA为半径画圆
 
一个圆只过一点时，那么这个圆一定可以缩小至第二个点到边界上。
如果一个过两个点的圆不以这两个点为直径，那么这个圆一定可以向一侧偏移，直至第三个点落到边界上。
我想，先求出以最远两点过圆的圆，让圆形在这两点中垂线上移动，然后让其他各点落在边界上，求出半径的全部列表后在比较。当中可能会可以简单化。
 
问题是能否证明“最小圆肯定过距离最远的两个点”。如果能证明这一点，这个问题就非常简单了。
 
“最小圆肯定过距离最远的两个点 ”是显然不正确的
 
to cnbell
前面已经证明过，以最远两点（设为AB）为直径作圆，的确是最小圆，但未必能包括所有点。而如果保持圆心在AB连线上，扩大半径来包括所有点，则未必是最小圆。也就是说最远两点与所求的圆心位置以及半径都没有直接关系。
 
这样呢:

先找一个最大的正方形(里面就包括所有的点的)
 
解这道题的方法很多，最直接的就是穷举，当然，效率是很低的，其时间复杂度是N的4次方。

我现在能够找到的方法是收缩算法，时间复杂度是N*LnN，希望弟兄们有更高效的方法。
 
1,以正负xy方向逼近点阵,作出最小矩形,然后画出矩形两组对边的垂直中分线
2, 现在可以将点阵粗略看作一个对称图,因为矩形的四条边每条边都最少包括一个点
3,圆心必是那两个中分线的交点,简单说就是对角线交点,不过这样说有助于理解
4求出距离圆心教远（设距离b）的矩形边上距离中分线与边交点最远的点（设距离a）
然后a^2+b^2的和再开方求出半径
5，至此，圆心求出，半径求出
6，这是最重要的一点，以上是点阵最理想的情况：凸包集在正负xy方向最“凸”／／：）
7，前边的只是一个特例，一般情况下，我的总体思路就是：先画出一个对称的，
包括点阵的最小图形，然后求出对称中心
有中心求半径就不难了
8，这是我瞎想的，请高手斧正！
 
这里有求凸包的C代码（两个算法——graham 扫描法、卷包裹法）：
http://blog.chinaunix.net/article.php?articleId=58288&blogId=9337
我大致看了一下，复杂度约为 N^2 。如果我们假定点集在平面中的分布是“均匀”的，
那么凸集的点数n和总点数N应当大致存在这样的关系：
N ≈ n*n / 4
代入上面复杂度为n^4的复杂度算式，在通常情况下，复杂度应该能降低不少:)

另外，证明“包含所有顶点的最小圆一定是凸包的外接圆”可以这样：若A是一个凸包的
最小外接圆，那么任意一个位于凸包之内的点必定都在这个外接圆之内——因为凸包内的点
都在凸包的顶点集所构成的多边形之内，而这个多边形又被外接圆所完全包容；另外，又因
为A已经是凸包的最小外接圆，必定不存在比A更小的、能够包围该凸包所有顶点的圆——原
命题得证。

我查到在学术杂志上有人已经发表了针对这个问题的论文：
汪卫，王文平，汪嘉业，求一个包含点集所有点的最小圆的算法，软件学报，2000，11（9）：1237-1240
:-)
 
to 沙隆巴斯的主人: 请问能详细说说收缩算法的步骤吗？

to lanyun2:
“圆心必是那两个中分线的交点”
我在前面证明过“圆心不是矩形中心了”，我所指的矩型是与坐标轴平行的矩型。如果你指的是任意方向的矩形，希望能给出证明，以及如何求得这个矩形。

“4求出距离圆心教远（设距离b）的矩形边上距离中分线与边交点最远的点（设距离a）
然后a^2+b^2的和再开方求出半径”
如果能定出圆心位置，那么最小圆半径必为圆心与距离圆心最远一点的距离。不用另外再求了。

“一般情况下，我的总体思路就是：先画出一个对称的，包括点阵的最小图形，然后求出对称中心”
如果所说的“最小对称图形”是指面积最小的不规则对称图形（中心对称？轴对称？）。我觉得一般情况下，这个“包括点阵的最小对称图形”，会比“包括点阵的最小圆形”更难求。
 
muhahaha, 那篇几何算法挺全的，抄袭中。。。谢谢creation-zy推荐.
 
您必须登录或注册才可回复。

Similar threads

不
奇淫怪巧之给Delphi的PrintDialog增加一个页码选定范围打印的Edit - 不得闲
回复
0
查看
914
不得闲
不
S
[教程]ZAsync 异步编程之四：请记住匿名函数是一个接口
回复
0
查看
725
swish
S
不
关于Delphi的子类化控件消息淫荡法则之一 - 不得闲
回复
0
查看
774
不得闲
不
不
Delphi中设置条件断点 - 不得闲
回复
0
查看
832
不得闲
不
S
[教程]IZAsyncInvoker 异步编程之三：我们对异步编程的一些观点
回复
0
查看
741
swish
S
后退
顶部