1
$\begingroup$

A similar question has been asked before on this site but that was of getting equation of circle using 3 points.

I want my center to be more accurate So my question is how can i get the center of the circle using 30 coordinates on its circumference. Please help me to know how can i get it.

$\endgroup$

closed as unclear what you're asking by Ali Caglayan, Henrik, Hurkyl, colormegone, Zain Patel Jul 10 '16 at 0:49

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 16
    $\begingroup$ You should explain more about why a "more accurate" center is important. In particular do you know something about errors in the points, how these errors are distributed? If every point were perfectly accurate, then any three would give exactly the same center, but when errors appear a number of schemes (best least squares, best min-max, etc.) could be proposed. The choice of scheme likely depends on your purpose and the distribution of errors. $\endgroup$ – hardmath Jul 9 '16 at 13:52
  • 3
    $\begingroup$ You only need 3 points. Ditch 27 of them unless the points aren't exactly on the circumference in which case you may require a method of approximation. $\endgroup$ – Pixel Jul 9 '16 at 15:46
  • $\begingroup$ A circle is uniquely determined by three points. Given 30 points you can have $\binom{30}{3}$ different circles. You really need to say something about why you expect them to be on the same circle, and why you don't just use three of them. $\endgroup$ – Henrik Jul 9 '16 at 17:47
  • $\begingroup$ @Henrik Maybe what the OP looking for is:- among these $\binom{30}{3}$ circles, which one best-fits these 30 points. $\endgroup$ – Mick Jul 9 '16 at 19:23
  • 3
    $\begingroup$ There are a number of questions we could invent and speculate the OP is actually asking -- it would be better to have the OP to fill in the missing context. Based on one of the comments, it sounds like the OP actually has a very specific problem, and could get a very specific answer if the OP actually filled in the details of the question! $\endgroup$ – Hurkyl Jul 9 '16 at 20:10
9
$\begingroup$

A circle centered at $(h,k)$ of radius $r$ has equation $(x-h)^2+(y-k)^2=r^2.$ So you can expand this equation and use your thirty points along with least squares to do it.

$\endgroup$
  • 3
    $\begingroup$ I think it's easier to do this with $Dx+Ey+F=x^2+y^2$ $\endgroup$ – Noble Mushtak Jul 9 '16 at 13:42
  • $\begingroup$ @NobleMushtak Yes, that way one has only three undetermined coefficients and it may be easier to set up for least squares. Using the expanded form I suggested there are still three unknown coefficents but after multiplying out a term $h^2+k^2-r^2$ remains, which (to me) is not so direct. $\endgroup$ – coffeemath Jul 9 '16 at 20:50
  • $\begingroup$ Least-squares may not be ideal because there is no 1:1 function y = f(x). There are published algorithms for fitting a conic section. Personally I like the RANSAC-based ellipse fits (which covers a circle, of course). Or you could convert to $ r-\theta$ space. $\endgroup$ – Carl Witthoft Jul 9 '16 at 22:50
7
$\begingroup$

The problem is much more complex since it depends how you express the objective function (in other words, what kind of distances to the circle you want to consider).

Probably the simplest (method 1) would be what Noble Mushtak commented that is to say to find the best $D,E,F$ parameters in the model $$Dx_i+Ey_i+F=x_i^2+y_i^2$$ Using matrices, the solution is almost immediate.

Another simple and explicit method I remember is given here.

More rigorous (method 2) will be to minimize $$F(a,b,r)=\sum_{i=1}^n \left( (x_i-a)^2+(y_i-b)^2-r^2\right)^2$$ The partial derivatives are simple to write but they lead to a nonlinear system of equations. However, you could use the first method to get good estimates of the solution and start a Newton-Raphson procedure to polish the solution.

Still more rigorous (method 3) would be to consider $$d_i=\sqrt{(x_i-a)^2 + (y_i-b)^2} - r$$ which represents the distance from the perimeter to point $(x_i,y_i)$ and to minimize $$G(a,b,r)=\sum_{i=1}^n d_i^2$$ Same problem as before and same solution.

Since the first method gives reasonable estimates, I suppose that the final solution could be obtained using Excel solver as a black box tool.

You could also use the method published here by Jean Jacquelin (he is a MSE user). The book is in French but you will not have any problem. Have a look at pages $12-13$. It is a very simple method and example is given.

Edit

For illustration purposes, I used the following data points $$\left( \begin{array}{cc} 2.5 & 6.5 \\ 2.0 & 8.5 \\ 4.0 & 11.5 \\ 7.5 & 11.0 \\ 9.0 & 9.0 \\ 8.0 & 6.5 \end{array} \right)$$

