Distâncias para coordenadas

24

Não há n pessoas em um plano 2D. Usando distâncias entre eles, vamos encontrar suas posições. Para obter uma resposta única, você deve fazer quatro suposições:

  1. Existem pelo menos 3 pessoas.
  2. A primeira pessoa está na posição (0, 0).
  3. A segunda pessoa está na posição (x, 0) para alguns x> 0.
  4. A terceira pessoa está na posição (x, y) para alguns y> 0.

Portanto, seu desafio é escrever um programa ou função que, com uma matriz 2D de distâncias (onde D[i][j]indica a distância entre a pessoa ie j), retorne uma lista de suas coordenadas. Sua resposta deve ter precisão de pelo menos 6 números significativos. A solução mais curta em bytes vence.

Exemplos

[[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
fonte
2
Então, basicamente você está procurando a função inversa de DistanceMatrixem mathematica ;-)
J42161217
No seu primeiro exemplo, o terceiro ponto pode ser (3,4) ou (3, -4).
DavidC
@ DavididC Você não leu as suposições suficientemente atentamente.
orlp
Sim. Agora eu vejo
DavidC
2
Pode haver mais de uma resposta correta ou estou fazendo algo errado? Estou obtendo +0.322a última coordenada do segundo exemplo.
Emigna

Respostas:

5

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

Guardou 1 byte graças a @ Giuseppe e 2 bytes graças a @ 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

Experimente online!

Usa os 3 primeiros pontos para calcular o restante. Retorna um par x-coords, y-coords conforme permitido nos comentários .

PurkkaKoodari
fonte
O+=[...]pode ser O+=...,e o+=[x]pode ser o+=x,.
Jonathan Frech
@JonathanFrech Não funciona. O Python permite apenas adicionar listas a listas. TIO
PurkkaKoodari
@ Pietu1998 Eu não quis dizer o+=x, mas sim 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]))}

O grande avanço está na linha 1, onde eu uso a função de R para o Multi-Dimensional Scaling (MDS). O resto é provavelmente ineficiente (obrigado por fazer sugestões sobre como melhorar): a linha 2 converte os dados para que o primeiro ponto esteja em (0, 0); a linha 3 gira os pontos para que o segundo ponto esteja em (0, x); a linha 4 vira tudo para que o terceiro ponto esteja em y> 0.

flodel
fonte
R tem um built-in para isso ?? 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)}

Experimente online!

Era uma vez, fiz um curso de Geometria Computacional. Eu gostaria de dizer que ajudou, mas claramente não aprendi nada.

Input é uma matriz R, com a saída uma lista de vetores de 2 elementos (x,y)(que está mais próximo da especificação e salva bytes).

O problema aqui é, obviamente, os três primeiros pontos. Depois de fixar três pontos, você pode calcular todos os outros com base nesses pontos.

Eu apenas usei um pouco de álgebra para simplificar as coisas e, em seguida, notei que, como só estou usando os 3 primeiros pontos para resolver os outros, tudo isso foi vetorizado de maneira muito clara.

Superado por flodel

Giuseppe
fonte
2

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}

Casos de teste

Mostrar snippet de código

Quão?

Seja d i, j a entrada e x i , y i a saída esperada.

Pelas regras do desafio, sabemos que:

  • Para qualquer par (i, j) : d i, j = √ ((x i - x j ) ² + (y i - y j ) ²)
  • x 0 = y 0 = y 1 = 0

Podemos deduzir imediatamente que:

  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 ²

Computação x j

Usando 2 e 3, obtemos:

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

O que leva a:

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

Computando y j

Agora que x j é conhecido, temos:

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

Que dá:

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

Determinamos o sinal de cada y j simplesmente tentando todas as combinações possíveis até corresponder às distâncias originais. Também temos que garantir que temos y 2 > 0 .

Fazemos isso usando a máscara de bits k em que 1 é interpretado como positivo e 0 é interpretado como negativo. Começamos com k = 7 ( 111 em binário) e adicionamos 8 a cada iteração. Dessa forma,é garantido queos valores positivos de y j sejam selecionados para 0 ≤ j ≤ 2 . (Poderíamos começar com k = 4 também, porque y 0 = y 1 = 0 de qualquer maneira. Mas o uso de 7 impede que zeros negativos apareçam.)

Arnauld
fonte
Não tenho certeza se seria mais curto, mas a maneira correta de calcular o sinal de y (após o 3 inicial) para o elemento ké encontrar p = (x, y)com dois pontos, definir p' = (x, -y)e pegar um terceiro ponto já conhecido je comparar a distância d[i][j]com dist(p, j)e dist(p', j). A propósito, não considero os zeros negativos uma resposta incorreta.
precisa saber é
@orlp Remover zeros negativos não custa nenhum byte, por isso é uma consideração puramente estética. :-) (e você está certo: esse método é uma solução bastante ineficiente em uma solução inicialmente não trabalhando Mas eu pensei foi ainda vale postagem..)
Arnauld
2

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

Guardou 1 byte graças a @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>
Expandir snippet

Funciona um pouco como a minha resposta Python. Os [x,y]pares retornados ficaram muito mais curtos que as listas X e Y separadas em JS. Substitui a lista de argumentos, portanto, não a use como entrada várias vezes.

PurkkaKoodari
fonte
2
@ Giuseppe Na verdade, eu simplesmente não consigo marcar f=e encaixar em um. : P
PurkkaKoodari
bem, eu não sei JavaScript, então não estou surpreso por ter perdido isso.
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)&

O programa usa interno RegionIntersectionpara calcular o ponto de interseção de círculos. Programa requer coordenadas exatas para funcionar.

Isso pressupõe RegionIntersectionsempre que o ponto com coordenadas y mais altas seja o último em seu resultado se a coordenada x for igual. (pelo menos é verdade no Wolfram Sandbox)

Por alguma razão RegionIntersection, não funciona se houver muitos círculos em sua entrada, então eu tenho que processar cada par uma vez usando Fold.

Demonstrar captura de tela:Captura de tela

user202729
fonte