28
\$\begingroup\$

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]]
\$\endgroup\$
14
  • 2
    \$\begingroup\$ So basically you are looking for the inverse function of DistanceMatrix in mathematica ;-) \$\endgroup\$
    – ZaMoC
    Sep 29, 2017 at 13:25
  • \$\begingroup\$ In your first example, the third point could be either (3,4) or (3,-4). \$\endgroup\$
    – DavidC
    Sep 29, 2017 at 13:25
  • \$\begingroup\$ @DavidC You didn't read the assumptions closely enough. \$\endgroup\$
    – orlp
    Sep 29, 2017 at 13:25
  • \$\begingroup\$ Yes. I now see. \$\endgroup\$
    – DavidC
    Sep 29, 2017 at 13:28
  • 2
    \$\begingroup\$ Can there be more than one correct answer or am I doing something wrong? I'm getting +0.322 for the last coordinate of the 2nd example. \$\endgroup\$
    – Emigna
    Sep 29, 2017 at 14:23

7 Answers 7

6
+200
\$\begingroup\$

APL (Dyalog Unicode), 74 59 bytes

+⍣(0>11○3⊃⊢)p÷×2⊃p←0j1⊥2↑⍉⊃⌹∘⍉⍨/1 .5*⍨2↑8415⌶.5×(⊣.+⍨-⊢)×⍨⎕

Try it online!

Lots of golfing at various places thanks to @H.PWiz and @ngn.

Uses the formula shown in the paper shared by Jonathan Allan. The formula on the paper involves EVD (eigenvalue decomposition), and fortunately Dyalog APL has its generalized version SVD(singular value decomposition). For square symmetric matrix \$M\$ as input, it exactly computes orthonormal \$U\$ and the diagonal matrix of eigenvalues \$\Lambda\$ in \$M=U\Lambda U^T\$.

Ungolfed and how it works

f←{
  m←×⍨⍵                     ⍝ square of distances
  v←1⌷m                     ⍝ first row
  G←.5×v+⍤1⍉m-⍤1⍨v          ⍝ -(m - column v - row v)÷2
            m-⍤1⍨v  ⍝ add v to -m by rows (rank 1)
           ⍉        ⍝ transpose
       v+⍤1         ⍝ add v to that by rows
    .5×             ⍝ halve

  U E←2↑8415⌶G              ⍝ singular value decomposition
        8415⌶G  ⍝ SVD built-in
                ⍝ since G is square and symmetric, it is identical to EVD
                ⍝ and gives orthonormal U, eigenvalue diagonal E,
                ⍝ transpose of V (≡ U), and a boolean indicator for success
      2↑        ⍝ we need only U and E

  pts←0j1⊥⊖(2↑E*.5)+.×⍉U    ⍝ compute pts as shown in the paper
                            ⍝ and convert to complex
           (2↑E*.5)         ⍝ first 2 rows of element-wise sqrt of E
                   +.×⍉U    ⍝ matmul with transposed U
                            ⍝ the resulting matrix is 2-row matrix where
                            ⍝ 1st row is x-coords and 2nd is y-coords
      0j1⊥⊖                 ⍝ compute x+yi for post-processing

  pts←pts×+×2⊃pts     ⍝ rotate by 2nd point's angle reversed
            2⊃pts  ⍝ the 2nd point
           ×       ⍝ signum; unit vector (representing angle)
          +        ⍝ complex conjugate (negation of angle)
      pts×         ⍝ rotate all points by that angle

  +⍣(0>11○3⊃pts)⊢pts  ⍝ mirror w.r.t. x-axis if 3rd point is below x-axis
  +⍣(          )  ⍝ conjugate all points (mirror w.r.t. x-axis) if...
          3⊃pts   ⍝ the 3rd point
       11○        ⍝ its complex part
     0>           ⍝ is negative
}
\$\endgroup\$
8
  • \$\begingroup\$ You can get rid of , and change v+⍤1⍉⍵-⍤1⍨v←1⌷⍵ to (⍉⊢-⊣⍀)⍣2⊢⍵ \$\endgroup\$
    – H.PWiz
    May 9, 2020 at 1:28
  • \$\begingroup\$ Although v-⍉⍵-v←⊣⍀⍵ is maybe simpler \$\endgroup\$
    – H.PWiz
    May 9, 2020 at 1:51
  • 1
    \$\begingroup\$ v+⍤1⍉⍵-⍤1⍨v←⊣/⍵ -> ⍵-⍨⊣.+⍨⍵ @Bubbler @H.PWiz \$\endgroup\$
    – ngn
    May 11, 2020 at 19:34
  • 1
    \$\begingroup\$ @H.PWiz .. or (⍉⊢-⊣⍀)⍣2 -> (⊣.+⍨-⊢) in your 64 bytes \$\endgroup\$
    – ngn
    May 11, 2020 at 19:40
  • 1
    \$\begingroup\$ (E*.5)⌹⍉⊃U E← -> ⊃⌹∘⍉⍨/1 .5*⍨ \$\endgroup\$
    – ngn
    May 11, 2020 at 19:45
