0
$\begingroup$

I'm trying to solve the following problem algorithmically. It seems it's a bit too math-y for StackOverflow.

Suppose we're given the coordinates of the centers of three circles ($A,B$ and $C$), as well as the radius of each circle. Now, suppose we iteratively add some small amount to the radius of each circle, until all three circles intersect at some point, $[x_i,y_i]$. How would I go about determining their point of intersection? Now, of course, in practice I can only increase the radius by some discrete amount (maybe $0.01$ units), so I'll have to take into account that they may never actually intersect, rather I'll probably want to determine when they're within some threshold (unless there's a better way to accomplish this entirely). With each iteration, I'll also have to be able to determine whether such an intersection even exists.

The best idea I can think of is to somehow compute every possible point along the circumference of each circle (in practice, a large discrete number, of course), and then check to see if there are three points within some threshold (i.e. there exists 3 points, one contributed by each circle, within some small threshold, maybe $0.01$ units).

Most important here is efficiency and ease of implementation.

NOTE: I should've added-- I'm aware of the solution involving finding the intersection of two hyperbolas. However, for this exercise, I'd like to avoid that particular solution.

$\endgroup$
  • $\begingroup$ This should be determinable as the intersection of two hyperbolas ... $\endgroup$ – Hagen von Eitzen Sep 23 '20 at 16:57
  • $\begingroup$ There may not be such a point. Suppose three circles of the same tiny radius (so they are disjoint at the start), two centers close together, one far away. Then as radii increase uniformly the two intersections of the first pair of circles travel both ways along the perpendicular bisector of the segment joining their centers. There's little reason to expect that the third circle will ever coincide with one of those points. $\endgroup$ – Ethan Bolker Sep 23 '20 at 18:26
  • $\begingroup$ @EthanBolker Oh, sorry, I should also have mentioned that the circles are guaranteed to intersect at some point. We simply do not know what that point is. $\endgroup$ – K_M Sep 23 '20 at 19:37
0
$\begingroup$

Let the centres be $(x_A,y_A)$, $(x_B,y_B)$, $(x_C,y_C)$, and the initial radii $r_A$, $r_B$, $r_C$. You want to find $(x,y)$ and $r$ such that $$\tag1(x-x_A)^2+(y-y_A)^2=(r_A+r)^2$$ $$\tag2(x-x_B)^2+(y-y_B)^2=(r_B+r)^2$$ $$\tag3(x-x_C)^2+(y-y_C)^2=(r_C+r)^2$$ Expanding and subtracting $(1)-(2)$ and $(1)-(3)$, we have $$\tag4-2x(x_A-x_B)+(x_A^2-x_B^2)-2y(y_A-y_B)+(y_A^2-y_B^2)\\=r_A^2-r_B^2+3(r_A-r_B)r $$ $$\tag5-2x(x_A-x_C)+(x_A^2-x_C^2)-2y(y_A-y_C)+(y_A^2-y_C^2)\\=r_A^2-r_C^2+3(r_A-r_C)r $$ so two linear equations in the unknowns $x,y,r$. Unless we are unlucky, these determine a line, i.e., something of the form $$\tag6 x=x_0+ar, y=y_0+br.$$ Substituting this into $(1)$, say, you obtain (in general) a quadratic equation in $r$ with hopefully two solutions, and use $(6)$ accordingly to find $(x,y)$.

$\endgroup$

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.