Clear Filters
Clear Filters

How to find the position of points given relative distances ?

36 views (last 30 days)
I have found the relative distances between 4 microphones using cross-correlation. The values are not very accurate because of measurement noise or other noise in the recordings. Given the distances, is it possible to find the approximate positions of the microphones using the first one as the reference (position [0 0]) ? The likely positions are on circles whose radius are the given distances. The relative distances follow. The distance estimates may be wrong, so I am more interested in knowing if the problem can be solved in general, that is if the measurements were correct. Some sort of grid search maybe ? For simplification I have assumed that the microphones are on the same level, that is a 2D problem.
from mic. 1 to mic. 2: -4.915(m)
from mic. 1 to mic. 3: 2.571(m)
from mic. 1 to mic. 4: -5.123(m)
from mic. 2 to mic. 3: 5.162(m)
from mic. 2 to mic. 4: -0.212(m)
from mic. 3 to mic. 4: -5(m) % this one is very uncertain
Thanks in advance.
Ted Shultz
Ted Shultz on 23 Aug 2019
This is called Multilateration. In particular TDOA (time difference of arrival). The Wikipedia page has a possible solution algorithm you may want to try.
Adam Danz
Adam Danz on 23 Aug 2019
Edited: Adam Danz on 23 Aug 2019
"Given the distances, is it possible to find the approximate positions of the microphones using the first one as the reference"
It depends. Given just the distances and a reference point of mic #1, it will not be possible to compute the position of the microphones in the world without more information. To illustrate, imagine rotating the microphone layout about the pivot point at mic #1 (0,0). The distance between the mics hasn't changed and the reference point hasn't change but the world-coordinates of the microphones have changed.
If we can assume the position of a second mic the problem is solved. For example, if the distance between mic 1 and mic 2 is 5 and we can assume mic 2 shares the same y coordinate as mic 1, it would be farily straightforward to compute the coordinates of the other mics.

Sign in to comment.

Accepted Answer

Adam Danz
Adam Danz on 23 Aug 2019
Edited: Adam Danz on 23 Aug 2019
This solution computes the coordinates of each microphone relative to mic #1 with the following assumptions.
  1. The position of mic #1 is a fixed reference point
  2. Mic #1 and #2 share the same y coordinate.
The code creates a 'real' microphone layout (red squared below) and then computes the distances between each mic. These distances are the input used to calculate the mic positions which are plotted in blue x's to confirm accuracy. It computes the internal angle 'c' and 'e' from the image below to find the position of mic #3 and #4. See comments in code for more detail.
  • incorrect distances will give you incorrect results
  • to get the actual world coordinates of the micophones relative to mic #1, you'd merely need to rotate the results but the angle of rotation is currently unknown given only distances.
  • Notice that the distance betweed mic #2 and #4 is not used. You could use that distance to test accuracy by comparing it to the distance between your calculated mic #2 and #4 positions.
%% Real mic positions (this is not known; it will be used to compute distances)
xy = [0 0; % mic 1; reference, always at (0,0)
2 0; % mic 2
2.5 4; % mic 3
-.5 3.5]; % mic 4
% Compute distances between all mics (these distances will already be known)
micDists = squareform(pdist(xy)); % micDists(i,j) is dist between xy(i,:) and xy(j,:)
% View layout
plot(xy(:,1),xy(:,2), 'rs','MarkerSize', 12, 'LineWidth',2,'DisplayName','Actual position')
text(xy(:,1)+.1,xy(:,2),{'mic 1','mic 2','mic 3','mic 4'})
axis equal
grid on
hold on
%% Calculate the position of each mic given the distances and reference point
% Use the law of cosines [1] to ...
% ...compute the angle c (between the lines at mic 1,2 and mic 1,3)
a = micDists(1,2); %distance between mic 1,2
b = micDists(1,3); %distance between mic 1,3
c = micDists(2,3); %distance between mic 2,3
ang_c = acos((a^2 + b^2 - c^2)/(2*a*b)); %radians
%...compute the angle e (between the lines at mic 1,4 and mic 1,3)
d = micDists(1,4); %distance between mic 1,2
e = micDists(4,3); %distance between mic 1,3
ang_e = acos((b^2 + d^2 - e^2)/(2*b*d)); %radians
% Define mic position 1
mic1Pos = [0,0];
% Compute position of mic #2 with the following 2 assumptions
% * it shares the same y coordinate as mic 1
% * it's to the right of mic 2 on the graph
% You can switch that the 'left' with minimal changes below.
mic2Pos(1) = mic1Pos(1) + micDists(1,2);
mic2Pos(2) = mic1Pos(2);
% Compute position of mic #3 [2]
mic3Pos(1) = mic1Pos(1,1) + micDists(1,3) * cos(ang_c);
mic3Pos(2) = mic1Pos(1,1) + micDists(1,3) * sin(ang_c);
% Compute the position of mic #4 [3]
mic4Pos(1) = mic1Pos(1,1) + micDists(1,4) * cos(ang_c + ang_e);
mic4Pos(2) = mic1Pos(1,1) + micDists(1,4) * sin(ang_c + ang_e);
% plot results on top of previous plot
plot([mic1Pos(1),mic2Pos(1),mic3Pos(1),mic4Pos(1)], ...
[mic1Pos(2),mic2Pos(2),mic3Pos(2),mic4Pos(2)], ...
'bx','LineWidth',2,'DisplayName', 'Computed position')
%% Notes
%[1]Law of cosines:
%[2] the angle needed in the 3rd term is the angle that pivots about mic #1 between the x axis and mic #3
%[3] the angle needed in the 3rd term is the angle that pivots about mic #1 between the x axis and mic #4
Kamran on 26 Aug 2019
Thanks very much for your offer. I think I understand what is happening in your code. Very much obliged. I was thinking of solving system of equations when I started the thread. Didn't even think that there is a more elegant way to do it.

Sign in to comment.

More Answers (1)

Aaron T. Becker's Robot Swarm Lab
Matlab has the function cmdscale for this type of problem.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!