2

My requirement is to find the point closest to three circles. So lets say the three circles are $C_1$, $C_2$, $C_3$. I want to find the point in the space such that the SUM of its distance from $C_1$, $C_2$ and $C_3$ is MINIMUM.

The distance of a given point from a circle is the distance of the given point from the point that lies on the circle and is intersection of the circle with the line joining the given point with the center of the circle.

I'm using the following approach which has been prescribed in another thread in Math SE: Closest point to 3 (or more) circles

Let $(x,y)$ be the BEST point and $(x_i,y_i)$ be the centre of circles; let $r_i$ be the radius of circles. Probably the easiest expression to minimize is the sum of the squares of the errors,

$$E(x,y)=\sum\left[(x−x_i)^2+(y−y_i)^2−r_i^2\right]^2$$

solve the system of equations

$$ \frac{\partial E}{\partial x}(x,y)=0, \\ \frac{\partial E}{\partial y}(x,y)=0 $$

This is where I get stuck. How to solve what I get after partial differentiation?I think its very complicated being degree $4$ in $x$, $y$ and multivariate polynomials. Can someone give an example of how to solve such equations manually (step by step)? Even if you could give pointers on how to handle this using sympy library of python, that'll be extremely helpful.

Community
  • 1
user3098199
  • 21

1 Answers1

0

You want to get rid of the out-most squared on your summands. To do this, run eight cases for positive or negative summands. Each of these cases corresponds to some combination of being inside or outside of the circles; make sure that the cases you're looking at are possible! (For example with disjoint circles, you cannot have a point inside both.) For each of these cases, if you get a negative $E(x,y)$, this means that you have chosen an incorrect region in that case, so throw it away. Over all your cases, look at the smallest non-negative number, and that corresponds to the point you're looking for.

T.J. Gaffney
  • 1,568
  • I'd like to know how to solve such equations. I assume what you say makes sense after the roots have been found. However, I am stuck at how to find roots. Any help would be great! – user3098199 Mar 13 '14 at 08:53