Comment fonctionne cette ligne-intersection?

Question

Je construis un jeu d'astéroïdes pour une assignation de classe. Pour finir, j'ai besoin d'un algorithme/code d'intersection de lignes . J'en ai trouvé un qui fonctionne, mais je ne comprends pas les maths derrière ça. Comment cela marche-t-il?

point* inter(point p1, point p2, point p3, point p4) 
{ 
point* r; 

//p1-p2 is the first edge. 
//p3-p4 is the second edge. 
r = new point; 
float x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x; 
float y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y; 

//I do not understand what this d represents. 
float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); 
// If d is zero, there is no intersection 
if (d == 0) return NULL; 

// I do not understand what this pre and pos means and 
// how it's used to get the x and y of the intersection 
float pre = (x1*y2 - y1*x2), pos = (x3*y4 - y3*x4); 
float x = (pre * (x3 - x4) - (x1 - x2) * pos)/d; 
float y = (pre * (y3 - y4) - (y1 - y2) * pos)/d; 

// Check if the x and y coordinates are within both lines 
if (x < min(x1, x2) || x > max(x1, x2) || 
     x < min(x3, x4) || x > max(x3, x4)) return NULL; 
if (y < min(y1, y2) || y > max(y1, y2) || 
     y < min(y3, y4) || y > max(y3, y4)) return NULL; 

cout << "Inter X : " << x << endl; 
cout << "Inter Y : " << y << endl; 

// Return the point of intersection 
r->x = x; 
r->y = y; 
return r; 
} 

Answer 1

point* inter(point p1, point p2, point p3, point p4) 
{ 
    point* r; 

    //p1-p2 is the first edge. 
    //p3-p4 is the second edge. 
    r = new point; 

Comme d'autres l'ont déjà commenté, ce qui précède peut/va fuite de mémoire. Mieux vaut utiliser un pointeur intelligent, par ex. std::auto_ptr.

Vous devez d'abord connaître le produit scalaire de deux vecteurs. Soit X et Y des vecteurs de longueur 1 dans les directions respectivement de l'axe des abscisses et de l'axe des ordonnées. Puis définissez X * X = 1, Y * Y = 1, et X * Y = 0, qui est une sorte de multiplication (ou juste une opération) donnant la longueur de la projection d'un vecteur sur l'autre, fois la longueur de l'autre (ou en d'autres termes, le produit des longueurs des vecteurs fois le cosinus de l'angle entre eux). Alors si deux vecteurs a et b sont a = ax * X + ay * Y et b = bx * X + par * Y, alors a * b = ax * bx + ay * par, car ces termes avec X * Y sont nuls , décrochage.

Et étonnamment que la généralisation, on obtient les longueurs des vecteurs fois cosinus de l'angle entre les deux vecteurs dans des directions pour arbitraires, ce qui signifie pour les vecteurs parallèles, le produit de leurs longueurs, et des vecteurs perpendiculaires, 0. :-)

Soit edge1 = p1-p2 et edge2 = p3-p4. Alors le ci-dessus calcule edge1.x * edge2.y - bord1.y * bord2.x = [bord1.x, bord1.y] * [bord2.y, -edge2.x]. Le dernier vecteur est bordé de 90 degrés. Maintenant, si ce bord tourné2 est perpendiculaire à edge1, edge1 et edge2 doivent être parallèles et ne peuvent pas se croiser. Et dans ce cas ce produit scalaire est 0.

// If d is zero, there is no intersection 
    if (d == 0) return NULL; 

    // I do not understand what this pre and pos means and 
    // how it's used to get the x and y of the intersection 
    float pre = (x1*y2 - y1*x2), pos = (x3*y4 - y3*x4); 
    float x = (pre * (x3 - x4) - (x1 - x2) * pos)/d; 
    float y = (pre * (y3 - y4) - (y1 - y2) * pos)/d; 


    // Check if the x and y coordinates are within both lines 
    if (x < min(x1, x2) || x > max(x1, x2) || 
      x < min(x3, x4) || x > max(x3, x4)) return NULL; 
    if (y < min(y1, y2) || y > max(y1, y2) || 
      y < min(y3, y4) || y > max(y3, y4)) return NULL; 

    cout << "Inter X : " << x << endl; 
    cout << "Inter Y : " << y << endl; 

    // Return the point of intersection 
    r->x = x; 
    r->y = y; 
    return r; 
} 

Oh cher. Je n'ai pas envie d'analyser ça ... Mais si ça marche, alors c'est la résolution de deux équations dans deux inconnues pour déterminer le point d'intersection des lignes infinies à travers les arêtes, puis vérifier si ce point d'intersection est dans les limites.

Vive & HTH,

Answer 2

Ils sont determinants.

Answer 3

Vous calculez la pente d'une ligne par rapport à (un système de coordonnées parallèle à) l'autre ligne. Le d est zéro, ils sont parallèles. Ensuite, il calcule l'intersection dans ce système de coordonnées, puis le ramène au système de coordonnées de base.

Answer 4

La détermination de l'intersection de deux lignes dans un plan bidimensionnel, le cas échéant (elles pourraient être parallèles) est un problème mathématique classique. L'algorithme que vous avez trouvé est basé sur la résolution d'un système avec deux équations linéaires. Ceci est fait en calculant le déterminant (d). Si zéro, alors les lignes sont parallèles. Sinon, le point d'intersection est calculé.

Voir par exemple ce tutoriel pour obtenir une description détaillée de la formule: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2