Preciso encontrar a direção da distância mais curta de um ponto no meu mundo 2D para outro ponto em que as bordas estão envolvidas (como asteróides etc.). Eu sei como encontrar a menor distância, mas estou lutando para encontrar em que direção está.
A menor distância é dada por:
int rows = MapY;
int cols = MapX;
int d1 = abs(S.Y - T.Y);
int d2 = abs(S.X - T.X);
int dr = min(d1, rows-d1);
int dc = min(d2, cols-d2);
double dist = sqrt((double)(dr*dr + dc*dc));
Exemplo do mundo
:
: T
:
:--------------:---------
: :
: S :
: :
: :
: T :
: :
:--------------:
No diagrama, as arestas são mostradas com: e -. Também mostrei uma repetição do mundo no canto superior direito. Quero encontrar a direção em graus de S a T. Portanto, a distância mais curta é a repetição no canto superior direito de T. mas como faço para calcular a direção em graus de S para o T repetido no canto superior direito?
Conheço as posições de S e T, mas suponho que preciso encontrar a posição do T repetido, porém há mais de 1.
O sistema de coordenadas do mundo começa em 0,0 no canto superior esquerdo e 0 graus para a direção pode começar no oeste.
Parece que isso não deve ser muito difícil, mas não consegui encontrar uma solução. Espero que alguém possa ajudar? Qualquer site seria apreciado.
Respostas:
Você precisará ajustar um pouco o algoritmo para calcular o ângulo - atualmente, você só registra a diferença absoluta na posição, mas precisa da diferença relativa (ou seja, pode ser positiva ou negativa, dependendo do posicionamento).
fonte
MapX
é 100,T.X
é 90 eS.X
é 10.dx
deve ser claramente 20, mas esse algoritmo retornará 30!Nesse mundo, há um número infinito de caminhos de S a T. Vamos denotar as coordenadas de T por
(Tx, Ty)
, as coordenadas de S por(Sx, Sy)
e o tamanho do mundo por(Wx, Wy)
. As coordenadas agrupadas de T são(Tx + i * Wx, Ty + j * Wy)
, ondei
ej
são números inteiros, isto é, elementos do conjunto{..., -2, -1, 0, 1, 2, ...}
. Os vetores que conectam S a T são(Dx, Dy) := (Tx + i * Wx - Sx, Ty + j * Wy - Sy)
. Para um determinado(i, j)
par, a distância é o comprimento do vetorsqrt(Dx * Dx + Dy * Dy)
e a direção em radianos éatan(Dy / Dx)
. O caminho mais curto é um dos 9 caminhos, ondei
ej
estão{-1, 0, 1}
:Os valores
i
ej
para o caminho mais curto podem ser determinados diretamente:Obrigado, @IlmariKaronen, @SamHocevar e @romkyns por sua ajuda!
fonte
abs(Tx-Sx) < Wx/2
, entãoi=0
é ideal; caso contrário, a escolha ideal éi=-1
oui=1
, dependendo do sinal deTx-Sx
. O mesmo vale paraTy-Sy
ej
.Calcule um vetor de direção possível, mesmo que não seja o menor, depois envolva sua coordenada X para que fique no
[-MapX/2,MapX/2]
intervalo e o mesmo para Y:É isso aí! Você também obtém a distância sem cálculos adicionais:
fonte
vec2 toroidalNearestWay (vec2 from, vec2 to, vec2 mapSize) { return (mod((to - from + 3.0 * mapSize / 2.0), mapSize)) - mapSize / 2.0; }
Eu acho que existem várias maneiras de fazer isso. Aqui estão 2 que eu consigo pensar em cima da minha cabeça:
# 1: Manipular casos manualmente
Existem exatamente 10 casos que podem acontecer:
S
Porém, para cada um dos ladrilhos circundantes, são permutações de cálculos diferentes para o componente de distância X ou Y. Por ser um número finito de casos, você pode apenas codificar como calculá-los e encontrar a menor distância entre todos eles.
Aqui está uma ilustração de 2 casos para encontrar
dx
. Caso 1, ondeT
está no mesmo bloco queS
, dx é justoS.x - T.x
. Para os ladrilhos à direita,dx
será calculado comoTileWidth - S.x + T.x
.Como uma pequena otimização, encontre a distância mínima antes de obter uma raiz quadrada. Então você economiza até 7
sqrt
chamadas.# 2: Abstraia as coordenadas
Se você precisar fazer algo mais "espacial" espacialmente, como um algoritmo de localização de caminhos, basta abstrair as coordenadas para que o algoritmo de localização de caminhos nem perceba que o mundo é feito de blocos repetitivos. O algoritmo de localização de caminho pode ir infinitamente em qualquer direção teoricamente (ok, bem, você será limitado por limites numéricos, mas você entendeu).
Para um cálculo simples da distância, não se preocupe em fazer isso.
fonte
Não se preocupe com as "9 direções". A razão é que existem 5 casos degenerados entre os 9: "norte reto", "oeste reto", "sul reto", "leste reto" e "idêntico". Por exemplo, o norte direto é degenerado porque representa o caso em que o noroeste e o nordeste se unem e produzem o mesmo resultado.
Assim, você tem quatro direções para calcular e pode escolher apenas o mínimo.
fonte
Obrigado por todas as respostas no final, usei Toomai editado por Scott Chamberlain. Eu também fiz algumas alterações devido ao fato de que meu sistema de coordenadas começa com y no canto superior esquerdo e aumenta à medida que você desce (basicamente invertido em comparação com as coordenadas normais do gráfico para y).
Publiquei caso alguém encontre essa página e tenha o mesmo sistema invertido.
fonte
y
no topo. É porque o comportamento desejado supostamente envolve as coordenadas na borda do mundo, enquanto o código que você reutilizou espelhava as coordenadas em cada limite.