# Find the centre of a circle given two points lying on it and its radius

We have been given 2 points on a circle and its radius. Now I want to find out the centre point of such a circle. How can I code this efficiently without solving the quadratic equations?

• Wouldn't there be two possibilities? – Dennis Meng Jan 25 '14 at 20:26
• What have you tried? Why is solving quadratic equations a problem? What are the restritions here, e.g. runtime? – Raphael Jan 25 '14 at 21:54
• @DennisMeng Yes there will be 2 possibilities. – Nikunj Banka Jan 26 '14 at 5:16

$$INPUT \rightarrow P_1(x_1, y_1), P_2(x_2,y_2), r$$ $$d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$ $$h=\sqrt{r^2-(\frac{d}2)^2}$$ $$\alpha=arcsin(\frac{y_1-y_2}{d})$$ $$x_c=\frac{x_1+x_2}2+h sin(\alpha)$$ $$y_c=\frac{y_1+y_2}2+h cos(\alpha)$$

• That's a bunch of formulae, not an answer. Where do they come from? Why are they correct? How can they be translated into an algorithm? Which runtime will it have? – Raphael Jan 25 '14 at 23:02
• @Raphael, I added an image which describe how it works. What do you mean by runtime, please? – Yasser Zamani Jan 25 '14 at 23:36
• @Raphael This is quite basic geometry; being given the solution is more than enough in my opinion. – G. Bach Jan 25 '14 at 23:56
• @G.Bach: If the point is geometry, it is offtopic here and should be on Mathematics. The OP, however, asks "How can I code this efficiently without solving the quadratic equations?". Other than that, usual standards apply, and just giving the solution is (almost) never enough to constitute an SE-good answer. – Raphael Jan 26 '14 at 1:21 \begin{align*} \mathbf{v} &= (\mathbf{p_2} - \mathbf{p_1}) = \begin{pmatrix} v_x \\ v_y \end{pmatrix} \\ h &= \sqrt{r^2 - \frac{\lvert \mathbf{v} \rvert^2}{4}} \\ \mathbf{u_h} &= \frac{1}{\lvert \mathbf{v} \rvert} \begin{pmatrix} v_y \\ -v_x \end{pmatrix} \\ c_{1,2} &= \mathbf{p_1} + \frac{1}{2} \mathbf{v} \pm h\mathbf{u_h}\\ \end{align*}

The algorithm is obvious, it's complexity should be $O(n^2)$.

• What does $n$ stand for? – Juho Jan 26 '14 at 13:25
• Any algorithm will take constant time. Without detailed costs forthe various operations the"cheapest algorithms" makes no sense. – vonbrand Jan 27 '14 at 1:22