Perfect circle.

[BlindSniper]

Hi all,
I'm writing some code and I need to determine if an array of points is in the shape of a perfect circle( not only the outline all points inside) and this code needs to be rather quick. One method I thought of is I take the average and the mean of all the points. If it is a perfect circle then these two should be equal(or very close to equal), but if it is a malformed circle then they would differ. The problem that i'm having is that my method seems very bad and I think the average and mean would be the same for any shape that is x and y symmetric.

Any ideas ?

[jemidiah]

I'm not sure what distinction you're drawing between "average" and "mean"; they're usually synonyms.

The first solution that comes to my mind is to first find the "center" by computing the average of all the points and then to compute the distance from the center to each point. Round these to the nearest pixel, and make a histogram. You can divide the frequency by the radius to make the result a flat line (with a particular height; 2pi something or other) with an eventual sharp drop off to 0 if and only if the points are nearly circular. Detecting a flat or nearly flat line shouldn't be too hard here.

Another approach comes to mind. Compute the first N moments. They should behave very well for circles (I won't do the calculations to figure out their forms) and misbehave for other shapes. This could take a lot of processing time so I haven't considered it thoroughly.

Another interesting approach comes to mind though it's also processing intensive. Compute the median of the x and y values (oh, is that what you mean by "mean"?). That'll give you the center but it can be fooled easily by symmetry. To get around that, cut up the plane into n pieces with angles 2pi/n centered on your median point and compute the number of points inside each region. If they're significantly unequal, no good, it's not a circle. Repeat for numerous values of n. Ideally the offset of the angles would be varied along with their size.

Ah, a very interesting solution came to mind, though it requires edge detection. If you can manage edge detection, you can verify the amount of equality in the isoperimetric inequality, which tells you how close to circular your shape is (non-circles have a higher perimeter to area ratio than circles).

[Lenggries]

I think you guys may be overthinking the problem, or else I'm misinterpreting the OP. It seems the definition of 'perfect circle' requires the array contain all points within the boundary of the circle. In order for this to even be possible, me must be talking about a discrete plane. I will assume we are talking about a Cartesian plane (x and y axes). In that case, for each possible radius (up to some maximum), we can precalculate the number of points contained within that circle. Thus, we can simply examine the size of the array and do a lookup comparison to eliminate many arrays. If the number matches, then we already know what radius we're looking for and can work from there. Off the top of my head, I'd say we could figure out the x and y maxes and mins to identify the origin and then and then see if every possible point within the circle of that location and radius is contained within the array. It should be O(n), where n is the size of the array.

[BlindSniper]

Yes, I'm working on a Cartesian plane and by mean I ment median. I thought mean was the correct translation. I'm going to be working on this again later in the day and I will tell you if I need more help or if I find a solution I will post it.

[jemidiah]

@Lengries: Maybe. I was thinking the problem was a little fuzzier than that and "perfect circle" wasn't really what was meant (since it's kind of an easy problem otherwise--compute the average or median to get the center, compute the expected radius using the number of points, compare).