Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
January 24th, 2013, 02:55 PM
 penguin_swagga
Registered User

Join Date: Jan 2013
Posts: 1
Time spent in forums: 20 m 26 sec
Reputation 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
January 24th, 2013, 11:42 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,174
Time spent in forums: 1 Month 3 Weeks 2 Days 11 h 47 m 24 sec
Reputation Power: 455
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!

#3
January 25th, 2013, 12:45 AM
 Lux Perpetua
Contributing User

Join Date: Feb 2004
Location: San Francisco Bay
Posts: 1,939
Time spent in forums: 1 Month 1 Week 3 h 27 m 29 sec
Reputation Power: 1312
Quote:
 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
January 25th, 2013, 01:33 AM
 salem
Contributed User

Join Date: Jun 2005
Posts: 4,261
Time spent in forums: 2 Months 4 Weeks 1 Day 15 h 24 m
Reputation Power: 1827
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

#5
January 25th, 2013, 09:36 AM
 BobS0327
Contributing User

Join Date: Oct 2012
Posts: 160
Time spent in forums: 4 Days 7 h 53 m 33 sec
Reputation Power: 64
Quote:
 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

Last edited by Scorpions4ever : January 25th, 2013 at 09:53 AM.

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Finding A Circle in A Set of N Points C++