Distances to coordinates

Question

There are n people on a 2D plane. Using distances between them we're going to find their positions. To get a unique answer you must make four assumptions:

1. There are at least 3 people.
2. The first person is at position (0, 0).
3. The second person is at position (x, 0) for some x > 0.
4. The third person is at position (x, y) for some y > 0.

So your challenge is to write a program or function that given a 2D array of distances (where D[i][j] gives the distance between person i and j) returns a list of their coordinates. Your answer must be accurate to at least 6 significant figures. Shortest solution in bytes wins.

---

Examples

[[0.0, 3.0, 5.0], [3.0, 0.0, 4.0], [5.0, 4.0, 0.0]]

=>

[[0.0, 0.0], [3.0, 0.0], [3.0, 4.0]]


[[0.0, 0.0513, 1.05809686, 0.53741028, 0.87113533], [0.0513, 0.0, 1.0780606,
0.58863967, 0.91899559], [1.05809686, 1.0780606, 0.0, 0.96529704,
1.37140397], [0.53741028, 0.58863967, 0.96529704, 0.0, 0.44501955],
[0.87113533, 0.91899559, 1.37140397, 0.44501955, 0.0]]

=>

[[0.0, 0.0], [0.0513, 0.0], [-0.39, 0.9836], [-0.5366, 0.0295], [-0.8094, -0.3221]]


