Search code examples
mathgeometrytriangulation

Finding the coordinates of points from distance matrix

I have a set of points (with unknow coordinates) and the distance matrix. I need to find the coordinates of these points in order to plot them and show the solution of my algorithm.

I can set one of these points in the coordinate (0,0) to simpify, and find the others. Can anyone tell me if it's possible to find the coordinates of the other points, and if yes, how?

Thanks in advance!

EDIT Forgot to say that I need the coordinates on x-y only

Solution

  • Step 1, arbitrarily assign one point P1 as (0,0).

    Step 2, arbitrarily assign one point P2 along the positive x axis. (0, Dp1p2)

    Step 3, find a point P3 such that 

    Dp1p2 ~= Dp1p3+Dp2p3
Dp1p3 ~= Dp1p2+Dp2p3
Dp2p3 ~= Dp1p3+Dp1p2

    and set that point in the "positive" y domain (if it meets any of these criteria, the point should be placed on the P1P2 axis).
    Use the cosine law to determine the distance:

    cos (A) = (Dp1p2^2 + Dp1p3^2 - Dp2p3^2)/(2*Dp1p2* Dp1p3)
P3 = (Dp1p3 * cos (A), Dp1p3 * sin(A))

    You have now successfully built an orthonormal space and placed three points in that space.

    Step 4: To determine all the other points, repeat step 3, to give you a tentative y coordinate. (Xn, Yn).
    Compare the distance {(Xn, Yn), (X3, Y3)} to Dp3pn in your matrix. If it is identical, you have successfully identified the coordinate for point n. Otherwise, the point n is at (Xn, -Yn).

    Note there is an alternative to step 4, but it is too much math for a Saturday afternoon