January 12th, 2013, 04:37 AM

How to find an ellipse from random points
Hello everyone!
I'm a new user here and I've started learning about C language just a few months ago, and I would like to ask for help in a task to solve.
I have to generate by random a set of n points in 2D cartesian coordinate sytem. Then to find an ellipse enveloping all of the points which area is the greatest.
So far I've got the steps but I have no idea how to do it.
1. Generate random n points.
2. I need to find an ellipse by;
a) finding the longest distance between two of these n points
b) calculating the half line for this segment
c) increasing points on this half line by one, as long as It doesn't give me an ellipse
3. calculate the area of this ellipse
I did step a) but I only stored these random points in an array.
Looks like this:
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
void main ()
{
srand( (unsigned) time( NULL ) );
int x_min = 0;
int x_max = 500;
int y_min = 0;
int y_max = 500;
int n;
printf("input a number of points:\n");
scanf("%d", &n);
int i, j;
int tab[5][2];
for (int i=0; i<5; ++i)
for (int j=0; j<2; ++j)
/* tab[i][0] = rand()/RAND_MAX + rand()%x_max;
tab[i][1] = rand()/RAND_MAX + rand()%x_max;*/
tab [i] = rand()*(x_maxx_min) / RAND_MAX + x_min;
tab [j] = rand()*(y_maxy_min) / RAND_MAX + y_min;
for(i=0; i<5; ++i)
{
for (j=0; j<2; ++j)
{
printf("[%d][%d] = %d \n", i, j, tab[i][j]);
}
}
}
And now is the part when I have no clue to solve. Please. :)
January 13th, 2013, 05:00 AM

It sound like someone gave you the problem out of this article
http://www.cs.cornell.edu/cv/OtherPdf/Ellipse.pdf
There is a lot of detail in this but one section sound like the solution description you seem to have. I am not sure that your description is completely clear.
First of you said you wanted the elipse with the greatest area. That's trivial.
Create an elipses forumula the has humongous coefficients blindly making
All of them 10^googleplex.
My variant of the problem would go as follows.
I am assuming you want an elipse that just encloses the set of points.
The first step 2 a tries to find the major axis of the elipse by finding the point farthest apart in the data set. If you have 500 points then there would 500x500 comparisons to find the max.
Once you have that you use those points to create the minor axis. Initially it could be the same size as them major axis there assuring all the points would be inside. The elipse would be a circle. Call this the outerlimit.
Now find the innner limit.
Cut the minor axis in half. Create the elipse formula. Test all the point to see if they are all In the small elipse. If they are make this the new outer limit and cut in half the minor axis an repeat.
Eventually you will get a minor axis size where the points don't fit. At that time the tightest fit has to be in between the outer limt size and inner limit.
Cut the difference in half and narrow the bracket of inner and outer limit to some arbitrary small number.
Let me know if you stand my description.
January 13th, 2013, 05:24 AM

First of all, thank you for the response.
So I followed your steps, and I agree with them all, only the last sentence is not clear for me.
Once I have the tightest fit in between the outer and inner limit, why do I need to cut the difference in half? Or what Difference you meant?
Isn't the tightest fit is our greatest ellipse area in this case?
January 13th, 2013, 10:35 PM

Just before the last instruction the outer limit of the minor axis is as far away the widest part of the cloud of dots along the major axis. The inner limit of the minor axis is inside the could of dots. One is outside of the cloud and one is inside there for the real boundery has to be in between them. Cutting the minor axis in half and chosing a new outer or inner limit will eventually get your ellipes that just barely includes you set of points.
What follows is a example of the points on the minor axis.
Each line after the dots is an iteration of the code.
The out limit will be marked it an O and the inside limit an I.
Code:
. .. .... ...... ..... . . .
1 I O
2 I O
3 I O
4 I O
5 I O
6 I O
Line 1 set inner to half outer, I is not in the cloud.
Line 2 I new position cut in half, it in the cloud.
Line 3 & 4 cut O distance in half until it would in side the cloud.
Leave it outside. Line 5 , 6 move I until it just is out side the cloud and move it back. The edge is between I and O.
Last edited by admiraln; January 13th, 2013 at 10:55 PM.
Reason: Additional points
January 14th, 2013, 10:03 AM

all right, seems logical.
Could you tell me how should I program this, and with the steps maybe I could solve it.
For example, the beginning is done, to set n random points. Now is the next step...but using what? :)
For example;
use a for, than put inside another for, open a new function, create sy. etc.