1
$\begingroup$

I'm attempting to solve a problem similar to trilateration but with slightly different data.

I want to find the center of a circle (in my case, its coordinate is the origin of a sound wave). Let's call the center of this circle $c$.

Imagine then I have a set of three points $p1...p3$ which are equidistant from each other, but all different distances from the origin of the sound, $c$.

Imagine a circle travelling outward from $c$ (this is the sound wave propagating). It will "hit" one of these points first - let's call this point $p_1$. This point then, by definition, intersects with the circle propagating from $c$ at this point in time.

Imagine for the sake of this explanation that this circle then stops propagating outwards, and instead, circles begin propagating from each of the remaining points $p_2$ and $p_3$ until these circles lie tangentially on the circle centered on $c$ at the moment that it intersects with $p_1$.

I'm hoping that this can be visually intuited with the graph below (The green point is $c$, the point in the bottom right is $p_1$, and the other two points whose circles lie tangentially to the circle centered on $c$ are naturally $p_1...p_2$):

Graph of the sound propagation

In actuality though, I only have a subset of the data depicted above known to me. That subset is:

  1. The coordinates of $p_1$, $p_2$, and $p_3$.
  2. The radii of the circles centered on $p_2$ and $p_3$.

My question: with only these known quantities, is it even possible for me to deduce the center of $c$? If so, how?

I've tried following trilateration tutorials, done a fair bit of article reading, but this seems like a weird sub-field / nuanced problem that seems to be preventing the information from applying completely.

Any help would be much appreciated. Thank you!

$\endgroup$
  • $\begingroup$ This problem is exactly trilateration using time difference of arrival (TDOA). $\endgroup$ – amd Sep 26 '19 at 3:08
1
$\begingroup$

Your problem is exactly the “time difference of arrival” setup for trilateration: the radii of the two circles are proportional to the differences in arrival times between the first receiver and the other two. As such, it is equivalent to finding the intersection of one branch of each of a pair of hyperbolas. In general, this requires solving a quartic equation, though it can be reduced to a cubic equation with a bit of work. There is a lot of literature out there on the Web on this subject, so I’m only going to give a brief gloss here.

Let the coordinates of the first receiver be $P_0=(x_0,y_0)$ and the two fixed circles have respective centers $P_1=(x_1,y_1)$ and $P_2=(x_2,y_2)$ and radii $r_1$ and $r_2$. Letting $(x,y)$ be the coordinates of the center of the unknown circle, the difference in reception times between $P_0$ and $P_1$ can be expressed as $$\sqrt{(x-x_1)^2+(y-y_1)^2}-\sqrt{(x-x_0)^2+(y-y_0)^2}=r_1. \tag{*}$$ This equation describes one branch of the hyperbola with foci $P_0$ and $P_1$ and transverse axis length $r_1$. The time difference between $P_0$ and $P_2$ gives rise to a similar equation of a hyperbola with foci at $P_0$ and $P_2$. The branch of interest in each case is the one that is closer to $P_0$, which will give you the two external tangents.

By squaring (*), rearranging, squaring again and simplifying, you can transform equation (*) into the form of a general conic equation, but in the process extraneous roots are introduced—the other branch of each hyperbola gets added. When you solve the resulting system of second-degree equations, you will get up to four real solutions—each fixed circle can be tangent to the unknown one either externally or internally. The correct solution to the original equations is the one that is closest to $P_0$.

Taking the example from your other question, $P_0=(0.87,-0.5)$, $P_1=(0,1)$, $r_1=\sqrt{0.015}$, $P_2=(-0.87,-0.5)$ and $r_2=\sqrt{0.236}$. Mathematica comes up with approximately $(0.299,0.098)$ as the solution to the resulting system of equations. The illustration below shows the solution and the two hyperbola branches used to find it.

TDOA

$\endgroup$
  • $\begingroup$ Amazing, that's the exact solution I was looking for. I must admit that a lot of this goes over my head though. How did you derive that equation for the hyperbola? $\endgroup$ – jonny Sep 26 '19 at 13:53
  • $\begingroup$ @jonny One of the definitions of a hyperbola is the locus of points with a constant difference between their distances to a pair of fixed points (the foci). The two terms on the left side of (*) are just applications of the usual distance formula. We want the distance to $P_0$ to be the lesser one, so it gets subtracted. $\endgroup$ – amd Sep 27 '19 at 0:00
  • $\begingroup$ @jonny Note that you can simplify the equations quite a bit by choosing a coordinate system in which $P_0$ is the origin and $P_1$ lies on the positive $x$-axis. $\endgroup$ – amd Sep 27 '19 at 0:06
  • $\begingroup$ Thanks @amd that makes total sense to me now - the difference of the magnitude of the vectors remains constant. Something else I'm a little confused about is why the hyperbola equations above only draw one branch - I thought hyperbolae by definition always defined two branches? $\endgroup$ – jonny Sep 27 '19 at 13:10
  • $\begingroup$ So given that the points are always equidistant from eachother, if I say that $P_0 = (0, 0)$ , $P_1 = (1.734, 0)$ and $P_2 = (0.867, 1.5)$ I can simplify the 2 equations down to $2y^2-3.5x+3=r_1^2$ and $2y^2-3y-1.734x+3=r_2^2$ - is that correct? If so, how do I then solve this system of multivariate quadratics? I may be way in over my head here... $\endgroup$ – jonny Sep 27 '19 at 14:00
1
$\begingroup$

You do have enough information to find the center of the circle.

Let the coordinates of the three point $(x_1,y_1)$, $(x_2,y_2)$ and $(x_3,y_3)$, and the radii of the two known circles $r_1$ and $r_2$, respectively. Also, denote the center and the radius of the unknown circle $(a,b)$ and $r$.

Then, the following relationships based on distances from the center $(a,b)$ to the three points can be established,

$$(a-x_1)^2+(b-y_1)^2 = (r_1+r)^2\tag{1}$$ $$(a-x_2)^2+(b-y_2)^2 = (r_2+r)^2\tag{2}$$ $$(a-x_3)^2+(b-y_3)^2 =r^2\tag{3}$$

Observe that you have three unknowns and three equations, from which $(a,b)$ and $r$ can be solved.

$\endgroup$
  • $\begingroup$ Thanks so much quanto for your prompt and detailed answer. Excuse my ignorance, I'm not very math literate, but how would I then solve for (a, b) and r in this case? Would I simply subsitute in the known values I have and then rearrange for a b and r seperately or are there other steps? $\endgroup$ – jonny Sep 23 '19 at 23:09
  • $\begingroup$ @jonny - you May take a look at the site en.m.wikipedia.org/wiki/System_of_linear_equations for solving systems of liners equation. Look for the section ‘Solving linear systems’ $\endgroup$ – Quanto Sep 23 '19 at 23:38

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.