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

W

wang_junfan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-19

• #61

我的思路，仅作参考，首先假定这个圆已经存在，则落在这个圆上的点至少有两个（否则我可以先移动圆心，再收缩圆）。
（1）首先假设只有两个点落在圆上，那么这两个点必须是圆形的直径（否则我可以移动圆心，收缩圆），所以首先计算所有的点距离最长的两个点，以它们为直径画一个圆，如果所有的点落在这个圆形内，则这个圆形就是所求的圆。
（2）接上面的思路，如果画出上述的圆后，有点在这个圆形外面，则证明所求的圆形至少有三个点落在圆上，那么问题就简化成在一堆点中任意取三个点，画外接圆，所有圆中外接圆直径最大的就是所求的圆。

 

W

wang_junfan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-19

• #62

以上是思路，实际算法可以优化

 

K

kidneyball

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-20

• #63

to 沙隆巴斯的主人
在你第一个算法中(ID：3419095), 迭代是在5-7步之间的. 这里的复杂度是大致符合N*lnN的. 但补充说明之后, 第5步被扩展成了三步, 其中第3步是当圆上有超过3个点时取其中两点再回到第2步. 其实这里才是最外层的迭代.

也就是说, N*lnN的复杂度只是找出一个中间状态而已, 外面还有一层循环,复杂度未知.

 

K

kidneyball

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-20

• #64

to lanyun2
你的算法中(ID：3420352), 第一次执行到第4步, 有ABC三个点. 然后回到第2步, 找到离圆心最远点.在第二次到第4步时, 涉及到四个点(ABC在圆周上, 还有离圆心最远的点C'). 这时应怎样选点?

 

沙

沙隆巴斯的主人

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-20

• #65

to kidneyball：
“其中第3步是当圆上有超过3个点时取其中两点再回到第2步”，它的复杂度是常数啊，对整体复杂度无影响。

 

L

lanyun2

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-20

• #66

距离最远的两个点肯定要入选的(相等就随便选一组)做A，B
第三个点选离线段AB中点最远的点

 

S

smokingroom

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-20

• #67

//思路:首先取得包含n个点的矩形;
//以这个矩形的对角线的作为圆的直径,对角线的交点作为圆心画圆问题即得解
//矩形计算不多说了结果存於R:TRect;
//对角线的一半计算方法:SQRT(W/2*W/2 + H/2*H/2),其中W为矩形宽度,H为矩形高度,SQRT为开二次方,这是简单的平面几何问题了.
//计算出来之后,对矩形进行扩充后画圆即可

//示例代码:
procedure TForm1.Button1Click(Sender: TObject);
var
I:Integer;
X,Y:Integer;
R:TRect;
tmp,tmpX,tmpY:Integer;
ptArray:array of TPoint;
NumberOfPoints:Integer;
begin
Refresh;
R:=Rect(0,0,0,0);
NumberOfPoints:=5;
SetLength(ptArray,NumberOfPoints);
for I:=0 to NumberOfPoints-1 do
begin
X:=Random(Width-200)+100;
Y:=Random(Height-300)+100;
ptArray.X:=X;
ptArray.Y:=Y;
if (R.Left=0) or (R.Left>X) then
R.Left:=X;
if (R.Right=0) or (R.Right<X) then
R.Right:=X;
if (R.Top=0) or (R.Top>Y) then
R.Top:=Y;
if (R.Bottom=0) or (R.Bottom<Y) then
R.Bottom:=Y;
end;
//圆半径的一半
tmp:=Round(SQRT((R.Right-R.Left)/2*(R.Right-R.Left)/2+(R.Bottom-R.Top)/2*(R.Bottom-R.Top)/2));
tmpX:=(tmp*2-R.Right+R.Left) div 2;
tmpY:=(tmp*2-R.Bottom+R.Top) div 2;
R.Left:=R.Left-tmpX;
R.Right:=R.Right+tmpX;
R.Top:=R.Top-tmpY;
R.Bottom:=R.Bottom+tmpY;
Canvas.Pen.Color:=clBlue;
Canvas.Ellipse(R);
Canvas.Pen.Color:=clRed;
for I:=0 to NumberOfPoints-1 do
begin
Canvas.Rectangle(ptArray.X,ptArray.Y,ptArray.X+2,ptArray.Y+2);
end;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
Randomize();
end;

 

S

smokingroom

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-20

• #68

另注，因为点画出来效果不明显，故对点加以放大了。
如果某点看起来超出了许许，事实上是没有超出的。

 

沙

沙隆巴斯的主人

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-21

• #69

楼上的有明显的几何错误，你还是再想想吧。

 

S

smokingroom

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-21

• #70

回答确实有误,已删除.

 

L

Lucker

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-21

• #71

Anylib已经推出新版本！主要增加以下功能：
1.数据库支持
2.数据分组
3.分页符
4.多栏打印
5.背景图

欢迎到我们的网站下载。
http://www.anylib.com

 

L

lanyun2

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-21

• #72

写代码的老兄好像考虑有误阿

 

M

muyirenyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-25

• #73

to kidneyball:
我认为你的方法是正确的,但是还要考虑一种情况以距离最远的两个点为直径时,是否能够包围所有的点,如果是该圆就是最小圆.如果不是如何选A,B,C,D中选3个点,使由它们生成的一个包含这4点的圆为最小

 

K

kidneyball

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-27

• #74

你指论文上的方法吧. 不知你是指他第二步的找圆还是第四步的找圆.
他的第2步说的比较笼统. 但由于只有ABC三个点, 我觉得应该就是先两两组合(3种组合), 看看两点为直径的圆是否包含第三点.如果是, 找出最小的. 如果都不是, 直接三点成圆

他在第4步的找圆也提到了两点成直径的情况, 不过不知道为什么分了段.
===============================================
第4步.在A,B,C,D中选3个点,使由它们生成的一个包含这4点的圆为最小.这3点成为新的A,B和C,返回执行第2步.

若在第4步生成的圆的圆周只通过A,B,C,D中的两点,则圆周上的两点取成新的A和B,从另两点中任取一点作为新的C.
================================================

改一下, 就是&quot;找出A,B,C,D中选出2个或3个点,使由它们生成的一个包含这4点的圆为最小.若该圆仅通过两点,则取这两点为新的A和B,剩下两点中任一点为C,返回执行第2步; 若该圆通过3点,这3点成为新的A,B和C,返回执行第2步.&quot;

 

M

muyirenyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-04-28

• #75

to kidneyball:
我是这么找A,B,C 这三个点的,在A,B,C,D中找出距离最远的两个点为A,B;然后,在判断其它两个点哪个距离AB所在的距离最远哪个点就为C.
结果是正确的.