Entfernungen zu Koordinaten

24

In einer 2D-Ebene befinden sich n Personen. Indem wir Entfernungen zwischen ihnen verwenden, werden wir ihre Positionen finden. Um eine eindeutige Antwort zu erhalten, müssen Sie vier Annahmen treffen:

  1. Es sind mindestens 3 Personen.
  2. Die erste Person ist auf Position (0, 0).
  3. Die zweite Person ist an Position (x, 0) für einige x> 0.
  4. Die dritte Person ist an Position (x, y) für ein y> 0.

Ihre Herausforderung besteht also darin, ein Programm oder eine Funktion zu schreiben, die bei einem gegebenen 2D-Array von Entfernungen (wobei D[i][j]die Entfernung zwischen Person iund Person angegeben wird j) eine Liste ihrer Koordinaten zurückgibt. Ihre Antwort muss auf mindestens 6 signifikante Stellen genau sein. Kürzeste Lösung in Bytes gewinnt.

Beispiele

[[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]]
code-golf geometry orlp
quelle
2
Also im Grunde suchen Sie nach der Umkehrfunktion DistanceMatrixin Mathematica ;-)
J42161217
In Ihrem ersten Beispiel könnte der dritte Punkt entweder (3,4) oder (3, -4) sein.
DavidC
@DavidC Du hast die Annahmen nicht genau genug gelesen.
Orlp
Ja. Ich verstehe jetzt.
DavidC
2
Kann es mehr als eine richtige Antwort geben oder mache ich etwas falsch? Ich komme +0.322zur letzten Koordinate des zweiten Beispiels.
Emigna

Antworten:

5

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

1 Byte dank @Giuseppe und 2 Byte dank @JonathanFrech gespeichert.

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

Probieren Sie es online!

Verwendet die ersten 3 Punkte, um den Rest zu berechnen. Gibt ein Paar von x-coords, y-coords wie in Kommentaren erlaubt zurück .

PurkkaKoodari
quelle
O+=[...]kann sein O+=...,und o+=[x]kann sein o+=x,.
Jonathan Frech
@ JonathanFrech Funktioniert nicht. Python erlaubt nur das Hinzufügen von Listen zu Listen. TIO
PurkkaKoodari
@ Pietu1998 meinte ich nicht o+=x, sondern eher o+=x,.
Jonathan Frech
4

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]))}

Der große Vorsprung befindet sich in Zeile 1, in der ich die R-Funktion für Multi-Dimensional Scaling (MDS) verwende. Der Rest ist wahrscheinlich ineffizient (danke für Verbesserungsvorschläge): Zeile 2 übersetzt die Daten so, dass der erste Punkt bei (0, 0) liegt; Linie 3 dreht die Punkte so, dass der zweite Punkt bei (0, x) liegt; Zeile 4 kippt alles so, dass der dritte Punkt bei y> 0 liegt.

Flodel
quelle
R hat ein eingebautes dafür ??? Dang.
Giuseppe
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)}

Probieren Sie es online!

Es war einmal ein Kurs in Computational Geometry. Ich möchte sagen, das hat geholfen, aber ich habe eindeutig nichts gelernt.

Die Eingabe ist eine R - Matrix, während die Ausgabe eine Liste von 2 - Element - Vektoren enthält (x,y)(die näher an der Spezifikation und der Formel liegen) Bytes speichert).

Das Problem hierbei sind natürlich die ersten drei Punkte. Sobald Sie drei Punkte festgelegt haben, können Sie alle anderen anhand dieser Punkte berechnen.

Ich habe nur ein bisschen Algebra verwendet, um die Dinge zu vereinfachen, und dann bemerkt, dass ich nur die ersten 3 Punkte verwende, um für die anderen Punkte zu lösen, was alles sehr ordentlich vektorisiert.

Von Flodel überfordert

Giuseppe
quelle
2

JavaScript (ES7), 202 - 193 Byte

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}

Testfälle

Code-Snippet anzeigen

Wie?

Sei d i, j der Eingang und x i , y i der erwartete Ausgang.

Durch die Herausforderungsregeln wissen wir, dass:

  • Für jedes Paar (i, j) gilt : d i, j = √ ((x i - x j ) ² + (y i - y j ) ²)
  • x 0 = y 0 = y 1 = 0

