Solving a System of Quadratic Equations for Sound Triangulation

Question

I am currently attempting to solve a system of quadratic (and linear) systems that I have run into while trying to triangulate sound.

My hypothetical setup includes 3 sensors on a perfectly equilateral triangle, with one sensor located at $(0,0)$ and the other two located below it. (The specifics don't matter, as I am simply referring to the sensor locations using $a_1,a_2,a_3$ for the x-coordinates of the sensors, and $b_1,b_2,b_3$ for the y-coordinates of the sensors, with $r_1,r_2,r_3$ being the radii of the circles from each respective sensor to the sound point)

I am trying to specify equations for the x position of the sound, the y position of the sound, and finally the radius of the incident sensor to the sound (the sensor that picks up the sound wave first).

My equations are as follows:

$$(x - a_1)^2 + (y - b_1)^2 = r_1^2$$ $$(x - a_2)^2 + (y - b_2)^2 = r_2^2$$ $$(x - a_3)^2 + (y - b_3)^2 = r_3^2$$ $$r_3 = r_1 + (t_3 * \text{speed of sound})$$ $$r_2 = r_1 + (t_2 *\text{speed of sound})$$

In this example, I am assuming that the sound reaches sensor 1 first. I understand that a true solution requires 3 discrete solutions, one for each sensor being the "incident sensor". (assuming that there cannot be a scenario where sound perfectly reaches multiple sensors at the same time)

My known variables: $a_1,a_2,a_3,b_1,b_2,b_3,\text{speed of sound}, t_1,t_2,t_3$

My Unknown variables: $x,y,r_1,r_2,r_3$.

Now I understand that I can just substitute in the three linear equations, but that leaves me with three quadratic equations that I am unsure of how to solve and obtain a meaningful answer from.

I tried searching for revelant topics, and the closest I could come was this: https://math.stackexchange.com/a/187858/656339

Which has the same setup as I, but doesn't detail how to solve it.

Any help would be appreciated.

Answer 1

Solving system of quadratic and indeed, general polynomial equations is possible with techniques like Buchberger's algorithm. See the first two chapters of the book by Cox et.al. There are also many numerical tools to assist you with this. Sympy in python is one alternative (the one I'd recommend) and there is also one I wrote in C# following the textbook cited.

Answer 2

After comments, let us work with $4$ sonsors. So we have $$(x - a_1)^2 + (y - b_1)^2 = c^2(t_1-\tau)^2\tag 1$$ $$(x - a_2)^2 + (y - b_2)^2 = c^2(t_2-\tau)^2\tag 2$$ $$(x - a_3)^2 + (y - b_3)^2 = c^2(t_3-\tau)^2\tag 3$$ $$(x - a_4)^2 + (y - b_4)^2 = c^2(t_4-\tau)^2\tag 4$$ where $c$ is the speed of sound and $\tau$ the time at which was produced the sound.

Now, subtract $(1)$ from $(2)$, $(3)$ and $(4)$ to get $$2(a_1-a_2)x+2(b_1-b_2)y+2c^2(t_2-t_1)\tau=(a_1^2+b_1^2-c^2t_1^2)-(a_2^2+b_2^2-c^2t_2^2)\tag 5$$ $$2(a_1-a_3)x+2(b_1-b_3)y+2c^2(t_3-t_1)\tau=(a_1^2+b_1^2-c^2t_1^2)-(a_3^2+b_3^2-c^2t_3^2)\tag 6$$ $$2(a_1-a_4)x+2(b_1-b_4)y+2c^2(t_4-t_1)\tau=(a_1^2+b_1^2-c^2t_1^2)-(a_4^2+b_4^2-c^2t_4^2)\tag 7$$

Define, for more simplicity, $$\alpha_i=2(a_1-a_i)\qquad \beta_i=2(b_1-b_i)\qquad \gamma_i=2c^2(t_i-t_1)$$ $$k_i=(a_1^2+b_1^2-c^2t_1^2)-(a_i^2+b_i^2-c^2t_i^2)$$ $(i=2,3,4)$ to make $$\alpha_2x+\beta_2y+\gamma_2 \tau=k_2\tag 8$$ $$\alpha_3x+\beta_3y+\gamma_3 \tau=k_3\tag 9$$ $$\alpha_4x+\beta_4y+\gamma_4 \tau=k_4\tag {10}$$ So, three linear equations in $(x,y,\tau)$ (easy to solve - use matrix calculations or successive elimination as I did below) and the explicit solutions are

$$\tau=\frac{k_4 (\alpha_3 \beta_2-\alpha_2 \beta_3)+k_3 (\alpha_2 \beta_4-\alpha_4 \beta_2)+k_2 (\alpha_4 \beta_3-\alpha_3 \beta_4) } {\alpha_4 (\beta_3 \gamma_2-\beta_2 \gamma_3)+\alpha_3 (\beta_2 \gamma_ 4-\beta_4 \gamma_2)+\alpha_2 (\beta_4 \gamma_3-\beta_3 \gamma_4) }\tag {11}$$ $$y=\frac{\alpha_3 (\gamma_2 \color{red}{\tau} -k_2)+\alpha_2 (k_3-\gamma_3 \color{red}{\tau} )}{\alpha_ 2 \beta_3-\alpha_3 \beta_2}\tag {12}$$ $$x=\frac{k_2-\beta_2 \color{red}{y}-\gamma_2 \color{red}{\tau} }{\alpha_2}\tag {13}$$