[[0.0, 41.9519, 21.89390815, 108.37048253, 91.40006121, 49.35063671,
82.20983622, 83.69080223, 80.39436793, 86.5204431, 91.24484876, 22.32327813,
99.5351474, 72.1001264, 71.98278813, 99.8621559, 104.59071383, 108.61475753,
94.91576952, 93.20212636], [41.9519, 0.0, 24.33770482, 144.67214389,
132.28290899, 49.12079288, 85.34321428, 117.39095617, 103.60848008,
79.67795144, 69.52024038, 42.65007733, 105.60007249, 110.50120501,
89.92218111, 60.03623019, 133.61394005, 76.26668715, 130.54041305,
122.74547069], [21.89390815, 24.33770482, 0.0, 130.04213984, 112.98940283,
54.26427666, 71.35378232, 104.72088677, 81.67425703, 90.26668791,
71.13288376, 18.74250061, 109.87223765, 93.96339767, 69.46698314,
84.37362794, 124.38527485, 98.82541733, 116.43603102, 113.07526035],
[108.37048253, 144.67214389, 130.04213984, 0.0, 37.8990613, 111.2161525,
176.70411028, 28.99007398, 149.1355788, 124.17549005, 198.6298252,
126.02950495, 101.55746829, 37.24713176, 152.8114446, 189.29178553,
34.96711005, 180.83483984, 14.33728853, 35.75999058], [91.40006121,
132.28290899, 112.98940283, 37.8990613, 0.0, 111.05881157, 147.27385449,
44.12747289, 115.00173099, 134.19476383, 175.9860033, 104.1315771,
120.19673135, 27.75062658, 120.90347767, 184.88952087, 65.64187459,
183.20903265, 36.35677531, 60.34864715], [49.35063671, 49.12079288,
54.26427666, 111.2161525, 111.05881157, 0.0, 125.59451494, 82.23823276,
129.68328938, 37.23819968, 118.38443321, 68.15130552, 56.84347674,
84.29966837, 120.38742076, 78.30380948, 91.88522811, 72.15031414,
97.00421525, 82.23460459], [82.20983622, 85.34321428, 71.35378232,
176.70411028, 147.27385449, 125.59451494, 0.0, 158.1002588, 45.08950594,
161.43320938, 50.02998891, 59.93581537, 180.43028005, 139.95387244,
30.1390519, 133.42262669, 182.2085151, 158.47101132, 165.61965338,
170.96891788], [83.69080223, 117.39095617, 104.72088677, 28.99007398,
44.12747289, 82.23823276, 158.1002588, 0.0, 136.48099476, 96.57856065,
174.901291, 103.29640959, 77.53059476, 22.95598599, 137.23185588,
160.37639016, 26.14552185, 152.04872054, 14.96145727, 17.29636403],
[80.39436793, 103.60848008, 81.67425703, 149.1355788, 115.00173099,
129.68328938, 45.08950594, 136.48099476, 0.0, 166.89727482, 92.90019808,
63.53459104, 177.66159356, 115.1228903, 16.7609065, 160.79059188,
162.35278463, 179.82760993, 140.44928488, 151.9058635], [86.5204431,
79.67795144, 90.26668791, 124.17549005, 134.19476383, 37.23819968,
161.43320938, 96.57856065, 166.89727482, 0.0, 148.39351779, 105.1934756,
34.72852943, 106.44495924, 157.55442606, 83.19240274, 96.09890812,
61.77726814, 111.24915274, 89.68625779], [91.24484876, 69.52024038,
71.13288376, 198.6298252, 175.9860033, 118.38443321, 50.02998891,
174.901291, 92.90019808, 148.39351779, 0.0, 72.71434547, 175.07913091,
161.59035051, 76.3634308, 96.89392413, 195.433818, 127.21259331,
185.63246606, 184.09218079], [22.32327813, 42.65007733, 18.74250061,
126.02950495, 104.1315771, 68.15130552, 59.93581537, 103.29640959,
63.53459104, 105.1934756, 72.71434547, 0.0, 121.04924013, 88.90999601,
52.48935172, 102.51264644, 125.51831504, 117.54806623, 113.26375241,
114.12813777], [99.5351474, 105.60007249, 109.87223765, 101.55746829,
120.19673135, 56.84347674, 180.43028005, 77.53059476, 177.66159356,
34.72852943, 175.07913091, 121.04924013, 0.0, 93.63052717, 171.17130953,
117.77417844, 69.1477611, 95.81237385, 90.62801636, 65.7996984],
[72.1001264, 110.50120501, 93.96339767, 37.24713176, 27.75062658,
84.29966837, 139.95387244, 22.95598599, 115.1228903, 106.44495924,
161.59035051, 88.90999601, 93.63052717, 0.0, 117.17351252, 159.88686894,
48.89223072, 156.34374083, 25.76186961, 40.13509273], [71.98278813,
89.92218111, 69.46698314, 152.8114446, 120.90347767, 120.38742076,
30.1390519, 137.23185588, 16.7609065, 157.55442606, 76.3634308, 52.48935172,
171.17130953, 117.17351252, 0.0, 145.68608389, 162.51692098, 166.12926334,
142.8970605, 151.6440003], [99.8621559, 60.03623019, 84.37362794,
189.29178553, 184.88952087, 78.30380948, 133.42262669, 160.37639016,
160.79059188, 83.19240274, 96.89392413, 102.51264644, 117.77417844,
159.88686894, 145.68608389, 0.0, 169.4299171, 33.39882791, 175.00707479,
160.25054951], [104.59071383, 133.61394005, 124.38527485, 34.96711005,
65.64187459, 91.88522811, 182.2085151, 26.14552185, 162.35278463,
96.09890812, 195.433818, 125.51831504, 69.1477611, 48.89223072,
162.51692098, 169.4299171, 0.0, 156.08760216, 29.36259602, 11.39668734],
[108.61475753, 76.26668715, 98.82541733, 180.83483984, 183.20903265,
72.15031414, 158.47101132, 152.04872054, 179.82760993, 61.77726814,
127.21259331, 117.54806623, 95.81237385, 156.34374083, 166.12926334,
33.39882791, 156.08760216, 0.0, 167.00907734, 148.3962894], [94.91576952,
130.54041305, 116.43603102, 14.33728853, 36.35677531, 97.00421525,
165.61965338, 14.96145727, 140.44928488, 111.24915274, 185.63246606,
113.26375241, 90.62801636, 25.76186961, 142.8970605, 175.00707479,
29.36259602, 167.00907734, 0.0, 25.82164171], [93.20212636, 122.74547069,
113.07526035, 35.75999058, 60.34864715, 82.23460459, 170.96891788,
17.29636403, 151.9058635, 89.68625779, 184.09218079, 114.12813777,
65.7996984, 40.13509273, 151.6440003, 160.25054951, 11.39668734,
148.3962894, 25.82164171, 0.0]]

=>

[[0.0, 0.0], [41.9519, 0.0], [19.6294, 9.6969], [-88.505, -62.5382],
[-88.0155, -24.6423], [21.2457, -44.5433], [14.7187, 80.8815], [-59.789,
-58.5613], [-29.9331, 74.6141], [34.5297, -79.3315], [62.6017, 66.3826],
[5.2353, 21.7007], [6.1479, -99.3451], [-62.597, -35.7777], [-13.6408,
70.6785], [96.8736, -24.2478], [-61.4216, -84.6558], [92.2547, -57.3257],
[-74.7503, -58.4927], [-55.0613, -75.199]]

