Posso simplificar a desigualdade "distância (p1, p2) <distância (p1, p3)?"

14

Estou trabalhando em alguma lógica vetorial, então estou perguntando: posso economizar tempo do processador simplificando essa desigualdade:

distance(vector1, vector2) < distance(vector1, vector3)

Vejo que isso vector1se repete nos dois casos.

vector Filip Dimitrovski
fonte
10
Apenas uma observação rápida: seu método atual é muito legível e sua função pode ser entendida instantaneamente. Algumas dessas respostas podem realizar a tarefa solicitada, mas são muito menos claras. Isso é bom se o desempenho for essencial, mas não deixe de comentar adequadamente para explicar a perda de clareza.
Mikes
3
Para continuar o comentário do @ MikeS, o desempenho só deve ser essencial em casos como esse se você já fez uma análise ou criação de perfil e identificou essa chamada como um gargalo. A manutenção supera o desempenho bruto, se estivermos falando da diferença entre 305fps e 303fps.
Phoshi

Respostas:

24

Sim , você pode simplificar isso. Primeiro, pare de chamá-los de vetores. São pontos. Vamos chamá-los A, Be C.

Então, você quer isso:

dist(A, B) < dist(A, C)

Substitua distâncias por distâncias ao quadrado e depois por produtos pontilhados (a partir da definição do comprimento euclidiano . Substitua ACpor AB + BC(agora esses são vetores reais). Expanda, simplifique, fator:

dist(A, B)² < dist(A, C)²
dot(AB, AB) < dot(AC, AC)
dot(AB, AB) < dot(AB + BC, AB + BC)
dot(AB, AB) < dot(AB, AB) + dot(BC, BC) + 2 dot(AB, BC)
0 < dot(BC, BC) + 2 dot(AB, BC)
0 < dot(BC + 2 AB, BC)

Aí está você:

dot(AB + AC, BC) > 0

Com sua notação vetorial:

dot(v2 - v1 + v3 - v1, v3 - v2) > 0

São algumas adições e um produto de ponto em vez dos dois produtos de ponto anteriores.

sam hocevar
fonte
Você pode explicar como substituir a a + b b = a a + c c pela versão do produto escalar?
TravisG
2
@ TravisG Não tenho certeza do que você está perguntando. Se a sua pergunta é por que dist(A, B)²é a mesma dot(AB, AB), vem da própria definição do comprimento euclidiano .
Sam Hocevar
2
Claramente, isso simplifica matematicamente a equação, mas não necessariamente "economiza tempo do processador" para o OP. Isso resulta em mais complexidade e mais cálculos do que apenas remover a raiz quadrada das equações de distância originais.
Michaelhouse
1
Corrija-me se eu estiver errado, mas os dois produtos pontuais são 5 operações por produto pontual mais as duas subtrações vec3, que são um total de 16 operações, seu caminho tem 3 substrações vec3 mais uma adição que faz 12 operações mais o produto pontual faz 17.
Luis W
2
Curiosamente, o resultado é o produto escalar das duas diagonais opostas de um paralelogramo. Mas isso é irrelevante. O que eu queria dizer é que não há muito a ganhar com essa simplificação completa ; como outros já mencionaram, é uma quantia decente ofuscar ou complicar o que você está realmente tentando calcular. No entanto, você definitivamente deseja usar o primeiro passo. Evitar uma raiz quadrada desnecessária sempre vale a pena. Apenas comparar os Quadrados das distâncias é o mesmo, pois a distância é positiva definida, mesmo no plano complexo.
precisa saber é o seguinte
16

Sim. Supondo que sua distancefunção use uma raiz quadrada, você pode simplificar isso removendo a raiz quadrada.

Ao tentar encontrar a maior (ou menor) distância, x^2 > y^2ainda é válido para x > y.

No entanto, outras tentativas de simplificar matematicamente a equação provavelmente não fazem sentido. A distância entre vector1e vector2não é a mesma que distância entre vector1e vector3. Embora a equação possa ser simplificada matematicamente, como mostra a resposta de Sam , a forma em que está atualmente é provavelmente tão simples quanto você obterá da perspectiva de uso do processador.

MichaelHouse
fonte
Não tenho representante suficiente, mas, como fundamentalmente incorreto, acredito: "posso economizar tempo de processador simplificando essa desigualdade?" A resposta é sim.
Eu estou tão confuso
A resposta é apenas sim se a equação da distância estiver usando uma raiz quadrada. O que eu mencionei.
MichaelHouse
Ponto válido, eu retiraria minha declaração. No entanto, é 99% garantido que o usuário significa sqrt distância euclidiana (soma (diferenças dimensionais quadrado))
im tão confuso
@imsoconfused Fair bastante, eu mudei a ordem da minha resposta para indicar o cenário mais provável (99%) primeiro.
MichaelHouse
2
Sim, minha experiência é quando você lida com esse tipo de coisa, uma função DistanceSquared é muito útil. É igualmente claro e evita a operação cara do sqrt.
Loren Pechtel
0

Algumas matemáticas podem ajudar.

O que você está tentando fazer é:

<v1, v2> < <v1, v3> =>
sqrt((y2-y1)^2+(x2-x1)^2) < sqrt((y3-y1)^2+(x3-x1)^2) =>
y2^2 - 2*y2y1 + y1^2 + x2^2 - 2*x2x1 + x1^2 < y3^2 - 2*y3y1 + y1^2 + x3^2 - 2*x3x1 + x1^2

Pelo que você pode remover variáveis ​​repetidas e agrupar outras. A operação que você precisa verificar é:

y3^2 - y2^2 - 2*y1(y3-y2) + x3^2 - x2^2 - 2*x1(x3-x2) > 0

Espero que ajude.

j4nSolo
fonte
-1

A verdadeira questão parece ser como reduzir a computação para determinar o objeto mais próximo?

A otimização disso geralmente é feita em jogos, embora com todas as otimizações deva ser guiada por perfil e, muitas vezes, não simplifica as coisas.

A maneira de evitar cálculos de distância desnecessários para determinar a coisa mais próxima - ou todas as coisas dentro de um determinado intervalo - é usar um índice espacial, por exemplo, uma octree .

Isso só compensa se houver um grande número de objetos. Por apenas três objetos, é improvável que valha a pena e certamente não simplifica o código.

Vai
fonte
4
Eu acho que a pergunta real é bastante direta, e esta resposta não aborda isso. Se você quiser especular sobre as questões mais profundas e não declaradas do OP, isso deve ser feito como um comentário, se você realmente não responder à pergunta.
Estou com o voto negativo porque invocar uma possível otimização prematura não é uma resposta para um problema em que a otimização explícita não prejudica a legibilidade, a manutenção do código nem incentiva práticas obscuras. Quando você pode escrever um código simples e otimizado, por que não fazê-lo? Certamente não custa nada, mesmo se você tiver um plano de nível superior (nenhum desenvolvedor de jogos jamais recusará alguns microssegundos extras por quadro, especialmente nos consoles).
Teodron #
@teodron: "Quando você pode escrever um código simples e otimizado, por que não fazê-lo?" - Porque o OP (e agora nós) passou um tempo não negligenciável otimizando algo que pode não lhe proporcionar nenhum benefício.
BlueRaja # Danny Pflughoeft
@ BlueRaja-DannyPflughoeft Eu concordo que isso seja menor (portanto, otimização insignificante se usada para algumas centenas de chamadas por quadro, mas se o fator de magnitude aumentar para milhares, as coisas certamente mudam). No entanto, somos todos livres para não perder tempo tentando responder / otimizar algo que consideramos inviável. O OP pediu uma coisa: as pessoas supuseram que o OP não estava ciente das estratégias e práticas de criação de perfil de nível superior. Pessoalmente, prefiro fazer essas observações nos comentários, não nas respostas. Desculpe por ser tão detalhado :(.
teodron
-3

depende de qual é a saída da distância (v1, v2)

se for um decimal (flutuante ou duplo) sobre um vetor, é provável que a distância percorrida seja muito mais rápida

RoughPlace
fonte
5
Não vejo o que isso floattem a ver com nada.
Michaelhouse
i significou um flutuador sobre outro vector só não explicou muito bem (e eu acho que você sabia disso)
RoughPlace
5
Eu não estava intencionalmente mal-entendido. Ainda não tenho certeza do que você quer dizer. Não sei por que uma função de distância retornaria um vetor.
Michaelhouse