What is the best way to determine a circle's (or Oval shape) position and radius so that can best fit all the points i give

Question

I have many points . What is the best way to find the center and the radius of the minimum radius circle that contains all the points given.

I guess that after i find the proper center the radius will be equal to the distance of the more far away point but how can i find the center?

Any algorithm/ pseudo code would be really useful.

Answer 1

CGAL provides such an algorithm. See here, but this is in C++. If you need it in java, you can write a simple wrapper using SWIG for example.

Answer 2

You can reduce the problem to finding the "widest" axis of your cloud of points. This will be a diameter of your smallest circle. Any smaller circle couldn't possibly enclose the extremal points that define this diameter.

An inefficient algorithm to accomplish this begins by looping over angles ɵ from 0 to 45 degrees. For each angle ɵ, transform the coordinates of every point by rotating the coordinate system by ɵ. Then simply find max(x)-min(x) and max(y)-min(y) to find the maximum extent for this rotation. Continue to find the maximum extent for all rotations.

Here is a C program which implements this simple algorithm, returning the length of the minimum diameter:

• problem statement
• solution in C

To adapt this code to your particular problem, add this code at the end:

 /* parameters of smallest circle enclosing the points */
 double center_x = (x[max_i]+x[min_i])/2;
 double center_y = (y[max_i]+y[min_i])/2;
 double radius = sqrt( (x[max_i]-x[min_i])*(x[max_i]-x[min_i]) +
                       (y[max_i]-y[min_i])*(y[max_i]-y[min_i])))/2;

There is doubtlessly a more efficient approach (for instance: first find the convex hull, and then consider only those points defining the hull), but this might suffice if the number of points is not astronomical.

Answer 3

Just take the mean of each component of each point vector as your centre, so the vector to your centre is (average_of_all_the_x, average_of_all_the_y), then, as you say, set the circumference as going through the most distant point.

Answer 4

Ty for the answers the way i did it was like that.

float minX = Float.MAX_VALUE;
            float maxX = Float.MIN_VALUE;
            float minY = Float.MAX_VALUE;
            float maxY = Float.MIN_VALUE;

            for (int i = 0; i < item.slaves.size(); i++) {
                OverlayItemExtended slaveItem = item.slaves.get(i);
                GeoPoint slavePoint = slaveItem.getPoint();
                Point slavePtScreenCoord = new Point();

                mapView.getProjection()
                    .toPixels(slavePoint, slavePtScreenCoord);

                float x = slavePtScreenCoord.x;
                float y = slavePtScreenCoord.y;

                maxX = Math.max(x, maxX);
                minX = Math.min(x, minX);
                maxY = Math.max(y, maxY);
                minY = Math.min(y, minY);

            }
            float centerX = (maxX + minX) / 2;
            float centerY = (maxY + minY) / 2;
            double distance = findDistance(minX, minY, maxX, maxY);         
            Paint linePaint = new Paint();
            linePaint.setColor(android.graphics.Color.RED);
            linePaint.setStyle(Paint.Style.FILL);
            linePaint.setAlpha(35);

            canvas.drawCircle(centerX, centerY, (float) (distance / 2) + 10,
                    linePaint);
}