Polygon approximation with a circle

Question

Well, approximating a circle with a polygon and the story of Pythagoras, it can be well known. But what about the other way?

I have several polygons that should actually be circles. However, due to measurement errors, they are not. So, I'm looking for a circle that best approximates a given polygon.

In the following figure, we see two different examples.

My first Ansatz was to find the maximum distance from the points to the center, as well as the minimum. The circle we are looking for may be somewhere in between.

Is there any algorithm for this problem?

Answer 1

I would use scipy to best put a circle in my glasses. You can get the starting point for the center and radius by simply calculating the center of mass. This works well if the points are evenly distributed in a circle. If this is not the case in the example below, it is still better than nothing!

The fit function is simple because the circle is simple. You just need to find the radial distance from your circle to your points, since the tangent (radial) surface will always be the best fit.

 import numpy as np from scipy.spatial.distance import cdist from scipy.optimize import fmin import scipy # Draw a fuzzy circle to test N = 15 THETA = np.random.random(15)*2*np.pi R = 1.5 + (.1*np.random.random(15) - .05) X = R*np.cos(THETA) + 5 Y = R*np.sin(THETA) - 2 # Choose the inital center of fit circle as the CM xm = X.mean() ym = Y.mean() # Choose the inital radius as the average distance to the CM cm = np.array([xm,ym]).reshape(1,2) rm = cdist(cm, np.array([X,Y]).T).mean() # Best fit a circle to these points def err((w,v,r)): pts = [np.linalg.norm([xw,yv])-r for x,y in zip(X,Y)] return (np.array(pts)**2).sum() xf,yf,rf = scipy.optimize.fmin(err,[xm,ym,rm]) # Viszualize the results import pylab as plt fig = plt.figure() ax = fig.add_subplot(1, 1, 1) # Show the inital guess circle circ = plt.Circle((xm, ym), radius=rm, color='y',lw=2,alpha=.5) ax.add_patch(circ) # Show the fit circle circ = plt.Circle((xf, yf), radius=rf, color='b',lw=2,alpha=.5) ax.add_patch(circ) plt.axis('equal') plt.scatter(X,Y) plt.show() 

Answer 2

Perhaps a simple algorithm will, firstly, calculate the centroid of the points (provided that they are usually roughly located on a regular basis). This is the center of the circle. After that, you can calculate the average radius of the points by specifying the radius of the circle.

A more complicated answer may be simple minimization, when you minimize the sum of the distances of the points to the edge of the circle (or the square of the distance).

Answer 3

There are two different O (n) algorithms for determining the smallest circle you draw, which includes a series of points on the wikipedia page with a small circle problem . From here it should be quite easy to draw a second circle, just determine the center of the circle that you found earlier, and find the point closest to this point. The radius of the second circle is as follows:

It may not be exactly what you want, but here's how I get started.

Answer 4

This problem may be the same as the problem with the smallest circle .

But since you have measurement errors that may include outliers, then RANSAC is a good option. See http://cs.gmu.edu/~kosecka/cs482/lect-fitting.pdf for a review of the method (as well as other basic methods), at http://www.asl.ethz.ch/education/master/ info-process-rob / Hough-Ransac.pdf has more information on setting up a circle.

Answer 5

It is very easy to find some approximation:

 def find_circle_deterministically(x,y): center = x.mean(), y.mean() radius = np.sqrt((x-center[0])**2 + (y-center[1])**2).mean() return center, radius 

Explanation: Put the center of the circle at the average of x and mean y of your points. Then, for each point, determine the distance to the center and take the average value at all points. This is your radius.

This full script:

 import numpy as np import matplotlib.pyplot as plt n_points = 10 radius = 4 noise_std = 0.3 angles = np.linspace(0,2*np.pi,n_points,False) x = np.cos(angles) * radius y = np.sin(angles) * radius x += np.random.normal(0,noise_std,x.shape) y += np.random.normal(0,noise_std,y.shape) plt.axes(aspect="equal") plt.plot(x,y,"bx") def find_circle_deterministically(x,y): center = x.mean(), y.mean() radius = np.sqrt((x-center[0])**2 + (y-center[1])**2).mean() return center, radius center, radius2 = find_circle_deterministically(x,y) angles2 = np.linspace(0,2*np.pi,100,True) x2 = center[0] + np.cos(angles2) * radius2 y2 = center[1] + np.sin(angles2) * radius2 plt.plot(x2,y2,"r-") plt.show() 

creates this graph:

This will work well as you have polygons with measurement errors. If your points are not evenly distributed in the corners [0,2pi[ , this will work poorly.

More generally, you can use optimization.