Daraus können wir sofort schließen:

  1. x 1 = d 0,1

  2. d 0, j = √ ((x 0 - x j ) ² + (y 0 - y j ) ²) = √ (x j ² + y j ²)
    d 0, j ² = x j ² + y j ²

  3. d 1, j = √ ((x 1 - x j ) ² + (y 1 - y j ) ²) = √ ((x 1 - x j ) ² + y j ²)
    d 1, j ² = (x 1 - x j ) ² + y j ² = x 1 ² + x j ² + 2x 1 x j + y j ² = d 0,1 ² + x j ² + 2d 0,1 x j + y j ²

Rechnen x j

Mit 2 und 3 erhalten wir:

x j ² - (d 0,1 ² + x j ² - 2d 0,1 x j ) = d 0, j ² - d 1, j ²

Was dazu führt:

x j = (d 0, j ² - d 1, j ² + d 0,1 ²) / 2d 0,1

Computing y j

Nun, da x j bekannt ist, haben wir:

y j ² = d 0, j ² - x j ²

Welches gibt:

y j = ± √ (d 0, j ² - x j ²)

Wir bestimmen das Vorzeichen jedes y j, indem wir einfach alle möglichen Kombinationen ausprobieren, bis wir mit den ursprünglichen Abständen übereinstimmen. Wir müssen auch sicherstellen, dass wir y haben 2 > 0 haben .

Wir tun das durch die Bitmaske mit k , wo 1 ‚s interpretiert werden als positive und 0 ‘ s werden als negativ interpretiert. Wir beginnen mit k = 7 ( 111 in binär) und addieren 8 bei jeder Iteration. Auf diese Weise, positive Werte von y j sind garantiert für ausgewählt werden : 0 ≤ j ≤ 2 . (Wir könnten genauso gut mit k = 4 beginnen , weil y 0 = y 1 = 0 ist. Die Verwendung von 7 verhindert jedoch, dass negative Nullen auftreten.)

Arnauld
quelle
Ich bin nicht sicher, ob es kürzer wäre, aber der richtige Weg, das Vorzeichen von y (nach der ersten 3) für das Element zu berechnen, kbesteht darin, p = (x, y)mit zwei Punkten p' = (x, -y)einen dritten bereits bekannten Punkt zu finden , festzulegen und die jEntfernung zu vergleichen d[i][j]mit dist(p, j)und dist(p', j). Ich halte negative Nullen übrigens nicht für eine falsche Antwort.
Orlp
@orlp Das Entfernen negativer Nullen kostet kein Byte, daher ist es eine rein ästhetische Überlegung. :-) (Und Sie haben Recht: Diese Methode ist eine ziemlich ineffiziente Lösung für eine anfangs nicht funktionierende Lösung. Aber ich dachte, es lohnt sich immer noch, sie zu veröffentlichen.)
Arnauld,
2

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

1 Byte dank @Giuseppe gespeichert.

/* 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>
Erweitern Sie das Snippet

Funktioniert etwas wie meine Python-Antwort. Die Rückgabe von [x,y]Paaren fiel viel kürzer aus als die getrennten X- und Y-Listen in JS. Überschreibt die Argumentliste, verwenden Sie sie also nicht mehrmals als Eingabe.

PurkkaKoodari
quelle
2
@ Giuseppe Eigentlich kann ich das einfach nicht punkten f=und es in eines einpassen . : P
PurkkaKoodari
Nun, ich kenne kein JavaScript, also bin ich nicht überrascht, dass ich das verpasst habe.
Giuseppe
2

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)&

Das Programm verwendet eingebaute RegionIntersection , um den Schnittpunkt von Kreisen zu berechnen. Das Programm erfordert eine genaue Koordinate.

Dies setzt voraus RegionIntersection dass der Punkt mit der höheren y-Koordinate immer der letzte in seinem Ergebnis ist, wenn die x-Koordinate gleich ist. (Zumindest trifft es auf Wolfram Sandbox zu)

Aus irgendeinem Grund RegionIntersection funktioniert es nicht, wenn die Eingabe zu viele Kreise enthält, sodass ich jedes Paar einmal mit verarbeiten mussFold .

Screenshot demonstrieren:Bildschirmfoto

user202729
quelle