# Circle with N points inside circle (or on the circle)

How can I construct a smallest possible circle which contains N specified points? I don't speak about cyclic polygons and points ON the circle, I need a routine for all polygons and the points can be INSIDE the circle.
I can do a circumscribed circle for a triangle but I don't know how to solve this one problem :-(

• : How can I construct a smallest possible circle which contains N
: specified points? I don't speak about cyclic polygons and points ON
: the circle, I need a routine for all polygons and the points can be
: INSIDE the circle.
: I can do a circumscribed circle for a triangle but I don't know how
: to solve this one problem :-(

i don't get your point. what is N then? is it a variable or the letter N itself?
• : : How can I construct a smallest possible circle which contains N
: : specified points? I don't speak about cyclic polygons and points ON
: : the circle, I need a routine for all polygons and the points can be
: : INSIDE the circle.
: : I can do a circumscribed circle for a triangle but I don't know how
: : to solve this one problem :-(
:
: i don't get your point. what is N then? is it a variable or the
: letter N itself?

In this case N is not related to programming, but simply an integer, specifically an integer larger than 3.
• : How can I construct a smallest possible circle which contains N
: specified points? I don't speak about cyclic polygons and points ON
: the circle, I need a routine for all polygons and the points can be
: INSIDE the circle.
: I can do a circumscribed circle for a triangle but I don't know how
: to solve this one problem :-(

This is way overdue, but Could you not just get the distance between the two farthest points, the find the center point of the two points and that would be your radius as well. That would encompass all the points inside of the circle I think.
Just a matter of looping through each point and comparing it's distance to the other points and updating a MaxDistance variable. Back to good 'ol pythagoras theorem, a
• : My current thought is to add together all the X coords and all the Y
: coord and find the average and that will give you a center point.
: Then the farthest point away will be the outside edge of the circle.
: This does ALWAYS encompass all points, but if the majority of the
: points are on one side, the circle will have wasted space. Getting
: closer I think

No, this method would produce much bigger circles than the minimal surrounding.
I even can't to find out how to do it with "paper geometry" without computer :-(
• : No, this method would produce much bigger circles than the minimal
: surrounding.
: I even can't to find out how to do it with "paper geometry" without
: computer :-(
:

I think I got it, but still trying to get it on computer. My thought is to take the distances of all lines, then take their center points. Now you can't just add all these together, but if you weight them, so that they are weighted based apon lengths I think that it should work out to the actual center point of the smallest possible circle (maybe?) Then you would just need to find the farthest point away from the center and create your circle.

It's dang close! I can see it. Right now It's just off center. I think I am forgetting to weight all the points.

Phat Nat
• I am not sure but I think I solved it on the paper.
Generaly two cases may occur: there can be two or three points on the circle. In some cases can be more points on the circle but it can be considered as special case of three points on the circle.
Algorithm:
1)find two points with largest distance (and name it A,B)
2)connect them with line and find center of this line (name it N)
3)check whether all other points have same or lower distance than A-N
4a)YES? We found the circle:
4b)NO?
5)find most outlying point from N. (name it C)
6)solve 3-point circle algorithm

