My solution is based on the fact that in 2-D if you know the center of the circle then all points belonging to the circle will be in equal distance from it. So, the algorithm:

1. Select 4 points at random (let them be A,B,C,D) and estimate arcs AB and CD.

2. Compute the line that passes from the middle of AB and is perpendicular to it, and the same for CD (let them be lines L1 and L2)

3. Estimate the point that lines L1 and L2 intersect. (let this be point O). If the 4 points belonged initially to the same circle then O will be the circle center.

4. If it is the circle center, since your data is 50% of all the points then the 50% of all points will have almost equal distance from O. So, estimate the distance of your point set from O and classify O either to be a circle center or not, depending on if the distance distribution has a major peak that corresponds to O.

5. Continue until you find the real circle center. Then, the circle arc consists from all points that have almost equal distance from O.

Since 1/2 of your points belong to the center and you select at each step 4 points, this algorithm is expected to need 16 iterations, and at each iteration the computational cost is linear.

Ok, I am coming back because my initial answer was a bit sloppy. More specifically, before executing the algorithm you must know that the 4 points that you selected lie in the same plane.

I remind you that if 4 3-D points P1(x1,y1,z1), P2(x2,y2,z2), P3(x3,y3,z3), P4(x4,y4,z4) lie in the same plane then the matrix:

|x1 y1 z1 1|

|x2 y2 z2 1|

|x3 y3 z3 1|

|x4 y4 z4 1|

has zero determinant.

So, the algorithm becomes:

1. Select randomly a large number of sets of 4-points and estimate the above determinant. Sort the 4-points sets based on this determinant by a ascending order.

2. Initialize, i=1

3. While you haven't found the circle

A.Take the i-th set of points.

B. Estimate the candidate center of the circle O' by using this 4 points to "do this":

http://www.mathopenref.com/constcirclecenter.html

C. Estimate the histogram of all distances between O' and the complete set of data-points.

D. Estimate the mean distance D' between O' and the 4 points

E. If the above histogram have a major peak in D' then O' is the center of the circle, the plane that the 4 points define is the plane of the circle, D' is the radius of the circle. Else, i=i+1.

Still, the mean computational complexity of the algorithm is linear.

Panagiotis,

Thank you for your detailed answer! It is much appreciated. I will try to implement this with my data set and see how easily it computes.

Thanks again.

Sean

Wai-keung,

Thanks for your suggestion. I have used the Hough transform to detect such patterns in 2D, but in this case I am really unclear as to how to apply the method to 3D data. Can you suggest any references that could provide some guidance?

Sean

Thanks for the suggestion, Wai-keung. I will contemplate the math and try it out!

Try to use geometric fit, i.e. theta= argmin d_i^2, d_i=EculdDist(P_i,the circle) , but here you need to find d_i between P_i=(X_i,Y_i,Z_i). Here you can assume that the true points lie on certain circular arc but because of noise, the true points are deviated from the arc

Hough transform is not without problems with occlusions. For an alternative, see:

Vivian Cho, Wm. Douglas Withers: Circle Location by Moments. ICISP 2010: 94-102

Is in 2D, but moments should also work in higher dimensions

Matthias, this is a really interesting find. Thanks for posting!

That is a good point, James. I've tried to clean/truncate a data set so that it can be posted, which I have attached. What I would like to do is gather the data points that form the large circular arc into one group. As you can see, there is quite a bit of extraneous noise including noise that is circular and linear. After doing a bit of reading, I am not sure that Hough transforms or moment-based methods will work since I do not have weighted values for my 'voxels'. I only have points which exist at discrete coordinate locations in the 3D space. Would a clustering method work here?

Thanks, James. Will contemplate this.