# Finding location of a point on 2D plane, given the distances to three other know points

I need to find location of the point $s_0$; the locations of other three points ($s_1$, $s_2$, $s_3$) are known. $d_i$ are known distances.

Given: $x_1$, $x_2$, $x_3$, $y_1$, $y_2$, $y_3$, $d_1$, $d_2$, $d_3$
To be found: $x_0$, $y_0$

This will be a physical system. $s_i$ will be fixed antennas and the distances $d_i$ will be read via proximity sensors. The aim will be to make $s_0$ find its own location. So, $s_0$ will always exist; there will always be a unique solution point $s_0:(x_0, y_0)$.

How do I solve this problem?

-
Are you assuming $s_0$ exists? –  David Mitra Jan 19 '12 at 14:27
@DavidMitra Yes, $s_0$ exists. Actually, this will be a physical system. $s_i$ will be fixed antennas and $d_i$ will be read via proximity sensors. So, $s_0$ will always exist. –  hkBattousai Jan 19 '12 at 15:58

The point $(x_0,y_0)$ is on three circles, with equations $$C_i(x,y)=0, \qquad i=1,2,3,$$ where $$C_i(x,y)=(x-x_i)^2+(y-y_i)^2-d_i^2.$$ For a point $(x,y)$ to be on the first two circles, we must have $C_1(x,y)=C_2(x,y)$. Expand and simplify. We get a linear equation.

Similarly, we have $C_2(x,y)=C_3(x,y)$. Expand and simplify. We get another linear equation.

We now have a system of two linear equations in two unknowns. Solve for $x$ and $y$.

Note that bad things can happen. If we put down points and distances "at random" it is quite likely that there will be no point $(x_0,y_0)$ that satisfies your conditions. In certain fairly rare cases, there may be more than one point that satisfies your conditions.

Details: The point $(x_0,y_0)$ is distance $d_1$ from $(x_1,y_1)$. So $(x_0,y_0)$ is on the circle with centre $(x_1,y_1)$ and radius $d_1$. This circle has equation $$(x-x_1)^2+(y-y_1)^2=d_1^2.$$ This equation expands to $$x^2+y^2-2x_1x-2y_1y +x_1^2+y_1^2-d_1^2=0.$$ Similarly, $(x_0,y_0)$ lies on the circle with equation $$x^2+y^2-2x_2x-2y_2y +x_2^2+y_2^2-d_2^2=0.$$ When we set the two left-hand sides equal to each other, the $x^2$ and $y^2$ terms cancel, and we arrive at the linear equation $$2(x_2-x_1)x +2(y_2-y_1)y +x_1^2-x_2^2+y_1^-y_2^2 -d_1^2+d_2^2=0.$$ This is a linear equation in $x$ and $y$. When the two circles intersect in two points, it is the equation of the line through these two points.

In the same, we obtain a second linear equation in $x$ and $y$, that is, the equation of (we hope) another line. Then $(x_0,y_0)$ lies on both lines, so can be easily found.

It is possible that the two lines will be the same. This happens when the points $(x_i,y_i)$ all lie in one line (are collinear). In that case, all is not lost. Use one of our linear equations to solve for $y$ in terms of $x$, and substitute in the equation of one of our circles. After a while, we get a quadratic equation in $x$. Solve. In general there will be two solutions, and thus two possibilities for $(x_0,y_0)$, symmetric about the line that contains our points $(x_i,y_i)$ ($i=1,2,3$). A sketch shows that we cannot do any better, for when our three points are collinear, there are in general two possibilities for $(x_0,y_0)$.

-

Create three circles with the center in $S_{1,2,3}$ and the radius $d_{1,2,3}$.

The point of intersection of the three circles is the point you are looking for (if it exists).

-

essentially you are solving the following equation in $x_0$ and $y_0$:

$$\begin{cases}(x_0-x_1)^2+(y_0-y_1)^2=d_1^2 \\ (x_0-x_2)^2+(y_0-y_2)^2=d_2^2 \\ (x_0-x_3)^2+(y_0-y_3)^2=d_3^2\end{cases}$$

solving only the first 2 will give you 0, 1 or 2 solutions for which you can select the correct one from the third equation

with the formulas taken from http://paulbourke.net/geometry/2circle/

if $|S_1S_2|> d_1+d_2$ or $|S_1S_2|< |d_1-d_2|$ then there are no solutions and if $S_1=S_2$ and $d_1+d_2$ then all the points on the entire circle are solutions

and with $a=\frac{d_1^2 - d_2^2 + |S_1S_2|^2 }{ 2 *|S_1S_2| }$ and $h^2 = d_1^2-a^2$we have

$$\begin{cases}x_0 = x_1 \pm h*\frac{ y_2 - y_1 }{|S_1S_2|}\\ y_0 = y_1 \mp h*\frac{ x_2 - x_1 }{|S_1S_2|}\end{cases}$$

as possible solutions insert these into the third equation and eliminate the one that doesn't fit

-