Distances aux coordonnées

24

Il y a n personnes sur un plan 2D. En utilisant les distances entre eux, nous allons trouver leurs positions. Pour obtenir une réponse unique, vous devez faire quatre hypothèses:

  1. Il y a au moins 3 personnes.
  2. La première personne est en position (0, 0).
  3. La deuxième personne est en position (x, 0) pour certains x> 0.
  4. La troisième personne est en position (x, y) pour certains y> 0.

Votre défi consiste donc à écrire un programme ou une fonction qui, étant donné un tableau 2D de distances (où D[i][j]donne la distance entre une personne iet j), renvoie une liste de leurs coordonnées. Votre réponse doit être précise à au moins 6 chiffres significatifs. La solution la plus courte en octets gagne.

Exemples

[[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
la source
2
Donc, fondamentalement, vous recherchez la fonction inverse de DistanceMatrixin
mathica
Dans votre premier exemple, le troisième point pourrait être (3,4) ou (3, -4).
DavidC
@DavidC Vous n'avez pas lu suffisamment les hypothèses.
orlp
Oui. Je vois maintenant.
DavidC
2
Peut-il y avoir plus d'une bonne réponse ou est-ce que je fais quelque chose de mal? J'obtiens +0.322la dernière coordonnée du 2ème exemple.
Emigna

Réponses:

5

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

1 octet enregistré grâce à @Giuseppe et 2 octets grâce à @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

Essayez-le en ligne!

Utilise les 3 premiers points pour calculer le reste. Renvoie une paire x-coords, y-coords comme autorisé dans les commentaires .

PurkkaKoodari
la source
O+=[...]peut être O+=...,et o+=[x]peut être o+=x,.
Jonathan Frech
@JonathanFrech Ne fonctionne pas. Python permet uniquement d'ajouter des listes aux listes. TIO
PurkkaKoodari
@ Pietu1998 Je ne voulais pas dire o+=x, mais plutôt 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]))}

La grande longueur d'avance est sur la ligne 1 où j'utilise la fonction de R pour l'échelle multidimensionnelle (MDS). Le reste est probablement inefficace (merci d'avoir fait des suggestions sur la façon de s'améliorer): la ligne 2 traduit les données afin que le premier point soit à (0, 0); la ligne 3 fait pivoter les points de sorte que le deuxième point soit à (0, x); la ligne 4 retourne tout pour que le troisième point soit à y> 0.

flodel
la source
R a un intégré pour cela ??? Dang.
Giuseppe
3

R , 227 215 209 176 169 169 octets

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

Essayez-le en ligne!

Il était une fois, j'ai suivi un cours de Géométrie Computationnelle. Je voudrais dire que cela a aidé, mais je n'ai clairement rien appris.

L'entrée est une matrice R, avec en sortie une liste de vecteurs à 2 éléments (x,y)(qui est plus proche de la spécification et économise des octets).

Le problème ici est, bien sûr, les trois premiers points. Une fois que vous avez fixé trois points, vous pouvez calculer tous les autres en fonction de ceux-ci.

J'ai juste utilisé un peu d'algèbre pour simplifier les choses, puis j'ai remarqué que puisque je n'utilise que les 3 premiers points à résoudre pour les autres, tout est vectorisé très soigneusement.

Dépassé par flodel

Giuseppe
la source
2

JavaScript (ES7), 202 193 octets

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}

Cas de test

Afficher l'extrait de code

Comment?

Soit d i, j l'entrée et x i , y i la sortie attendue.

Selon les règles du défi, nous savons que:

  • Pour toute paire (i, j) : d i, j = √ ((x i - x j ) ² + (y i - y j ) ²)
  • x 0 = y 0 = y 1 = 0

On peut en déduire immédiatement:

  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 ²

Informatique x j

En utilisant 2 et 3, nous obtenons:

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

Qui conduit à:

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

Informatique y j

Maintenant que x j est connu, nous avons:

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

Qui donne:

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

Nous déterminons le signe de chaque y j en essayant simplement toutes les combinaisons possibles jusqu'à ce que nous correspondions aux distances d'origine. Nous devons également nous assurer que nous avons y 2 > 0 .

Nous le faisons en utilisant le bitmask k où les 1 sont interprétés comme positifs et les 0 sont interprétés comme négatifs. Nous commençons avec k = 7 ( 111 en binaire) et ajoutons 8 à chaque itération. De cette façon, les valeurs positives de y j sont garanties d'être sélectionnées pour 0 ≤ j ≤ 2 . (Nous pourrions tout aussi bien commencer par k = 4 , car y 0 = y 1 = 0 de toute façon. Mais l'utilisation de 7 empêche l' apparition de zéros négatifs .)

Arnauld
la source
Je ne sais pas si ce serait plus court, mais la bonne façon de calculer le signe de y (après le 3 initial) pour l'élément kest de trouver p = (x, y)avec deux points, de définir p' = (x, -y)et de prendre un troisième point déjà connu jet de comparer la distance d[i][j]avec dist(p, j)et dist(p', j). Je ne considère pas les zéros négatifs comme une réponse incorrecte au fait.
orlp
@orlp La suppression des zéros négatifs ne coûte aucun octet, c'est donc une considération purement esthétique. :-) (Et vous avez raison: cette méthode est un correctif plutôt inefficace sur une solution initialement non fonctionnelle. Mais je pensais que cela valait toujours la peine d'être publié.)
Arnauld
2

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

1 octet enregistré grâce à @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>
Développer l'extrait

Fonctionne un peu comme ma réponse Python. Les [x,y]paires retournées se sont avérées beaucoup plus courtes que les listes X et Y séparées dans JS. Remplace la liste d'arguments, donc ne l'utilisez pas plusieurs fois en entrée.

PurkkaKoodari
la source
2
@ Giuseppe En fait, je ne peux tout simplement pas marquer le f=et l'adapter en un. : P
PurkkaKoodari
eh bien je ne connais pas JavaScript donc je ne suis pas surpris d'avoir raté ça.
Giuseppe
2

Mathematica, 160 octets

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

Le programme utilise intégré RegionIntersectionpour calculer le point d'intersection des cercles. Le programme nécessite des coordonnées exactes pour fonctionner.

Cela suppose RegionIntersectiontoujours que le point avec la coordonnée y la plus élevée soit le dernier dans son résultat si la coordonnée x est égale. (au moins c'est vrai sur Wolfram Sandbox)

Pour une raison quelconque, RegionIntersectioncela ne fonctionne pas s'il y a trop de cercles dans son entrée, je dois donc traiter chaque paire une fois en utilisant Fold.

Montrez la capture d'écran:Capture d'écran

user202729
la source