I have a list of points and would like to determine if they form a circle

Question

I'm using C#, I have a list of Vector points and would like to try and approximate how close they look like a circle.

Any ideas how to implement this or if someone else has?

Answer 1

1) Pick any three points from that list, find the center of their appropriate circle

We can do this, using triangle circumcircle construction method, you find the medians of all three sides (two are sufficient) and their intersection is the center of the circle. Something like this:

public PointF findCenter(PointF a, PointF b, PointF c)
{
    float k1 = (a.Y - b.Y) / (a.X - b.X) //Two-point slope equation
    float k2 = (a.Y - c.Y) / (a.X - c.X) //Same for the (A,C) pair
    PointF midAB = new PointF((a.X + b.X) / 2, (a.Y + b.Y) / 2) //Midpoint formula
    PointF midAC = new PointF((a.X + c.X) / 2, (a.Y + c.Y) / 2) //Same for the (A,C) pair
    k1 = -1*k1; //If two lines are perpendicular, then the product of their slopes is -1.
    k2 = -1*k2; //Same for the other slope
    float n1 = midAB.Y - k1*midAB.X; //Determining the n element
    float n2 = midAC.Y - k2*midAC.Y; //Same for (A,C) pair
    //Solve y1=y2 for y1=k1*x1 + n1 and y2=k2*x2 + n2
    float x = (n2-n1) / (k1-k2);
    float y = k1*x + n1;
    return new PointF(x,y);
}

2) Check if the other points are equivalently distanced from this center, if yes, you have a circle, if no, you don't.

P.S. I haven't tested the code, so be prepared to debug. Ask if you need anything else

Answer 2

Based on the "gestures" tag I guess you not only want to know how close are these points to the smallest-circle (search for "Smallest-circle problem"), but you have to be concerned also about their order and spread:

1. I would start with the distance from the smallest-circle. If they are too far, you're done, it's not a circle.
2. If they are close enough to your configured threshold, compute the angle between the vector defined by the circle center, first point and each other point (picture bellow)
3. Check that each angle is greater than the previous.
4. Check that difference between any two angles next to each other is not over some configured threshold.
5. Check that the last point is close enough to the first one.
6. You will probably think of some other checks eventually, so make it simple to extend.

Answer 3

Another possibility:

1. Find the centroid (http://en.wikipedia.org/wiki/Centroid#Of_a_finite_set_of_points) of the points
2. Determine the distance (radius) of each point from the location of the centroid
3. Calculate the distribution and determine if the points are within acceptable tolerances (e.g. standard deviation < ±0.05 × mean radius or something like that)

Without knowing more about the source of the points, it's hard to suggest the best solution.

These might be of use: http://link.springer.com/article/10.1007%2FBF02276879#page-1 and http://www.dtcenter.org/met/users/docs/write_ups/circle_fit.pdf. Those methods will give you the best fitting circle through the points, but you are still going to need to determine whether your data points are close enough for your purposes.

UPDATE: based on the 'gesture' tag, somebody has already implemented it: http://depts.washington.edu/aimgroup/proj/dollar/

Answer 4

Take any three points from your point set. If the points are co-linear then, your point set doesn't all lie on a circle. Find the circumcircle of the triangle. The diameter is given by: d = (a*b*c)/2*area. The center of the circle is the point of intersection of the perpendicular bisectors of the three sides.

Now for every remaining point in the point set, if the distance from the center is not equal to the radius then the points are not on a circle. You can speed up the calculations by comparing the square of the radius against the square of the distance between the given point and the center.