January 24th, 2013, 01:55 PM

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;
}
}
January 24th, 2013, 10:42 PM

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.
[code]
Code tags[/code] are essential for python code and Makefiles!
January 24th, 2013, 11:45 PM

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.
January 25th, 2013, 12:33 AM

January 25th, 2013, 08:36 AM

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
[modedit]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 08:53 AM.