Structure from sound - minimal problem in 2D

TOA 2D - minimal inverse problem 3 'sounds' and 3 'microphones

Here is a new solver for the problem of determining the 2D positions of 3 'microphones' and 3 'sounds sources' given the 9 distances between each sound source and each microphone. The code is available for download at github:

The problem was solved in Henrik Stewenius Thesis from 2005:

Henrik has a solver using his technique. It is available at

Here we present a new solver based on technique presented in

The input to the solver is a 3x3 matrix D, where the element D(i,j) is the distance from microphone i to sound source j. There can be several solutions. The output are two cell arrays, Rc and Sc, with all the real solutions to the problem, i.e. Rc{k} and Sc{k} are both 2x3 matrices for a solutions k, where Rc{k} represents the receiver positions in the plane and Sc{k} represents the sender positions in the plane. 



Generate data, receiver positions R and transmitter positions S

R = [[0;0] randn(2,2)]; R(1,3)=0
S = randn(2,3)
R =

         0    0.3923         0
         0    0.0017    0.3302

S =

   -1.9455    0.4918   -0.3845
    0.1514    0.0178   -0.0059

Calculate 9 distances from 3 transmitters to 3 receivers

d =

    1.9514    0.4921    0.3846
    2.3426    0.1008    0.7769
    1.9537    0.5826    0.5107

Run solver on distances, to obtain all real minimal solutions


Rc = 

  Columns 1 through 4

    [2x3 double]    [2x3 double]    [2x3 double]    [2x3 double]

  Column 5

    [2x3 double]

Sc = 

  Columns 1 through 4

    [2x3 double]    [2x3 double]    [2x3 double]    [2x3 double]

  Column 5

    [2x3 double]

Plot results (plot maximum of four of the real solutions)

close all;
for k = 1:min(length(Rc),4);
    hold off;
    hold on;
    for i = 1:3,
        for j = 1:3,
            plot([Rc{k}(1,i) Sc{k}(1,j)],[Rc{k}(2,i) Sc{k}(2,j)],'-');
            xx = (Rc{k}(1,i)+Sc{k}(1,j))/2;
            yy = (Rc{k}(2,i)+Sc{k}(2,j))/2;
Sidansvarig:  | 2015-11-06