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

  • 主题发起人 主题发起人 muyirenyan
  • 开始时间 开始时间
M

muyirenyan

Unregistered / Unconfirmed
GUEST, unregistred user!
包围在同一平面上的n个点最小圆怎么算 各位帮忙看看
 
唉！数学问题，给个思路，代码不写了（懒得翻书看三角函数）。
1.3个不在一条直线上的点确定一个园，根据这规则列出所有存在的园的可能的点的组合；
2.计算这些园的直径，直径最大的就是所要求的园。
 
我又想了一下，好像思路不对。
 
想到了，计算所有点之间的距离，用距离最远的两个点之间额直线作为直径作的园应该就对了。
 
是不是找出这些点的左上角和右下角，就是找出包围这些点的最小矩形，矩形的对角线就是园的直径
 
唉，我那个好像也不对..............
 
矩形的对角线交点为圆心，圆心到最远点的距离为半径
 
列个坐标,比如是x,y坐标,找出x最小,最大点,y最小最大点,找到4个点后以这四个点做内切点做个圆,不知道对不对
 
只要思路,不用写代码
 
1：确定半径
将所有点的X轴坐标与Y轴坐标进行排序，找X轴最大点与最小点坐标差与Y轴最大点与最小点坐标差进行比较，如果X轴大，则差值的一般既为半径。反之Y轴差值的一般为半径。
2：确定圆心
找X轴中心画垂线，找Y轴中心画垂线，焦点既为圆心
 
未经证明的想法：
圆心X坐标：最小的X坐标与最大的X坐标的中值
圆心Y坐标：最小的Y坐标与最大的Y坐标的中值
半径：圆心与最远点的距离

===================================
三分钟后编辑：
想到了反例， 以上做法错误。
反例： 点(0,0),(2,0),(1,-1), (0,1), 按以上算法得出圆心为(1,0), 半径为(1,0)到(0,1)的距离sqrt(2)。 显然此圆只经过(0,1)而与其他三点都不相交，因此可把圆心向(0,1)点方向稍微移动，并以新圆心与(0,1)直线距离为半径画圆，直至新圆与另一点相交。则此新圆比旧圆小，且包括所有点
 
1、定义一个结构，某个点到其它点的最大距离
type pointDistance =record
startPointNo: integer;
endPointNo: integer;
distance: integer; //是编号为startPointNo的点到其它点中的最大距离，到最大距离点的编号为endPointNo；
end;

2、定义数组：pointDistanceArray: array[0..N -1] of pointDistance; //存储每个点到其他点的最大距离
pointArray: array[0..N -1] of Tpoint; //N个点

3、求出对应每个点的pointDistance ，填入数组pointDistanceArray，查找pointDistanceArray中所有元素中distance最大的那个元素，则以该元素的 startPointNo，endPointNo为圆直径的两个端点画圆即可。
 
另，以最远两点为直径端点画圆也是错误的。
反例：
设最远两点为点A,B。以它们为直径端点画出的圆为C1
以A为圆心，AB为半径画圆，设此圆为C2；以B为圆心，AB为半径画圆，设此圆为C3。
则C1为C2，C3的内切圆，C2与C3在C1外有交集。设点C在C2与C3的交集内而不在C1中，显然AC<AB, BC<AB （圆内点到圆心距离<半径），但C不在C1中
 
是计算所有点的离散度,也就是离散度的一种度量方法的变形
 
同意kidneyball！

1、定义一个结构，某个点到其它点的最大距离
type pointDistance =record
startPointNo: integer;
endPointNo: integer;
distance: integer; //是编号为startPointNo的点到其它点中的最大距离，到最大距离点的编号为endPointNo；
end;

2、定义数组：pointDistanceArray: array[0..N -1] of pointDistance; //存储每个点到其他点的最大距离
pointArray: array[0..N -1] of Tpoint; //N个点

3、求出对应每个点的pointDistance ，填入数组pointDistanceArray，查找pointDistanceArray中所有元素中distance最大的那个元素，设置找到的这两个点为
startPointNoMax, endPointNoMax,则连接这两点的直线中点设为PointMid，
则
PointMid.X := (startPointNoMax.X + endPointNoMax.X) / 2;
PointMid.Y := (startPointNoMax.Y + endPointNoMax.Y) / 2;
4、求N个点到点PointM的最大距离，设找到的最大距离为MaxSemDistance；
5、以PointMid为圆心，以MaxSemDistance为半径画圆即可。
 
