### Thread: Finding A Circle in A Set of N Points C++

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2013
Posts
1
Rep Power
0

#### Finding A Circle in A Set of N Points C++

I'm a beginner at C++ and I was given this problem to do for my end of semester project. The question states:
"Generate by random, a set of n points in a 2D Cartesian Coordinates System. Find a circle enveloping all of the points which area is the smallest. Use functions for reading, printing appropriate data. Use local variables."
I NEED HELP. This is all I have done so far:

#include <stdio.h>
#include <stdlib.h>
#include <iostream>

#define n 100
#define range_y 100
#define range_x 100

struct point
{
int x;
int y;
};

void main()
{
point * table;
table=(point *)(malloc(n*sizeof(point)));
for (int i=0;i<n;i++)
{
table[i].x=rand()%range_y+1;
table[i].y=rand()%range_x+1;
}
}
2. I'd plunge right in and apply a convex hull algorithm to reduce the size of the problem. Next I'd draw some pictures and research the geometry to see if there's an analytical technique. Otherwise you'll have to use numerical methods. Now, if I were clever I'd think about the problem before I wrote code. I mean, the answer couldn't be something stupidly simple like "a diameter of the enclosing circle is defined by the two points with greatest separation". Anyway, I doubt that's correct, but if it were it would be a shame to have bothered with convex hull.
3. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1313
Originally Posted by b49P23TIvg
I mean, the answer couldn't be something stupidly simple like "a diameter of the enclosing circle is defined by the two points with greatest separation". Anyway, I doubt that's correct, but if it were it would be a shame to have bothered with convex hull.
It's not that simple: consider the three vertices of an equilateral triangle, along with a fourth point opposite one of the vertices just barely inside the circumcircle of the triangle. Anyway, this is a pretty old and solved problem. I believe Emo Welzl is the name usually associated to this.
4. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2012
Posts
187
Rep Power
83
Originally Posted by pacosarae
I believe Emo Welzl is the name usually associated to this.
Emo's algorithm is sometimes found in 3D game engines. But anyway, here is a link to a tutorial and sample Java code

[mod-edit]Deleted pacosarae's post due to his image link drop attempt and delinked his image on your reply.[/edit]
Last edited by Scorpions4ever; January 25th, 2013 at 09:53 AM.