#1
  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. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    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!
  4. #3
  5. 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.
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,377
    Rep Power
    1871
    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
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    186
    Rep Power
    82
    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 08:53 AM.

IMN logo majestic logo threadwatch logo seochat tools logo