Thread: C program array problem

I was asked to make a program: Generate by random a set of 2d coordinates. Find two different circles enveloping all of the points and connected to the set ( there are at least three points on the circle). Check which circle has a greater area. Use function for reading, printing appropriate data. Use local variables.

Code:

#include<stdio.h>
#include<math.h>
#include <stdlib.h>
#include<time.h>



int main(void)
{
 int nofpoints, i;
 double x_max, x_min, y_max, y_min, *tabx, *taby, *tabdistance, *r, *rsquared, sumofy, sumofx;
 printf("input the n\n");
 scanf("%d", &nofpoints);
 srand((unsigned)time(NULL));
 tabx = (double*)malloc(nofpoints*sizeof(double));
 taby = (double*)malloc(nofpoints*sizeof(double));


 tabdistance = (double*)malloc(nofpoints*sizeof(double));
 x_max = 5;
 x_min = 0;
 y_max = 5;
 y_min = 0;


 for (i = 0; i <= (nofpoints - 1); i++)
 {


  tabx[i] = rand() * (x_max - x_min) / (double)RAND_MAX + x_min;
  taby[i] = rand() * (y_max - y_min) / (double)RAND_MAX + y_min;
  printf("x%d=%lf\ny%d=%lf\n\n", i, tabx[i], i, taby[i]);
 }
 sumofx = 0;
 sumofy = 0;
 for (i = 0;i <= (nofpoints - 1);i++)
 {
  sumofx = sumofx + tabx[i];
  sumofy = sumofy + taby[i];
 }
 printf("sum of x=%lf\nsum of y=%lf", sumofx, sumofy);
 double averagex = (sumofx / nofpoints);
 double averagey = (sumofy / nofpoints);
 printf("coordinates of the center of mass\nx=%lf y=%lf\n", averagex, averagey);
 for (i = 0;i <= nofpoints;i++)
 {
  tabdistance[i] = sqrt((((tabx[i] - averagex)*(tabx[i] - averagex)) + ((taby[i] - averagey)*(taby[i] - averagey))));
  printf("distance=%lf\n", tabdistance[i]);
 }






 r = (double*)malloc(nofpoints*sizeof(double));
 rsquared = (double*)malloc(nofpoints*sizeof(double));


 for (int i = 0;i < nofpoints;i++)
 {
  r[i] = ((tabdistance[i]) / 2);
  rsquared[i] = (r[i] * r[i]);
  for (int s = 0;s < nofpoints;s++)
  {
   if (rsquared[i] > (((tabx[s]-averagex)*(tabx[s] - averagex)) + ((taby[s]-averagey)*(taby[s]-averagey))))
   {
    printf("x=%lf, y=%lf r=%lf\n", tabx[s], taby[s],r[i]);
   }
   if (rsquared[i] = (((tabx[s] - averagex)*(tabx[s] - averagex)) + ((taby[s] - averagey)*(taby[s] - averagey))))
    printf("xboundary=%lf, yboundary=%lf r=%lf\n", tabx[s], taby[s], r[i]);
  }
 }
}

i have a problem with the last few lines. I have all possible radii stored in an array and i have all the points ( y and x coordinates) stored in an array. I dont know how to write the code which will print out only the radii for which a circle envelopes all the points and at least 3 points are on the circle itself.

I don't understand what you're trying to do. Can you show or link to a picture of it?

My problem is not how to do this from a mathematical point of view..The conditions for the radius are that for certain x,y coordinates the r^2 >= (( x-a)^2)+((x-b)^2) where a and b are coordinates of the centre of the circle ( in my case determined by the centre of the mass of the points generated). I have all possible radii stored in an array and all x and y coordinates stored in an array. I need to write a code which will output only the radii which envelops all the points ( at least 3 points must lie on the circle itself). I thought about nesting a loop in a if statement condition but apparently it is not working. For all x and y points I need an r^2 >= (( x-a)^2)+((x-b)^2) where a and b are coordinates of the centre of the circle and I don't know how to write a code which will print on the screen only the radii suitable. The code that I have already written prints all the points bounded by a radius and I have to manually count weather all points are bounded by the certain radius or not. All I need is for the code to do this for me.

Originally Posted by Tadek Kaniewski

My problem is not how to do this from a mathematical point of view..

No, it is exactly your problem. Whoever guided you on your current path wasted your time; you're way off course.

You see, you were asked to find two circumscribed circles with at least three points on the circle, and rest of the points inside the circle.

Three points happen to be exactly the minimum number of points that suffice to define a circle (if the points are not collinear, i.e. on the same line). Because the order of those points do not matter, you should have considered each unique triplet in the point set; i.e. triple loop, with e.g. i0 = 0 .. N-3, i1 = i0+1 .. N-2, i2 = i1+1 .. N-1, where N is the number of points.

Each triplet is sufficient to specify the candidate circle. You use the well-known formula to find the center of the circumscribed circle, and then find the radius by checking the distance from the three points to that center. (They should be equal, but in real life will often differ a bit due to numerical error as expected for floating-point numbers.)

Whether there are points outside the candidate circle, is easily tested: just check if any point has distance squared larger than the circle radius squared. (Why squared? Simply because there is no need to calculate the square root. All distances are nonnegative, so squared distances compare the same order as the distances themselves do.)

Thus, the entire operation can be written as a simple function, with four nested loops. The three outermost iterate over the unique triplets, and the innermost checks whether there are any points outside the circle specified by that triplet. The function can return early, whenever it has found the second such circle. I would declare it as

Code:

typedef struct {
    double x;
    double y;
} point;

typedef struct {
    double x;
    double y;
    double r;
} circle;

size_t find_circumcircles(circle *const circles, const size_t num_circles,
                      const point *const points, const size_t num_points)
{
    /* return the number of circumcircles found, at most num_circles */
}

Clustering has nothing to do with the problem at hand here.

There is absolutely no reason to check for the center of mass, either. It has no relevance, because each triplet of points define the circle (they are on) exactly.

In fact, you most certainly do not have "all the possible radii" calculated either. There are up to N!/3!/(N-3)! unique circles defined by N points, and as many radii. (As N grows, this approaches N³/6.)

The main difficulty here is to use an epsilon in comparisons. Instead of assuming the three points have exactly the same (squared) distance to the center of the circle they define, you must allow a bit of numerical error, due to the limited precision when computing stuff with floating-point numbers. In particular, you must allow for some error when considering whether other points are inside, on, or outside the circle. Here, only the outside matters, so you should only reject points further than the circle radius plus some epsilon times the radius. The epsilon is then the acceptable relative error. Typical values for this epsilon depend on what precision is used to specify your input data, and how precise the mathematical operations used to operate on them are, but values from 0.0001 (1e-4) to 0.000000001 (1e-9) are common choices.

If you do not handle the numerical errors correctly, and ignore that epsilon stuff, then you'll notice that in some cases one or more of the points you used to define the circle are actually outside of it.