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?
$\begingroup$
$\endgroup$
3
asked Jan 25, 2014 at 20:05
-
4$\begingroup$ Wouldn't there be two possibilities? $\endgroup$– Dennis MengCommented Jan 25, 2014 at 20:26
-
$\begingroup$ What have you tried? Why is solving quadratic equations a problem? What are the restritions here, e.g. runtime? $\endgroup$– RaphaelCommented Jan 25, 2014 at 21:54
-
$\begingroup$ @DennisMeng Yes there will be 2 possibilities. $\endgroup$– Nikunj BankaCommented Jan 26, 2014 at 5:16
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
$$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)$$
-
$\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$– RaphaelCommented Jan 25, 2014 at 23:02
-
2$\begingroup$ @Raphael, I added an image which describe how it works. What do you mean by runtime, please? $\endgroup$ Commented Jan 25, 2014 at 23:36
-
2$\begingroup$ @Raphael This is quite basic geometry; being given the solution is more than enough in my opinion. $\endgroup$– G. BachCommented Jan 25, 2014 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$– RaphaelCommented Jan 26, 2014 at 1:21
$\begingroup$
$\endgroup$
2
\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)$.
-
2
-
$\begingroup$ Any algorithm will take constant time. Without detailed costs forthe various operations the"cheapest algorithms" makes no sense. $\endgroup$– vonbrandCommented Jan 27, 2014 at 1:22