5
+100
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ R has a built-in for this??? Dang. \$\endgroup\$
    – Giuseppe
    Sep 30, 2017 at 14:15
5
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ O+=[...] can be O+=..., and o+=[x] can be o+=x,. \$\endgroup\$ Sep 30, 2017 at 14:29
  • \$\begingroup\$ @JonathanFrech Doesn't work. Python only allows adding lists to lists. TIO \$\endgroup\$ Oct 2, 2017 at 11:20
  • \$\begingroup\$ @Pietu1998 I did not mean o+=x, but rather o+=x,. \$\endgroup\$ Oct 2, 2017 at 11:25
3
\$\begingroup\$

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 di,j be the input and xi, yi be the expected output.

By the challenge rules, we know that:

  • For any pair (i, j): di,j = √((xi - xj)² + (yi - yj)²)
  • x0 = y0 = y1 = 0

We can immediately deduce that:

  1. x1 = d0,1

  2. d0,j = √((x0 - xj)² + (y0 - yj)²) = √(xj² + yj²)
    d0,j² = xj² + yj²

  3. d1,j = √((x1 - xj)² + (y1 - yj)²) = √((x1 - xj)² + yj²)
    d1,j² = (x1 - xj)² + yj² = x1² + xj² + 2x1xj + yj² = d0,1² + xj² + 2d0,1xj + yj²

Computing xj

By using 2 and 3, we get:

xj² - (d0,1² + xj² - 2d0,1xj) = d0,j² - d1,j²

Which leads to:

xj = (d0,j² - d1,j² + d0,1²) / 2d0,1

Computing yj

Now that xj is known, we have:

yj² = d0,j² - xj²

Which gives:

yj = ±√(d0,j² - xj²)

We determine the sign of each yj by simply trying all possible combinations until we match the original distances. We also have to make sure that we have y2 > 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 yj are guaranteed to be selected for 0 ≤ j ≤ 2. (We could start with k = 4 just as well, because y0 = y1 = 0 anyway. But using 7 prevents negative zeros from appearing.)

\$\endgroup\$
2
  • \$\begingroup\$ I'm not sure whether it'd be shorter, but the correct way to calculate the sign of y (after the initial 3) for element k is to find p = (x, y) with two points, set p' = (x, -y), and take a third already-known point j and compare distance d[i][j] with dist(p, j) and dist(p', j). I don't consider negative zeroes an incorrect answer by the way. \$\endgroup\$
    – orlp
    Sep 29, 2017 at 20:47
  • \$\begingroup\$ @orlp Removing negative zeros doesn't cost any byte, so it's a purely aesthetic consideration. :-) (And you're right: this method is a rather inefficient fix on an initially non-working solution. But I thought it was still worth posting.) \$\endgroup\$
    – Arnauld
    Sep 29, 2017 at 21:04
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ @Giuseppe Actually, I can just not score the f= and fit it in one. :P \$\endgroup\$ Sep 29, 2017 at 20:54
  • \$\begingroup\$ well I don't know JavaScript so I'm not surprised I missed that. \$\endgroup\$
    – Giuseppe
    Sep 29, 2017 at 20:55
2
\$\begingroup\$

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:Screenshot

\$\endgroup\$
1
  • \$\begingroup\$ If I'm not mistaken, s[[2]]={#[[1,2]],0} can be replaced with s[[2,1]]=#[[1,2]]. \$\endgroup\$ May 7, 2020 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.