Answer 1

Python 2, 183 178 166 161 160 159 158 156 bytes

Saved 1 byte thanks to @Giuseppe and 2 bytes thanks to @JonathanFrech.

def f(D):
 X=D[0][1];o=[0,X];O=[0,0];n=2
 for d in D[2:]:y=d[0]**2;x=(y-d[1]**2)/X/2+X/2;y-=x*x;o+=x,;O+=y**.5*(y>d[2]**2-(x-o[2])**2or-1),;n+=1
 return o,O

Try it online!

Uses the first 3 points to calculate the rest. Returns a pair of x-coords, y-coords as allowed in comments.

Answer 2

R, 107

function(d){y=t(cmdscale(d))
y=y-y[,1]
p=cbind(c(y[3],-y[4]),y[4:3])%*%y/sum(y[,2]^2)^.5
p*c(1,sign(p[6]))}

The big head start is on line 1 where I use R's function for Multi-Dimensional Scaling (MDS). The rest is probably inefficient (thanks for making suggestions on how to improve): line 2 translates the data so that the first point is at (0, 0); line 3 rotates the points so that the second point is at (0,x); line 4 flips everything so that the third point is at y>0.

Answer 3

R, 227 215 209 176 169 bytes

function(d){x=y=c(0,0)
x[2]=a=d[1,2]
d=d^2
i=3:nrow(d)
D=d[1,i]
x[i]=(D+a^2-d[2,i])/2/a
y[3]=e=sqrt(d[1,3]-x[3]^2)
y[i]=(D-d[3,i]+x[3]^2+e^2-2*x[3]*x[i])/2/e
Map(c,x,y)}

Try it online!

Once upon a time, I took a course in Computational Geometry. I'd like to say that helped, but I clearly learned nothing.

Input is an R matrix, with the output a list of 2-element vectors (x,y) (which is closer to the spec and saves bytes).

The problem here is, of course, the first three points. Once you fix three points, you can compute all the others based on those.

I just used a bit of algebra to simplify things and then noticed that since I'm only using the first 3 points to solve for the others, this all vectorized very neatly.

Outgolfed by flodel

Answer 4

JavaScript (ES7), 202 193 bytes

d=>{for(k=7;(a=d.map((r,i)=>[x=(r[0]**2-r[1]**2+a*a)/2/a,(d[0][i]**2-x*x)**.5*(k>>i&1||-1)],a=d[0][1])).some(([x,y],i)=>a.some(([X,Y],j)=>(Math.hypot(x-X,y-Y)-d[i][j])**2>1e-6));k+=8);return a}

Test cases

let f =

d=>{for(k=7;(a=d.map((r,i)=>[x=(r[0]**2-r[1]**2+a*a)/2/a,(d[0][i]**2-x*x)**.5*(k>>i&1||-1)],a=d[0][1])).some(([x,y],i)=>a.some(([X,Y],j)=>(Math.hypot(x-X,y-Y)-d[i][j])**2>1e-6));k+=8);return a}

format = a => a.map(JSON.stringify).join`\n`