to superdba:
这样有反例，例如上面我所提到的ABC三点。你的做法是以AB中点O为圆心，CO为半径画圆。由于OC>OA=OB，这个圆就只经过C点，A和B都在圆内。这样，就可以沿OC方向移动圆心，设新圆心为O'，以CO'为半径画圆。直至新圆经过A或B其中一点，而另一点还在圆内或同时被新圆经过。显然新圆包括了所有的点，而且CO'<CO，新圆比原来的圆要小。
===================================
可以看出，这个包括所有点的最小圆有三个必要条件：
1.它的半径必定是圆心与距离圆心最远的点的距离
2. 它至少要经过两个点(否则可以沿圆心与最远点的连线移动圆心直至新圆通过另一个点，此时新圆比原来的圆小）
3.设最小圆通过的两个点是AB，则要么最小圆的圆心在AB中点，要么最小圆必通过第三个点。（理由同第二点，如果圆心不在AB中点，而所有其他点都在圆内，则沿AB中垂线，向AB中点方向移动圆心，直到新圆与任一第三点相交，此时新圆比旧圆小，且包括所有点）
 
想到一个方法，是根据我上面贴子提出的条件为基础的：

条件1：最小圆必通过至少两个点；
条件2：设最小圆通过的两点为AB，则要么最小圆的圆心是AB中点，要么最小圆通过第三个点。

算法如下：

步骤1. 把所有点两两组合，一共有n*(n-1)/2种可能

步骤2. 对每种组合，设两点分别为AB, 可得线段AB的中点O。通过以下步骤求出通过AB且包含所有点的最小圆:

步骤a. 设一个记录器R， 使R等于无限大。

步骤b. 对线外除AB以外的每个点（共有n-2个），设为C。

步骤c. 若OC<=OA, 则放弃该点。否则以三点定圆公式，得出圆心O'.若方程无解，即ABC在同一直线上且OC>OA，则放弃该点。然后比较O'与所有ABC外其他点的距离，若存在一点D，OD>OA=OB=OC,则放弃该点(即判断此圆是否包括所有点，最坏情况要做n-3次比较)。

步骤d1. 若对所有点均有OC<=OA，则R=OA，记录圆心为O。跳到步骤e

步骤d2. 若OC>OA且圆ABC包括所有点。且圆ABC的半径小于R，则使R等于圆ABC的半径，且记录圆心。重复b直至扫描完所有点，

步骤e. 这时R为通过AB点且包括所有点的最小圆的半径。若R仍为无限大，则不存在通过AB两点而包含所有点的圆


步骤3. 对所有两点组合进行以上步骤，找出每个两点组合的最小圆。则这些最小圆中半径最小的一个为所求的包括所有点的圆。

最坏情况下的算法复杂度大概为:n*(n-1)*(n-2)*(n-3)/2

==============================
匆匆写成，考虑不够详细，语言也组织得不太好。欢迎指正
 
还有一个方法，逻辑上简单一点，
首先找出所有点中距离最远的两点，以这两点为直径画圆。然后判断是否其他所有点都在圆内。复杂度为 n*(n-1）/2+(n-2)。若所有点均在圆内，则该圆为最小圆。
否则，把该圆半径记录为R1
把所有点三三组合,共有n*(n-1)*(n-2)/6种可能。对每个组合，用三点定圆公式求出经这三点的圆。若圆半径小于R1，则直接放弃。否则对所有其他点逐点判断是否在圆中。最坏情况下共要比较(n-3)次，若发现有点不在圆中，则放弃此组合。
最后剩下的三点组合都能确定一个包含所有点的圆，这些圆中半径最小的即为所求圆。

最坏情况下算法复杂度为 [两点定圆复杂度+三点定圆并判断圆内点复杂度+最终比较最小圆复杂度] = n*(n-1)/2+(n-2) + n*(n-1)*(n-2)*(n-3)/6 + n*(n-1)*(n-2)/6

但实际复杂度会远小于此数，因为放弃圆半径小于R1的三点圆可以过滤掉大部分小圆。
 
思路：先对点集求凸包，然后对位于凸包顶点上的点三个一组按照朋友们已经提出的方法
来画圆判断。
凸包的获得有很多捷径可走，一旦获得顶点集，总的复杂度会大大降低。而根据凸包上的
点来画圆好像简化的办法不多。

这里有两个帖子，希望能有所帮助：
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1277180
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1375640
 
直觉上同意creation-zy的办法，显然凸包顶点的外接圆必定包含所有点。但一时还想不出如何证明“包含所有顶点的最小圆一定是凸包的外接圆”。

我想到的求凸包顶点的基本思路是：设有两点AB，若点集里所有点均在AB连线同侧或AB连线上，则AB均为凸包顶点或位于凸包边线上。
算法如下：
1. 将所有点两两组合，共有n*(n-1)/2种可能。对每一种组合，设这两点为AB，执行以下操作：
a.若AB为垂直线，则A与B的横坐标相等，设为X
对其他各点C1...Ci...Cn-2，设坐标为Ci(X',Y'),
i.若对所有点Ci(1<=i<=n-2)，均有X>=X'，则AB为凸包顶点; 或
ii.若对所有点Ci(1<=i<=n-2)，均有X<=X'，则AB为凸包顶点;
或
b,若AB非垂直线，则
对其他各点C1...Ci...Cn-2，设坐标为Ci(X,Y), 将X代入AB直线方程得纵坐标Y'
i.若对所有点Ci(1<=i<=n-2)，均有Y>=Y'，则AB为凸包顶点; 或
ii.若对所有点Ci(1<=i<=n-2)，均有Y<=Y'，则AB为凸包顶点;
最坏情况下算法复杂度为n*(n-1)*(n-2)/2。

求出点集后，先取距离最远两点判断是否能取中点画圆，包含所有顶点。若不能，则三三组合，求出最小圆（不用判断是否所有点都在圆内）。

总体来说算法复杂度应该大大减少了，但编程复杂度稍微提高了。如果能证明包含所有点的最小圆一定是凸包的外接圆就完满了。
 
您必须登录或注册才可回复。

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
后退
顶部