Can anybody confirm this algorithm?
• Yes! It works.
Now would be interresting to make a modification where wouldn't be a points but circles with various radius.
• i am new to this forum, i was trying to solve this problem for a long period, now i got the result, its working now. thanks. Let i try this with my students also.
=========================================
Micky Brown
• Unfortunately this is not correct.
As you can see on the following figure, points A and D are with the largest distance, but point D is not on the circle.
There is an optimal algorithm by Grassmann and Rokne, check the "Graphic Gems II" book. You can also find an implementation in ActionScript [link=http://lab.polygonal.de/2007/02/17/bounding-circle-computation/]here[/link]
Cheers,
Vassil Iordanov
• SOLVED!
Try this source:

uses Graph,Crt;

type TBod = object
x,y:real;
end;

Tkruh = object(TBod)
r:real;
end;

const delta=0.0000001;
max_bod = 6;

{ specbody:array[0..max_bod] of TBod = ((x:408;y:313),
(x:406;y:215),
(x:311;y:151),
(x:225;y:309),
(x:330;y:245));}

var barva:byte;
body:array[0..max_bod] of TBod;

Function IsEqual(a,b:real):boolean;
begin
IsEqual:=(ab-delta);
end;

Function IsLessOrEqual(a,b:real):boolean;
begin
IsLessOrEqual:=(ab) then
if (a>c) then begin d:=a;end else
begin d:=c;a1:=a2;a2:=a3;end else
{b>=a}
if (b>c) then begin d:=b;a2:=a3;end else
begin d:=c;a1:=a2;a2:=a3;end;

t.x:=(a1.x+a2.x) / 2;
t.y:=(a1.y+a2.y) / 2;
t.r:=d / 2;
Exit;
end;
t.x := (D * E - B * F) / G;
t.y := (A * F - C * E) / G;
t.r := Vzdalenost(a1,t);
end;

Function MaxDistance(var a,b:longint):real;
{vrati maximalni vzdalenost mezi body v poli}
var i,j:longint;
k,max:real;
begin
max:=0;
for i:=0 to max_bod-1 do
for j:=i+1 to max_bod do
begin
k:=Vzdalenost(body[i],body[j]); {zmerim vzdalenost vsech bodu}
if k>max then
begin
max:=k;
a:=i;
b:=j;
end;
end;
MaxDistance:=max;
end;

Function MaxDistanceToPoint(p:Tbod):real;
{maximalni vzdalenost bodu v poli vhledem k P}
var v,w:real;
i:longint;
begin
w:=0;
for i:=0 to max_bod do
begin
v:=Vzdalenost(p,body[i]);
if v>w then w:=v;
end;
MaxDistanceToPoint:=w;
end;

Procedure ZjistiObklopujiciKruznici(var z:Tkruh);
{sestroji nejmensi obklopujici kruznici}
var s:tbod;
a,b,c:longint;
v,w:real;
h:TKruh;

begin
v:=MaxDistance(a,b); {zjisti nejdelsi vzdalenost mezi body a take}
{o ktere body jde}
s.x:=(body[a].x+body[b].x) / 2;
s.y:=(body[a].y+body[b].y) / 2; {na teto usecce udela stred S}

w:=MaxDistanceToPoint(s);
{a zjisti, jestli je nejaky bod dal od S nez krajni body usecky}

if IsLessOrEqual(w,v/2) then
{kdyz ne, tak vime, ze je kruznice tvorena dvema body}
begin
barva:=5;
z.x:=s.x;
z.y:=s.y;
z.r:=v/2;
end
else begin
{existuje bod, ktery je dal od S nez krajni body usecky.
{V tom pripade bude kruznice definovana tremi body, pricemz ale mezi nimi
nemusi nutne byt body A a B. Je tedy treba proscanovat vsechny myslitelne
trojuhelniky, ktere je mozno z definovanych bodu sestavit a hledat jim
opsane kruznice}
z.r:=0;
for a:=0 to max_bod-2 do
for b:=a+1 to max_bod-1 do
for c:=b+1 to max_bod do
begin
{tento trojnasobny cyklus proscanuje vsechny myslitelne trojuhelniky}
Kruznice3(body[a],body[b],body[c],h);
s.x:=h.x;
s.y:=h.y;

w:=MaxDistanceToPoint(s);
if IsLessOrEqual(w,h.r) then
if (z.r=0) or (h.r<z.r) then z:=h;
end;
end;
end;

Procedure NakresliScenu(z:TKruh);
var a:byte;
begin
SetColor(4);
Circle(round(z.x),round(z.y),round(z.r));
for a:=0 to max_bod do
PutPixel(round(body[a].x),round(body[a].y),14);
end;

{-----------------------------------------------------------------}

var gd,gm:integer;
z:Tkruh;
a:longint;
r1,r2:real;
c:char;

begin
randomize;
gd:=vga;gm:=vgahi;InitGraph(gd,gm,'');
OutText('Pro ukonceni zmackni ESC, pro dalsi sestavu jakoukoliv jinou klavesu');
SetFillStyle(0,0);

repeat
Bar(0,20,639,479);
for a:=0 to max_bod do
begin
r1:=random(200);
r2:=random(200);
body[a].x:=r1-100+320;
body[a].y:=r2-100+240;
end;

ZjistiObklopujiciKruznici(z);
NakresliScenu(z);

repeat until keypressed;