How to find the position of points given relative distances ?

33 次查看（过去 30 天）
Kamran
Kamran 2019-8-23
回答： Aaron T. Becker's Robot Swarm Lab 2023-5-1
Hi,
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.
  2 个评论
Ted Shultz
Ted Shultz 2019-8-23
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 2019-8-23
编辑：Adam Danz 2019-8-23
"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.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Adam Danz
Adam Danz 2019-8-23
编辑：Adam Danz 2019-8-23
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.
Caveats
  • 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
figure();
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')
legend()
%% Notes
%[1]Law of cosines: https://www.mathsisfun.com/algebra/trig-solving-sss-triangles.html
%[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
Result
  4 个评论
显示 2更早的评论
Kamran
Kamran 2019-8-26
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.
Cheers,
kamran

请先登录，再进行评论。

更多回答（1 个）

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

类别

在 Help Center 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息

标签

产品


版本

R2013b

Community Treasure Hunt

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

Start Hunting!

Translated by