#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

#### Categories

Welcome to the new platform of Programmers Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use it's exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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

Posts: 9Member
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 :-(
· ·

• Posts: 77Member
: 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?
· ·
• Posts: 6,349Member
: : 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.
· ·
• Posts: 757Member
: 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
· ·
• Posts: 9Member
: 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 :-(
· ·
• Posts: 757Member
: 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
· ·
• Posts: 9Member
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?
· ·
• Posts: 9Member
Yes! It works.
Now would be interresting to make a modification where wouldn't be a points but circles with various radius.
· ·
• Posts: 1Member
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
· ·
• Posts: 1Member
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
· ·
• Posts: 9Member
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;