Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Problem Description

share|improve this question
1  
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
add comment

3 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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