Comment détecter l'intersection de deux segments de droite ?

Question

Comment puis-je déterminer si deux lignes se croisent ou non, et si c'est le cas, à quel point x,y ?

Answer 1

Il existe une approche intéressante de ce problème qui utilise les produits vectoriels croisés. Définissez le produit vectoriel croisé bidimensionnel v   w à être v _x   w _y    v _y   w _x .

Supposons que les deux segments de ligne partent de p a p  +  r et de q a q  +  s . Alors tout point de la première ligne est représentable comme p  +  t   r (pour un paramètre scalaire  t ) et tout point de la deuxième ligne comme q  +  u   s (pour un paramètre scalaire  u ).

Les deux lignes se croisent si on peut trouver t y u de telle sorte que :

p + t   r \= q + u   s

Traversez les deux côtés avec s en obtenant

( p + t   r ) × s \= ( q + u   s ) × s

Et comme s   s \= 0, ce qui signifie

t  ( r × s ) = ( q p ) × s

Et donc, en résolvant pour t :

t \= ( q p ) × s / ( r × s )

De la même manière, nous pouvons résoudre u :

( p + t   r ) × r \= ( q + u   s ) × r

u  ( s × r ) = ( p q ) × r

u \= ( p q ) × r / ( s × r )

Pour réduire le nombre d'étapes de calcul, il est pratique de réécrire ceci comme suit (en se rappelant que s   r \=   r   s ) :

u \= ( q p ) × r / ( r × s )

Il y a maintenant quatre cas :

1. Si r   s  = 0 et ( q    p )  r  = 0, alors les deux lignes sont colinéaires.

   Dans ce cas, exprimer les points d'extrémité du deuxième segment ( q y q  +  s ) en fonction de l'équation du premier segment de droite ( p + t r ) :

   t ₀ \= ( q p ) -  r / ( r  -  r )

   t ₁ \= ( q + s p ) -  r / ( r  -  r ) = t ₀ + s  -  r / ( r  -  r )

   Si l'intervalle entre t ₀ y t ₁ coupe l'intervalle [0, 1], alors les segments de droite sont colinéaires et se chevauchent ; sinon, ils sont colinéaires et disjoints.

   Notez que si s y r pointent dans des directions opposées, alors s  -  r < 0 et donc l'intervalle à vérifier est [ t ₁ , t ₀ ] plutôt que [ t ₀ , t ₁ ].

2. Si r   s  = 0 et ( q    p )  r   0, alors les deux lignes sont parallèles et ne se coupent pas.

3. Si r   s   0 et 0   t   1 et 0   u   1, les deux segments de droite se rencontrent au point p + t   r \= q + u   s .

4. Sinon, les deux segments de ligne ne sont pas parallèles mais ne se coupent pas.

Crédit : cette méthode est la spécialisation bidimensionnelle de l'algorithme d'intersection de lignes 3D de l'article "Intersection of two lines in three-space" de Ronald Goldman, publié dans Gemmes graphiques page 304. En trois dimensions, le cas habituel est que les lignes sont obliques (ni parallèles ni sécantes), auquel cas la méthode donne les points de plus grande proximité des deux lignes.

Answer 2

Pour information, la fonction suivante (en C) détecte les intersections de lignes et détermine le point d'intersection. Elle est basée sur un algorithme de l'ouvrage d'André LeMothe " Les astuces des gourous de la programmation des jeux sous Windows ". Ce n'est pas différent de certains algorithmes dans d'autres réponses (par exemple, celle de Gareth). LeMothe utilise ensuite la règle de Cramer (ne me demandez pas) pour résoudre les équations elles-mêmes.

Je peux attester qu'il fonctionne dans mon faible clone d'astéroïdes, et semble traiter correctement les cas limites décrits dans d'autres réponses par Elemental, Dan et Wodzu. Il est aussi probablement plus rapide que le code posté par KingNestor parce qu'il n'y a que des multiplications et des divisions, pas de racines carrées !

Je suppose qu'il y a un risque de division par zéro, mais cela n'a pas été un problème dans mon cas. C'est assez facile à modifier pour éviter le crash de toute façon.

// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines 
// intersect the intersection point may be stored in the floats i_x and i_y.
char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s1_x, s1_y, s2_x, s2_y;
    s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
    s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;

    float s, t;
    s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        // Collision detected
        if (i_x != NULL)
            *i_x = p0_x + (t * s1_x);
        if (i_y != NULL)
            *i_y = p0_y + (t * s1_y);
        return 1;
    }

    return 0; // No collision
}

BTW, je dois dire que dans le livre de LeMothe, bien qu'il ait apparemment bien compris l'algorithme, l'exemple concret qu'il montre introduit les mauvais chiffres et fait des calculs erronés. Par exemple :

(4 * (4 - 1) + 12 * (7 - 1)) / (17 * 4 + 12 * 10)

\= 844/0.88

\= 0.44

Cela m'a perturbé pendant heures . :(

Answer 3

Le problème se réduit à cette question : Est-ce que deux lignes de A à B et de C à D se croisent ? On peut alors la poser quatre fois (entre la ligne et chacun des quatre côtés du rectangle).