console.log(format(f([[0.0,3.0,5.0],[3.0,0.0,4.0],[5.0,4.0,0.0]])))
console.log(format(f([[0.0,0.0513,1.05809686,0.53741028,0.87113533],[0.0513,0.0,1.0780606,0.58863967,0.91899559],[1.05809686,1.0780606,0.0,0.96529704,1.37140397],[0.53741028,0.58863967,0.96529704,0.0,0.44501955],[0.87113533,0.91899559,1.37140397,0.44501955,0.0]])))
console.log(format(f([[0.0,41.9519,21.89390815,108.37048253,91.40006121,49.35063671,82.20983622,83.69080223,80.39436793,86.5204431,91.24484876,22.32327813,99.5351474,72.1001264,71.98278813,99.8621559,104.59071383,108.61475753,94.91576952,93.20212636],[41.9519,0.0,24.33770482,144.67214389,132.28290899,49.12079288,85.34321428,117.39095617,103.60848008,79.67795144,69.52024038,42.65007733,105.60007249,110.50120501,89.92218111,60.03623019,133.61394005,76.26668715,130.54041305,122.74547069],[21.89390815,24.33770482,0.0,130.04213984,112.98940283,54.26427666,71.35378232,104.72088677,81.67425703,90.26668791,71.13288376,18.74250061,109.87223765,93.96339767,69.46698314,84.37362794,124.38527485,98.82541733,116.43603102,113.07526035],[108.37048253,144.67214389,130.04213984,0.0,37.8990613,111.2161525,176.70411028,28.99007398,149.1355788,124.17549005,198.6298252,126.02950495,101.55746829,37.24713176,152.8114446,189.29178553,34.96711005,180.83483984,14.33728853,35.75999058],[91.40006121,132.28290899,112.98940283,37.8990613,0.0,111.05881157,147.27385449,44.12747289,115.00173099,134.19476383,175.9860033,104.1315771,120.19673135,27.75062658,120.90347767,184.88952087,65.64187459,183.20903265,36.35677531,60.34864715],[49.35063671,49.12079288,54.26427666,111.2161525,111.05881157,0.0,125.59451494,82.23823276,129.68328938,37.23819968,118.38443321,68.15130552,56.84347674,84.29966837,120.38742076,78.30380948,91.88522811,72.15031414,97.00421525,82.23460459],[82.20983622,85.34321428,71.35378232,176.70411028,147.27385449,125.59451494,0.0,158.1002588,45.08950594,161.43320938,50.02998891,59.93581537,180.43028005,139.95387244,30.1390519,133.42262669,182.2085151,158.47101132,165.61965338,170.96891788],[83.69080223,117.39095617,104.72088677,28.99007398,44.12747289,82.23823276,158.1002588,0.0,136.48099476,96.57856065,174.901291,103.29640959,77.53059476,22.95598599,137.23185588,160.37639016,26.14552185,152.04872054,14.96145727,17.29636403],[80.39436793,103.60848008,81.67425703,149.1355788,115.00173099,129.68328938,45.08950594,136.48099476,0.0,166.89727482,92.90019808,63.53459104,177.66159356,115.1228903,16.7609065,160.79059188,162.35278463,179.82760993,140.44928488,151.9058635],[86.5204431,79.67795144,90.26668791,124.17549005,134.19476383,37.23819968,161.43320938,96.57856065,166.89727482,0.0,148.39351779,105.1934756,34.72852943,106.44495924,157.55442606,83.19240274,96.09890812,61.77726814,111.24915274,89.68625779],[91.24484876,69.52024038,71.13288376,198.6298252,175.9860033,118.38443321,50.02998891,174.901291,92.90019808,148.39351779,0.0,72.71434547,175.07913091,161.59035051,76.3634308,96.89392413,195.433818,127.21259331,185.63246606,184.09218079],[22.32327813,42.65007733,18.74250061,126.02950495,104.1315771,68.15130552,59.93581537,103.29640959,63.53459104,105.1934756,72.71434547,0.0,121.04924013,88.90999601,52.48935172,102.51264644,125.51831504,117.54806623,113.26375241,114.12813777],[99.5351474,105.60007249,109.87223765,101.55746829,120.19673135,56.84347674,180.43028005,77.53059476,177.66159356,34.72852943,175.07913091,121.04924013,0.0,93.63052717,171.17130953,117.77417844,69.1477611,95.81237385,90.62801636,65.7996984],[72.1001264,110.50120501,93.96339767,37.24713176,27.75062658,84.29966837,139.95387244,22.95598599,115.1228903,106.44495924,161.59035051,88.90999601,93.63052717,0.0,117.17351252,159.88686894,48.89223072,156.34374083,25.76186961,40.13509273],[71.98278813,89.92218111,69.46698314,152.8114446,120.90347767,120.38742076,30.1390519,137.23185588,16.7609065,157.55442606,76.3634308,52.48935172,171.17130953,117.17351252,0.0,145.68608389,162.51692098,166.12926334,142.8970605,151.6440003],[99.8621559,60.03623019,84.37362794,189.29178553,184.88952087,78.30380948,133.42262669,160.37639016,160.79059188,83.19240274,96.89392413,102.51264644,117.77417844,159.88686894,145.68608389,0.0,169.4299171,33.39882791,175.00707479,160.25054951],[104.59071383,133.61394005,124.38527485,34.96711005,65.64187459,91.88522811,182.2085151,26.14552185,162.35278463,96.09890812,195.433818,125.51831504,69.1477611,48.89223072,162.51692098,169.4299171,0.0,156.08760216,29.36259602,11.39668734],[108.61475753,76.26668715,98.82541733,180.83483984,183.20903265,72.15031414,158.47101132,152.04872054,179.82760993,61.77726814,127.21259331,117.54806623,95.81237385,156.34374083,166.12926334,33.39882791,156.08760216,0.0,167.00907734,148.3962894],[94.91576952,130.54041305,116.43603102,14.33728853,36.35677531,97.00421525,165.61965338,14.96145727,140.44928488,111.24915274,185.63246606,113.26375241,90.62801636,25.76186961,142.8970605,175.00707479,29.36259602,167.00907734,0.0,25.82164171],[93.20212636,122.74547069,113.07526035,35.75999058,60.34864715,82.23460459,170.96891788,17.29636403,151.9058635,89.68625779,184.09218079,114.12813777,65.7996984,40.13509273,151.6440003,160.25054951,11.39668734,148.3962894,25.82164171,0.0]])))

