2
$\begingroup$

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?

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

$$INPUT \rightarrow P_1(x_1, y_1), P_2(x_2,y_2), r$$ How it works $$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)$$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Raphael Jan 25 '14 at 23:02
  • 2
    $\begingroup$ @Raphael, I added an image which describe how it works. What do you mean by runtime, please? $\endgroup$ – Yasser Zamani Jan 25 '14 at 23:36
  • 2
    $\begingroup$ @Raphael This is quite basic geometry; being given the solution is more than enough in my opinion. $\endgroup$ – G. Bach Jan 25 '14 at 23:56
  • $\begingroup$ @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. $\endgroup$ – Raphael Jan 26 '14 at 1:21
-1
$\begingroup$

\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)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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