determinando a distância entre os pontos em n-dimensões

Question

Estou construindo uma tabela mySQL listando pontos em n-dimensões, cada dimensão estão sendo indexados. Dado qualquer ponto do sistema n-dimensional, eu gostaria de ser capaz de saída de todos os outros pontos na ordem de sua distância do ponto escolhido.

Uma solução simples seria a distâncias de calcular cada ponto usando o teorema de Pitágoras ... sqrt (x ^ 2 + y ^ 2) = z. Eu estava buscando um método mais eficiente. Só é necessária uma ordem aproximada, então eu sou muito mente aberta.

Graças.

-diddle

Answer 1

Juntamente com o que tem sido dado, você poderia também considerar "binning" seus pontos - ou seja (pelo menos mentalmente) desenhar uma grade sobre o seu "mapa", e os pontos de percurso com base em qual quadrado eles se enquadram. Basicamente, você começa com os pontos na mesma praça, em seguida, os de um "anel" em torno quadrado do ponto escolhido, então o próximo anel exterior, e assim por diante. Dependendo do tamanho da grade que você usa, você pode fazer este tão preciso ou aproximar como você gosta. Claro, uma grade 2D é para 2D pontos - se tem mais dimensões, você tem que aumentar a dimensionalidade da grade para coincidir com

.

Answer 2

Uma técnica comum para este tipo de coisa é considerar a distância ao quadrado em vez da distância real que elimina a raiz quadrada, mas, se eu estou entendendo a pergunta corretamente, você não precisa para recuperar a distância real entre o seu índice. Nesse caso, você poderia usar apenas a soma do valor absoluto de cada componente.