Introdução
Muitas vezes, ao desenvolver jogos, torna-se necessário encontrar o ponto de intersecção de linhas, segmentos, raios, etc. Como implementar isso da maneira mais simples possível, neste artigo.
Métodos populares e suas críticas
Talvez muitos se lembrem de um método da álgebra escolar - fazer equações de duas linhas retas, igualar seus lados direitos, encontrar x e substituí-lo na equação de uma linha reta para encontrar y ( mais detalhes aqui ).
No entanto, este método torna-se bastante complicado ao escrever código (talvez seja por isso que você está lendo este artigo agora), além disso, não é universal: se uma das retas for paralela ao eixo Y, obteremos uma divisão por erro zero ao calcular a inclinação, e temos que registre um código para este caso; se duas linhas são paralelas, você precisa mexer no processamento desse caso também. Esse código se torna longo e feio.
Em busca de uma solução mais elegante para este problema, me deparei com algumas maneiras muito interessantes com base na multiplicação de vetores (habr.com/ru/post/267037 ) e ray casting ( ru.wikipedia.org/wiki/Ray_casting#Concept ). Mas, em minha opinião, eles são excessivamente complexos do ponto de vista computacional. Portanto, apresento a sua atenção (e crítica) o meu método.
O meu caminho
Tarefa
As coordenadas de dois segmentos são fornecidas. Você precisa descobrir se os segmentos se cruzam e, em caso afirmativo, em que ponto. Para isso, escreveremos uma função.
Decisão
Legenda para evitar mal-entendidos: a - vetor a, a (y) - projeção do vetor a no eixo Y, a {x1, y1} - vetor a, especificado pelas coordenadas x1, y1.
Vamos representar nossos segmentos na forma de dois vetores: a {x2-x1; y2-y1} e b {x3-x4; y3-x4}. Observe que o vetor b está na direção oposta do que é esperado. Vamos introduzir um vetor c {x3-x1; y3-y1}. Observe que a * k + b * n = c, onde k, n são alguns coeficientes. Assim, obtemos um sistema de equações:
a (x) * k + b (x) * n = c (x)
a (y) * k + b (y) * n = c (y)
Nossa tarefa se reduz a encontrar esses coeficientes (para falar a verdade, basta encontrar apenas um).
Proponho multiplicar ambos os lados da equação inferior por q = -a (x) / a (y). Então, depois de adicionar duas equações, nos livramos imediatamente de k. Encontrar n será reduzido para resolver uma equação linear ordinária. É importante notar que n pode não ter uma solução.
O leitor atento notará que quando a (y) = 0, obtemos um erro. Vamos escrever a ramificação no estágio de encontrar a (y). Este caso é ainda mais simples, porque imediatamente obtemos uma equação com uma incógnita.
Eu recomendo tentar gerar n você mesmo, então ficará mais claro o que vem no código abaixo.
Sabendo n, você pode encontrar o ponto de interseção, para isso subtraímos o vetor b * n da coordenada do ponto (x3, y3)
Juntar as peças
float dot[2]; //
bool cross(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
float n;
if (y2 - y1 != 0) { // a(y)
float q = (x2 - x1) / (y1 - y2);
float sn = (x3 - x4) + (y3 - y4) * q; if (!sn) { return 0; } // c(x) + c(y)*q
float fn = (x3 - x1) + (y3 - y1) * q; // b(x) + b(y)*q
n = fn / sn;
}
else {
if (!(y3 - y4)) { return 0; } // b(y)
n = (y3 - y1) / (y3 - y4); // c(y)/b(y)
}
dot[0] = x3 + (x4 - x3) * n; // x3 + (-b(x))*n
dot[1] = y3 + (y4 - y3) * n; // y3 +(-b(y))*n
return 1;
}Esta função pega as coordenadas dos vértices e retorna o valor 1 se as linhas retas dos segmentos (ou seja, as linhas retas) se cruzam, caso contrário, 0. Se você precisar das coordenadas dos vértices, você pode tirá-las do array dot [].
Importante: quando você insere duas linhas coincidentes, o algoritmo não exibe nenhuma interseção. O algoritmo encontra o ponto de interseção das linhas nas quais os segmentos de linha se encontram, portanto, o ponto pode estar fora do segmento (o que você terá que verificar em seu código).
Vamos aplicar a função:
int main() {
if (cross(1,1,7,2, 7,3,5,6)) {
std::cout << dot[0] << " " << dot[1] << std::endl;
}
else {
std::cout<<"Not cross!"<<std::endl;
}
return 0;
}Posfácio
Embora eu não tenha encontrado esse método no processo de pesquisar meu problema no Google e desenvolvido o algoritmo sozinho, não pretendo ser totalmente original (e correto). Bem-vindo aos comentários!