Using method 1, we find $D=10.81773$, $E=16.84893$, $F=-88.579820$ which correspond to $a=5.40887$, $b=8.42447$, $r=3.41287$.

Using method 2, we get the same results (this is normal).

Using method 3, we obtain $a=5.39989$, $b=8.42763$, $r=3.41031$.

$\endgroup$
5
$\begingroup$

A circle is not made more accurate by adding more points. 3 non-colinear points fully defines the equation for a circle. Your remaining 27 points are either perfectly on this circle, adding nothing, or they are not perfectly on the circle, in which case there is no equation for a circle through all 30 points.

It strikes me that you are not looking for the equation for a circle that goes through those 30 points, but the best fit for a circle which almost goes through each point. This is a fitting process, not a simple analytic geometry problem.

For a best fit, you have to define what "best fit" means to you. Often it means minimizing the sum of the squares of the errors. Claude Leibovici's answer does a good job of going down that path.

$\endgroup$
3
$\begingroup$

If all of the points lie on a common circle, then take the first three points and then find the circle that intersects those three points. Since all of the points lie on the same circle, all of the points must lie on the same circle as the first three points, so the circle of the first three points is the same as the circle of the whole set.

$\endgroup$
  • $\begingroup$ I already did that..... but as i was processing an image i found that the image was somewhat skewed. So that was giving some error in finding the center. By the way thanks $\endgroup$ – Utkarsh Dixit Jul 9 '16 at 14:25
  • 1
    $\begingroup$ @Hudixt The simplest and messiest way then is to just take random sets of 3 points and average the centers of the circle based on those sets of points. $\endgroup$ – bjb568 Jul 9 '16 at 16:05
  • $\begingroup$ Let's move this discussion to chat. $\endgroup$ – bjb568 Jul 9 '16 at 16:10
1
$\begingroup$

Pixels in an image are never "accurate" so 3 are insufficient. The circle Hough Transform (CHT) is used for detecting circular objects (and other shapes). https://en.wikipedia.org/wiki/Circle_Hough_Transform It is computationally complex (slow!) and works by transforming the image into 3d "parameter space" where the axes are the possible circle centres (a, b) and the circle radii R. Other useful links are a 2005 lecture: https://www.cis.rit.edu/class/simg782/lectures/lecture_10/lec782_05_10.pdf and the openCV documentation.

$\endgroup$
0
$\begingroup$

Hint:

Pick up arbitrary two point, write down the equation of perpendicular line which passes through the midpoint of these two point. Denote the equation for the line as $E1$.

Pick up different arbitrary two point, write down the equation of perpendicular line which passes through the midpoint of these two point. Denote the equation for the line as $E2$.

Set $E1$ and $E2$ into a system of equation, solve it (i.e. find the intersection point of line $E1$ and line $E2$). The solution with respect to $x$ and $y$ is the coordinate of center of the circle.

EDIT: notice that if $E1$ and $E2$ parallel, then $E1$ and $E2$ has numerous solutions.

When use other two point, check whether line about these point is parallel to the one about first chosen points.

$\endgroup$
  • $\begingroup$ You should also guarantee that you don't end up with the same line when you choose the other two points. A simple trick would be choosing two points $A$ and $B$, take that line you mentioned, and then take another point $C\neq A,B$ and take the line perpendicular to $AC$ and passing through their midpoints. It also explains why three non-linear points give a unique circle. $\endgroup$ – Levent Jul 9 '16 at 15:11
  • $\begingroup$ That's why the word "different" there. The problem of my solution is that the coefficient matrix of $E1$ and $E2$ doesn't have full rank. $\endgroup$ – Zack Ni Jul 10 '16 at 0:32
0
$\begingroup$

Would this work? For each pair of points $P_i, P_j$ construct the bisector line $L_{ij}$; the point that minimizes the sum of squared distances from $L_{ij}$ is a candidate centre for the circle. The setup is quadratic in number of points (unless you know the sequence of the points along the circumference, in which case it's reasonable to use only N-1 lines), but the solution is trivial, equivalent to finding the apex of an elliptic paraboloid.

I have used the method given here: http://www.dtcenter.org/met/users/docs/write_ups/circle_fit.pdf

I have not got around to reading this: http://www.spaceroots.org/documents/circle/circle-fitting.pdf

Afterthought: If the input is noisy or quantized, it's likely best not to use (only) bisectors of adjacent pairs; better to pair each point with the one most distant.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.