Recherche du point d'intersection de deux lignes (et segments de ligne)

introduction

Assez souvent, lors du développement de jeux, il devient nécessaire de trouver le point d'intersection de lignes, segments, rayons, etc. Comment implémenter cela de la manière la plus simple possible, dans cet article.

Méthodes populaires et leurs critiques

Peut-être que beaucoup se souviendront d'un moyen de l'algèbre scolaire - faire des équations de deux lignes droites, assimiler leurs côtés droits, trouver x et le remplacer dans l'équation d'une ligne droite pour trouver y ( Plus de détails ici ).



Cependant, cette méthode devient assez lourde lors de l'écriture de code (c'est peut-être pour cela que vous lisez cet article maintenant), de plus, elle n'est pas universelle: si l'une des droites est parallèle à l'axe Y, nous obtiendrons une division par erreur zéro lors du calcul de la pente, et nous devons enregistrer un code pour ce cas; si deux lignes sont parallèles, vous devez également bricoler le traitement de ce cas. Un tel code devient long et laid.



À la recherche d'une solution plus élégante à ce problème, je suis tombé sur des moyens très intéressants basés sur la multiplication vectorielle (habr.com/ru/post/267037 ) et la diffusion de rayons ( ru.wikipedia.org/wiki/Ray_casting#Concept ). Mais à mon avis, ils sont inutilement complexes en termes de calcul. Par conséquent, je présente à votre attention (et critique) ma méthode.

Mon chemin

Tâche

Les coordonnées de deux segments sont données. Vous devez savoir si les segments se croisent, et si oui, à quel point. Pour cela, nous écrirons une fonction.

Décision

Légende pour éviter les malentendus: a - vecteur a, a (y) - projection du vecteur a sur l'axe Y, a {x1, y1} - vecteur a, spécifié par les coordonnées x1, y1.



Représentons nos segments sous la forme de deux vecteurs: a {x2-x1; y2-y1} et b {x3-x4; y3-x4}. Notez que le vecteur b est dans la direction opposée à ce qui est attendu. Introduisons un vecteur c {x3-x1; y3-y1}. Notez que a * k + b * n = c, où k, n sont des coefficients. Ainsi, nous obtenons un système d'équations:



a (x) * k + b (x) * n = c (x)

a (y) * k + b (y) * n = c (y)

Notre tâche se réduit à trouver ces coefficients (à vrai dire, il suffit de n'en trouver qu'un).



Je propose de multiplier les deux côtés de l'équation inférieure par q = -a (x) / a (y). Donc, après avoir ajouté deux équations, nous nous débarrassons immédiatement de k. Trouver n se réduit à résoudre une équation linéaire ordinaire. Il est important de noter que n peut ne pas avoir de solution.



Le lecteur attentif remarquera que lorsque a (y) = 0, nous obtenons une erreur. Écrivons le branchement au stade de la recherche de a (y). Ce cas est encore plus simple, car nous obtenons immédiatement une équation avec une inconnue.



Je recommande d'essayer d'imprimer n vous-même, de sorte que ce qui provient du code ci-dessous sera plus clair.



Connaissant n, vous pouvez trouver le point d'intersection, pour cela nous soustrayons le vecteur b * n de la coordonnée du point (x3, y3)

Mettre ensemble

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;
}

Cette fonction prend les coordonnées des sommets et renvoie la valeur 1 si les lignes droites des segments (c'est-à-dire les droites) se croisent, sinon 0. Si vous avez besoin des coordonnées des sommets, vous pouvez les prendre dans le tableau dot [].



Important: lors de l'introduction de deux lignes coïncidentes, l'algorithme n'affiche aucune intersection. L'algorithme trouve le point d'intersection des lignes sur lesquelles se trouvent les segments de ligne, de sorte que le point peut être en dehors du segment (que vous devrez vérifier dans votre code).



Appliquons la fonction:

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;
}

Épilogue

Bien que je ne sois pas tombé sur cette méthode en train de googler mon problème et de développer moi-même l'algorithme, je ne prétends pas être complètement original (et correct). Alors bienvenue dans les commentaires!