How?

Let d_i,j be the input and x_i, y_i be the expected output.

By the challenge rules, we know that:

• For any pair (i, j): d_i,j = √((x_i - x_j)² + (y_i - y_j)²)
• x₀ = y₀ = y₁ = 0

We can immediately deduce that:

1. x₁ = d_0,1

2. d_0,j = √((x₀ - x_j)² + (y₀ - y_j)²) = √(x_j² + y_j²)
   d_0,j² = x_j² + y_j²

3. d_1,j = √((x₁ - x_j)² + (y₁ - y_j)²) = √((x₁ - x_j)² + y_j²)
   d_1,j² = (x₁ - x_j)² + y_j² = x₁² + x_j² + 2x₁x_j + y_j² = d_0,1² + x_j² + 2d_0,1x_j + y_j²

Computing x_j

By using 2 and 3, we get:

x_j² - (d_0,1² + x_j² - 2d_0,1x_j) = d_0,j² - d_1,j²

Which leads to:

x_j = (d_0,j² - d_1,j² + d_0,1²) / 2d_0,1

Computing y_j

Now that x_j is known, we have:

y_j² = d_0,j² - x_j²

Which gives:

y_j = ±√(d_0,j² - x_j²)

We determine the sign of each y_j by simply trying all possible combinations until we match the original distances. We also have to make sure that we have y₂ > 0.

We do that by using the bitmask k where 1's are interpreted as positive and 0's are interpreted as negative. We start with k = 7 (111 in binary) and add 8 at each iteration. This way, positive values of y_j are guaranteed to be selected for 0 ≤ j ≤ 2. (We could start with k = 4 just as well, because y₀ = y₁ = 0 anyway. But using 7 prevents negative zeros from appearing.)

Answer 5

JavaScript (ES7), 140 139 126 121 118 117 bytes

Saved 1 byte thanks to @Giuseppe.

/* this line for testing only */ f =
D=>D.map((d,n)=>n>1?(y=d[0]**2,D[n]=x=(y-d[1]**2)/X/2+X/2,y-=x*x,[x,y**.5*(y>d[2]**2-(x-D[2])**2||-1)]):[X=n*d[0],0])

<!-- HTML for testing only --><textarea id="i" oninput="test()">[[0.0, 0.0513, 1.05809686, 0.53741028, 0.87113533], [0.0513, 0.0, 1.0780606, 0.58863967, 0.91899559], [1.05809686, 1.0780606, 0.0, 0.96529704, 1.37140397], [0.53741028, 0.58863967, 0.96529704, 0.0, 0.44501955], [0.87113533, 0.91899559, 1.37140397, 0.44501955, 0.0]]</textarea><pre id="o"></pre><script>window.onload=test=function(){try{document.querySelector("#o").innerHTML=JSON.stringify(f(JSON.parse(document.querySelector("#i").value)))}catch(e){}}</script>

Works somewhat like my Python answer. Returning [x,y] pairs turned out much shorter than separate X and Y lists in JS. Overwrites the argument list, so don't use it as input multiple times.

Answer 6

Mathematica, 160 bytes

(s=Table[0{,},n=Tr[1^#]];s[[2]]={#[[1,2]],0};f@i_:=RegionIntersection~Fold~Table[s[[j]]~Circle~#[[j,i]],{j,i-1}];s[[3]]=Last@@f@3;Do[s[[i]]=#&@@f@i,{i,4,n}];s)&

The program use built-in RegionIntersection to calculate intersection point of circles. Program requires exact coordinate to work.

This assumes RegionIntersection always make the point with higher y-coordinate the last one in its result if the x-coordinate is equal. (at least it is true on Wolfram Sandbox)

For some reason RegionIntersection doesn't work if there is too many circles in its input so I have to process each pair once by using Fold.

Demonstrate screenshot: