Geek Answers Handbook

What is the best way to determine the position and radius of a circle (or Oval) so that it best matches all the points that I give

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

I assume that after I find the right center, the radius will be equal to the distance of a more distant point, but how can I find the center?

Any algorithm / pseudo code would be really helpful.

+4
source share
4 answers

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

+3
source

You can reduce the problem by finding the "widest" axis of your point cloud. This will be the diameter of your smallest circle. Any smaller circle could not enclose the extreme points defining this diameter.

An ineffective algorithm for this starts with a loop at angles ɵ from 0 to 45 degrees. For each angle ɵ, transform the coordinates of each point by rotating the coordinate system by ɵ. Then just find max(x)-min(x) and max(y)-min(y) to find the maximum degree for this rotation. Continue to find the maximum degree for all turns.

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

To adapt this code to your specific 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;

Undoubtedly, there is a more effective approach (for example: first find a convex hull, and then consider only those points that define the hull), but this may be sufficient if the number of points is not astronomical.

0
source

Just take the average of each component of each point vector as your center, so the vector is towards your center (average_of_all_the_x, average_of_all_the_y), then, as you say, set the circle as passing through the farthest point.

-1
source

Ty for answers the way I did it.

 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); }
-1
source

More articles:


All Articles