0
$\begingroup$

I'm trying to solve a problem that to me is "triangulation" but searching to see if it's been answered before makes me think that this word has a different meaning to pure mathematicians.

Broadly, I'm using the term to refer to the kind of thing one does with a map and a compass to find location in planar space. However, my problem is probably more closely modeled on something like seismography or "passive sonar" except in two dimensional space. Here's the problem.

I have three sound sensors at known, fixed, locations. The "target" emits a noise somewhere in the space between these sensors. In due course, the sound reaches each of the sensors and the absolute time of these events is noted (by a computer!)Triangulation

Now, some notes:

  • The whole thing is entirely planar, I don't have a third dimension to worry about
  • I can position the three sensors to form an equilateral triangle, or put them on three vertices of a square, if either makes the math easier, mostly, I'm in complete control of the positions of the sensors, and there aren't any obstacles or the like
  • I know with modest accuracy the speed of sound in the medium this is all happening in, but I have a feeling that a solution should be possible without that information, instead relying only on the fact that the speed of sound is constant across the medium
  • I don't know the absolute time that the target emitted the sound, so the first knowledge about the event is when the first sensor responds. In effect, I have to treat that as time zero, and the only "real" input information (other than the geometry of the sensors, and possibly the speed of sound) is the two differential times, marked delta t 1 (green) and delta t 2 (purple) in the diagram.

I've tried a number of doodles hoping to solve this, but even just trying to plot the locus of possible points from one pair of sensors kept leading me to very messy worse-than-quadratic equations involving way too many squares and roots of compound expressions, and I have no idea if I'm even on the right track. Even if I solved that part, I'd still have to find a point by solving two of these equations simultaneously and given that my math ended not long after high school and that was forty years ago, I'm struggling badly!

On one hand, it would be most rewarding if I could solve this myself, so hints and references are welcome, but on the other hand, my main interest is in building the device and so an actual solution would be totally welcome too. I'll let you decide if you think this is an interesting investigation for me.

EDIT: So, I'm failing to understand Claude's help. I'm trying to take the equations he provided (6) and (7) and "(6) and (7), eliminate X and Y which then express as linear functions of T." But I don't understand how to do this. I've written out as far as I can get in the image:

enter image description here

But this gives me a function that relates Y and T, both of which are unknowns, but I don't understand how to eliminate Y to get at an expression for T (which is what I think Claude is telling me to do, though I admit I'm wondering if I've totally misunderstood). To be fair, even if I did have a function for T, I'm not entirely sure I see how the next step of "plug the results in 1" proceeds, but I'm not there yet anyway.

$\endgroup$
  • $\begingroup$ I take it your are trying to solve for both the time and position of the event? $\endgroup$ – saulspatz Dec 22 '18 at 23:53
  • 1
    $\begingroup$ This comes down to finding (or, in real life, estimating) the intersection of three hyperbolas. Search for “TDOA (Time Difference of Arrival) geolocation” or “multilateration.’ $\endgroup$ – amd Dec 22 '18 at 23:54
  • $\begingroup$ You can suppose that the speed of sound in the medium is $1$ unit per second, so you can use distance instead of time. That should give you a clue as to where the hyperbolas in @amd's comment come from. $\endgroup$ – saulspatz Dec 23 '18 at 0:00
  • $\begingroup$ @saulspatz, no, I only care about the location, not the time. I'll investigate the answer from Claude Leibovici below and the hyperbolae observation and see what I find. Thanks. $\endgroup$ – Toby Eggitt Dec 23 '18 at 15:57
0
$\begingroup$

You have $3$ sensors located at coordinates $(x_i,y_i)$ which receive the information at times $t_i$ and you look for the coordinates $(X,Y)$ where the event happened at time $T$. Let $v$ be the speed of sound.

Consider the three equations $$(X-x_1)^2+(Y-y_1)^2 = v^2 (t_1-T)^2 \tag 1$$ $$(X-x_2)^2+(Y-y_2)^2 = v^2 (t_2-T)^2 \tag 2$$ $$(X-x_3)^2+(Y-y_3)^2 = v^2 (t_3-T)^2 \tag 3$$

Subtract $(1)$ from $(2)$ and $(3)$, simplify and group terms. You will get $$2(x_1-x_2)X+2(y_1-y_2)Y+2(t_2-t_1)v^2 T=(x_1^2+y_1^2)-(x_2^2+y_2^2)+v^2(t_2^2-t_1^2)=2R_{12} \tag 4$$ $$2(x_1-x_3)X+2(y_1-y_3)Y+2(t_3-t_1)v^2 T=(x_1^2+y_1^2)-(x_3^2+y_3^2)+v^2(t_3^2-t_1^2)=2R_{13} \tag 5$$ that is to say $$(x_1-x_2)X+(y_1-y_2)Y+(t_2-t_1)v^2 T=R_{12} \tag 6$$ $$(x_1-x_3)X+(y_1-y_3)Y+(t_3-t_1)v^2 T=R_{13} \tag 7$$ From $(6)$ and $(7)$, eliminate $X$ and $Y$ which then express as linear functions of $T$. Plug the results in $(1)$; this gives a quadratic equation in $T$. Solve it and go back to $X$ and $Y$.

$\endgroup$
  • $\begingroup$ Ah, yes, these look similar in complexity to what I was coming up with, though I'd left out speed and they weren't the same. One question; what are R12 and R13? I haven't studied your answer yet, so if I realize it's obvious when I do, I apologize! And does the world get any simpler if I don't care about the time? (I actually don't...) Meanwhile, thanks for this Claude! $\endgroup$ – Toby Eggitt Dec 23 '18 at 16:02
  • $\begingroup$ @TobyEggitt. $(x_1^2+y_1^2)-(x_2^2+y_2^2)+v^2(t_2^2-t_1^2)=2R_{12}$ and look for the other one. It is not so complex (I used this for decades). For sure the problem is simpler with distances than with time. $\endgroup$ – Claude Leibovici Dec 23 '18 at 16:07
  • $\begingroup$ Complexity is relative :) Hopefully I'll work out R12 soon. I'll get to work and come back if I fall flat on my face (or if I succeed!) $\endgroup$ – Toby Eggitt Dec 23 '18 at 16:32
  • $\begingroup$ @TobyEggitt. Yes, please : let me know ! Cheers :-) $\endgroup$ – Claude Leibovici Dec 23 '18 at 16:49
  • $\begingroup$ Well, I have to admit I'm struggling. I finally managed to reproduce what you've already done, so at least I actually understand that. And I know that "R12" is a shorthand for "half the right hand side result of the subtraction of 1 from 2" ;) But when I try to work with 6 and 7 I'm failing. I started down the path of re-writing 6 to give me an expression for X, with the intention of patching that into 7. But a) it's huge (well, that might be OK I suppose) and b) this route only eliminates X, it does nothing for Y. Can you give a hint as to how I do this elimination? $\endgroup$ – Toby Eggitt Dec 26 '18 at 16:52

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.