1

Here is an example:

Suppose there are 4 points: A, B, C, and D

Given that Point A is at (0,0):
and the distances:

A to B: 7
A to C: 5
A to D: 9
B to C: 6
B to D: 5
C to D: 7

The goal would be to find a solution to points B(x,y), C(x,y) and D(x,y)

What is an algorithm to find the points ( up to 50 of them ) given the distances between them?

Dr C
  • 150
  • 3
  • 9
  • If you have one coordinate and a bunch of distances, there's an infinite number of possible solutions. For example, B(0,7) is valid and so is B(7,0) and so is B(7*cos(theta), 7*sin(theta)) for any value of theta between 0 and 360. If you have two coordinates, there are two possible solutions (one solution, plus its mirror image across the axis of the two known coordinates). If you have three coordinates, you can find everything unambiguously with triangulation. – Kevin Nov 04 '14 at 18:04
  • Additionally, there are infeasible inputs: d(A,B) = d(B,C) = 1, d(A,C) = 3 does not satisfy the triangle inequality. d(A,B) = d(A,C) = d(A,D) = d(B,C) = d(B,D) = d(C,D) = 1 satisfies the triangle inequality, but those distance can only be satisfied if you extend your embedding to use 3 dimensions. – Timothy Shields Nov 04 '14 at 18:12
  • 3
    See [Finding the coordinates of points from distance matrix](http://stackoverflow.com/q/10963054/1468366) or [Using distance matrix to find coordinate points of set of points](http://stackoverflow.com/q/18096783/1468366). – MvG Nov 04 '14 at 19:21
  • I am looking for any solution that works for the given distances – Dr C Nov 04 '14 at 21:02
  • @DrC possible duplicate of this http://stackoverflow.com/a/25928054/2521214 – Spektre Nov 05 '14 at 10:15

1 Answers1

0

OK,you have 4 points A, B, C, and D which are separated from one another such that the lengths of the distances between each pair of points is AB=7, AC=5, BC=6, AD=9, BD=5, and CD=7. Axyz=(0,0,0), Bxyz=(7,0,0), Cxyz=(2.7,4.2,0), Dxyz=(7.5,1.9,4.6) (rounding to the first decimal).

  • We set point A at the origin Axyz= (0,0,0).
  • We set point B at x=7,y=0,z=0 Bxyz= (7,0,0).

  • We find the x coordinate for point C by using the law of cosines:

  • ((AB^2+AC^2-BC^2)/2)/Bx = Cx

  • ((7^2+5^2-6^2)/2)/7=
  • ((49+25-36)/2)/7= 38/14 = 2.714286
  • We then use the pythagorean theorem to find Cy:
  • sqrt(AC^2-Cx^2)=Cy
  • sqrt(25-7.367347)=4.199
  • So Cxyz=(2.714,4.199,0)
  • We find Dx in much the same way we found Cx:
  • ((AB^2+AD^2-BD^2)/2)/Bx =Dx
  • ((49+81-25)/2)/7= 7.5 = Dx
  • We find Dy by a slightly different formula:
  • (((AC^2+AD^2-CD^2)/2)-(Cx*Dx))/Dy
  • (((25+81-49)/2)-(2.714*7.5))/4.199= 1.94 (approx)
  • Having found Dx and Dy, we can find Dz by using Pythagorean theorem:
  • sqrt(AD^2-Dx^2-Dy^2)=
  • sqrt(9^2-7.5^2-1.94^2) = 4.58
  • So Dxyz=(7.5, 1.94, 4.58)

If you have pairwise distances between each of a set of 50 points, then you might need as many as 49 dimensions in order to obtain coordinates for all the points. If A, B, C, D, and E are all separated by 10 lengths units from each of every other, then you would need 4 spatial dimensions - if you introduce another point (F) which is also equidistant from all the other points, then you will need 5 dimensions. The algorithm works the same no matter how many dimensions are necessary (and in fact it works best when the maximum number of dimensions IS required-). The algorithm also works when the distances violate the triangle rule - such as if AB=3, AC=4, and BC=13 - the coordinates are A=0,0; B=3,0; and C=-24,23.66i. If the triangle rule is violated, then some of the coordinates will simply be imaginary valued. No big deal. In general for point G, the coordinates (x1st, x2nd, x3rd, x4th, x5th, and x6th) can be found thusly:

  • G1st=((AB^2+AG^2-BG^2)/2)/(B1st)
  • G2nd=(((AC^2+AG^2-CG^2)/2)-(C1st*G1st))/(C2nd)
  • G3rd=(((AD^2+AG^2-DG^2)/2)-(D1stG1st)-(D2ndG2nd))/(D3rd)
  • G4th=(((AE^2+AG^2-EG^2)/2)-(E1stG1st)-(E2ndG2nd)-(E3rd*G3rd))/(E4th)
  • G5th=(((AF^2+AG^2-FG^2)/2)-(F1stG1st)-(F2ndG2nd)-(F3rdG3rd)-(F4thG4th))/(F5th)
  • G6th=sqrt(AG^2-G1st^2-G2nd^2-G3rd^2-G4th^2-G5th^2)

For the 5th point you find the first three coordinates with lawofcosine calculations and you find the 4th coordinate with a pythagoreantheorem calculations. For the 6th point you find the first 4 coordinates with 4 lawofcosine calculations and then you obtain the final coordinate with the pythagoreantheorem calculation. For the 50th point, you find the first 48 coordinates with 48 lawofcosines calculations and the 49th coordinate is found with a pythagoreantheorem calculation. So for 50 points, there will be 48 pythagoreantheorem calculations altogether plus 1128 lawofcosine calculations.

  • The algorithm is fairly straightforward:
  • A is always set at the origin and B is set at x=AB (or rather B1st=AB)
  • C1st is found by using the law of cosines ((AB^2+AC^2-BC^2)/2)/(B1st)
  • C2nd is then found with pythagorean theorem (sqrt(AC^2-C1st^2))
  • BUT WHAT IF C2nd = 0? This is not necessarily a problem, but it can become a problem for finding D2nd, D3rd, E2nd, E3rd, E4th, etc.
  • If AB=4, AC=8, BC=4, then we will obtain A (0,0), B (4,0), and C (8,0). If AD=4, BD=8, and CD=12, then there will be no problem for finding coordinates for D which would be D (-4,0).
  • However, if CD is not equal to 12, then we WILL have a problem. For instance, if CD=5, then we might find that we should go back and calculate coordinates for the points in a different order such as ACDB, that way we can get A=(0,0,0);C=(8,0,0); D=(3.44,2.04,0); and B=(4,-14.55,14.55i). This is a fairly intuitive solution, but it interrupts the flow of the algorithm because we have to go backwards and start over in a different order.
  • Another solution to the problem which does not necessitate interrupting the flow of computations is to deliberately introduce an error whenever a pythagoreantheorem calculation gives us a zero. -- Instead of a zero, put a 0.1 or 0.01 as the C2nd coordinate. This will allow one to proceed with calculating coordinates for the remaining points without interruption and the accuracy of the final results will suffer only a little (truth be told the algorithm is subject to cumulative rounding errors anyhow, so its no big deal). Also the deliberate introduction of error is the only way to obtain a solution at all in some cases:
  • Consider once again 4 points A, B, C, and D with distances such the AB=4, AC=8, BC=4, AD=4, BD=8, and CD=4 (we previously have had CD at 12, and CD at 5). When CD=4, there IS NO exact solution no matter what order you calculate the points. Go ahead and try.
  • A=(0,0,0), B=(4,0,0), C=(8,0,0)... If you introduce an error at C2nd so that instead of zero you put 0.1 such that C=(8,0.1,0), then you can obtain a solution for point D's coordinates D=(-4,640,640i). If you introduce a smaller error for C2nd such that C=(8,0.01,0), then you get D=(-4,6400,6400i). As C2nd gets closer and closer to zero, D2nd, and D3rd just get farther and farther away along the same direction. A similar result occurs sometimes when the distance between two points is close to zero. The algorithm ofcourse will not work with a distance that is actually equal to zero such with AB=5,AC=8, and BC=0. But it will work with BC=0.000001.
  • Anyway, I think this has answered your question you asked a year ago.
Ian Quinn
  • 1
  • 1