Voici les mathématiques vectorielles pour le faire. Je suppose que la ligne de A à B est la ligne en question et que la ligne de C à D est l'une des lignes du rectangle. Ma notation est la suivante Ax est la "coordonnée x de A" et Cy est la "coordonnée y de C". Et " * " signifie produit scalaire, donc par exemple A*B = Ax*Bx + Ay*By .

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy ) 
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

Ce site h Le numéro est la clé. Si h est entre 0 y 1 les lignes se croisent, sinon elles ne se croisent pas. Si F*P est égal à zéro, vous ne pouvez bien sûr pas faire le calcul, mais dans ce cas, les lignes sont parallèles et ne se croisent donc que dans les cas évidents.

Le point exact d'intersection est C + F*h .

Plus de plaisir :

Si h es exactement 0 o 1 les lignes se touchent à un point final. Vous pouvez considérer ce point comme une "intersection" ou non, comme bon vous semble.

Plus précisément, h est le nombre de fois que vous devez multiplier la longueur de la ligne afin de toucher exactement l'autre ligne.

Par conséquent, si h<0 cela signifie que la ligne du rectangle est "derrière" la ligne donnée (la "direction" étant "de A à B"), et si h>1 la ligne du rectangle est "devant" la ligne donnée.

Dérivation :

A et C sont des vecteurs qui pointent vers le début de la ligne ; E et F sont les vecteurs des extrémités de A et C qui forment la ligne.

Pour toute paire de lignes non parallèles dans le plan, il doit y avoir exactement une paire de scalaires. g y h de sorte que cette équation tienne :

A + E*g = C + F*h

Pourquoi ? Parce que deux lignes non parallèles doivent se croiser, ce qui signifie que vous pouvez mettre à l'échelle les deux lignes d'une certaine quantité chacune et les faire se toucher.

( Au premier abord, cela ressemble à une seule équation avec deux inconnues ! Mais ce n'est pas le cas si l'on considère qu'il s'agit d'une équation vectorielle en 2D, ce qui signifie qu'il s'agit en réalité d'une paire d'équations en x y y .)

Nous devons éliminer une de ces variables. Un moyen facile est de rendre la E terme zéro. Pour cela, il faut prendre le produit scalaire des deux côtés de l'équation en utilisant un vecteur dont le point est nul avec E. Ce vecteur est appelé P ci-dessus, et j'ai fait la transformation évidente de E.

Vous avez maintenant :

A*P = C*P + F*P*h
(A-C)*P = (F*P)*h
( (A-C)*P ) / (F*P) = h

Answer 4

J'ai essayé de mettre en œuvre l'algorithme si élégamment décrit par Jason ci-dessus ; malheureusement, en travaillant sur les mathématiques dans le débogage, j'ai trouvé de nombreux cas pour lesquels il ne fonctionne pas.

Par exemple, les points A(10,10) B(20,20) C(10,1) D(1,10) donnent h=.5 et pourtant il est clair, à l'examen, que ces segments ne sont pas du tout proches les uns des autres.

Le graphique montre clairement que le critère 0 < h < 1 indique seulement que le point d'interception se trouverait sur CD s'il existait, mais ne dit rien sur le fait que ce point se trouve sur AB. Pour s'assurer qu'il y a un point d'intersection, il faut faire le calcul symétrique pour la variable g et le critère d'interception est : 0 < g < 1 ET 0 < h < 1

Answer 5

Voici une amélioration de la réponse de Gavin. La solution de marcp est également similaire, mais aucun des deux ne reporte la division.

Il s'agit en fait d'une application pratique de la réponse de Gareth Rees, car l'équivalent du produit vectoriel en 2D est le produit perp-dot, que ce code utilise à trois reprises. En passant à la 3D et en utilisant le produit en croix, en interpolant à la fois s et t à la fin, on obtient les deux points les plus proches entre les lignes en 3D. Bref, la solution 2D :

int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
    s10_x = p1_x - p0_x;
    s10_y = p1_y - p0_y;
    s32_x = p3_x - p2_x;
    s32_y = p3_y - p2_y;

    denom = s10_x * s32_y - s32_x * s10_y;
    if (denom == 0)
        return 0; // Collinear
    bool denomPositive = denom > 0;

    s02_x = p0_x - p2_x;
    s02_y = p0_y - p2_y;
    s_numer = s10_x * s02_y - s10_y * s02_x;
    if ((s_numer < 0) == denomPositive)
        return 0; // No collision

    t_numer = s32_x * s02_y - s32_y * s02_x;
    if ((t_numer < 0) == denomPositive)
        return 0; // No collision

    if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
        return 0; // No collision
    // Collision detected
    t = t_numer / denom;
    if (i_x != NULL)
        *i_x = p0_x + (t * s10_x);
    if (i_y != NULL)
        *i_y = p0_y + (t * s10_y);

    return 1;
}

En fait, il reporte la division au dernier moment et déplace la plupart des tests jusqu'à ce que certains calculs soient effectués, ce qui ajoute des sorties anticipées. Enfin, il évite également le cas de la division par zéro qui se produit lorsque les lignes sont parallèles.

Vous pourriez également envisager d'utiliser un test epsilon plutôt qu'une comparaison par rapport à zéro. Les lignes qui sont extrêmement proches du parallèle peuvent produire des résultats légèrement erronés. Il ne s'agit pas d'un bogue, mais d'une limitation des calculs en virgule flottante.