Comment puis-je vérifier si deux segments se croisent ?

Question

Comment puis-je vérifier si 2 segments s'intersectent?

J'ai les données suivantes:

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ] 

Je dois écrire un petit algorithme en Python pour détecter si les 2 lignes s'intersectent.

Answer 1

L'utilisateur @i_4_got pointe vers cette page avec une solution très efficace en Python. Je le reproduis ici pour plus de commodité (car cela m'aurait rendu heureux de l'avoir ici) :

def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Renvoie vrai si les segments de droite AB et CD s'intersectent
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

Answer 2

L'équation d'une droite est :

f(x) = A*x + b = y

Pour un segment, c'est exactement la même chose, sauf que x est inclus dans un intervalle I.

Si vous avez deux segments, définis comme suit :

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

L'abscisse Xa du point d'intersection potentiel (Xa,Ya) doit être contenue dans les deux intervalles I1 et I2, définis comme suit :

I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]

Et on pourrait dire que Xa est inclus dans :

Ia = [max( min(X1,X2), min(X3,X4) ),
      min( max(X1,X2), max(X3,X4) )]

Maintenant, nous devons vérifier que cet intervalle Ia existe :

if (max(X1,X2) < min(X3,X4)):
    return False  # Il n'y a pas d'abscisses mutuelles

Ainsi, nous avons deux formules de droite et un intervalle commun. Vos formules de droite sont :

f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y

Comme nous avons deux points par segment, nous sommes capables de déterminer A1, A2, b1 et b2 :

A1 = (Y1-Y2)/(X1-X2)  # Faites attention à ne pas diviser par zéro
A2 = (Y3-Y4)/(X3-X4)  # Faites attention à ne pas diviser par zéro
b1 = Y1-A1*X1 = Y2-A1*X2
b2 = Y3-A2*X3 = Y4-A2*X4

Si les segments sont parallèles, alors A1 == A2 :

if (A1 == A2):
    return False  # Segments parallèles

Un point (Xa,Ya) appartenant aux deux droites doit vérifier les deux formules f1 et f2 :

Ya = A1 * Xa + b1
Ya = A2 * Xa + b2
A1 * Xa + b1 = A2 * Xa + b2
Xa = (b2 - b1) / (A1 - A2)   # Une fois de plus, faites attention à ne pas diviser par zéro

La dernière chose à faire est de vérifier que Xa est inclus dans Ia :

if ( (Xa < max( min(X1,X2), min(X3,X4) )) or
     (Xa > min( max(X1,X2), max(X3,X4) )) ):
    return False  # L'intersection est hors limites
else:
    return True

En plus de cela, vous pouvez vérifier au démarrage que deux des quatre points fournis ne sont pas égaux pour éviter tous ces tests.

Answer 3

Vous n'avez pas besoin de calculer exactement où les segments s'intersectent, mais seulement de comprendre s'ils s'intersectent. Cela simplifiera la solution.

L'idée est de traiter un segment comme l'"ancre" et de séparer le deuxième segment en 2 points.
Maintenant, vous devrez trouver la position relative de chaque point par rapport au segment "ancré" (À gauche, À droite ou Colinéaire).
Après avoir fait cela pour les deux points, vérifiez qu'un des points est À gauche et l'autre est À droite (ou peut-être inclure la position colinéaire, si vous souhaitez inclure des intersections impropres également).

Vous devez ensuite répéter le processus avec les rôles des segments ancré et séparé.

Une intersection existe si, et seulement si, un des points est À gauche et l'autre est À droite. Voir ce lien pour une explication plus détaillée avec des images d'exemple pour chaque cas possible.

Mettre en œuvre une telle méthode sera bien plus facile que d'implémenter réellement une méthode qui trouve le point d'intersection (étant donné les nombreux cas exceptionnels que vous devrez également gérer).

Mise à jour

Les fonctions suivantes devraient illustrer l'idée (source : Géométrie Computationnelle en C).
Remarque : Cet exemple suppose l'utilisation de nombres entiers. Si vous utilisez une représentation en virgule flottante à la place (ce qui pourrait évidemment compliquer les choses), alors vous devriez déterminer une valeur epsilon pour indiquer l'"égalité" (surtout pour l'évaluation de IsCollinear).

// les points "a" et "b" forment le segment ancré.
// le point "c" est le point évalué
bool IsOnLeft(Point a, Point b, Point c)
{
     return Area2(a, b, c) > 0;
}

bool IsOnRight(Point a, Point b, Point c)
{
     return Area2(a, b, c) < 0;
}

bool IsCollinear(Point a, Point b, Point c)
{
     return Area2(a, b, c) == 0;
}

// calcule la taille du triangle (formé par le segment "ancré" et le point supplémentaire)
int Area2(Point a, Point b, Point c)
{
     return (b.X - a.X) * (c.Y - a.Y) -
            (c.X - a.X) * (b.Y - a.Y);
}

Bien sûr, lors de l'utilisation de ces fonctions, il faut se rappeler de vérifier que chaque segment se situe "entre" l'autre segment (puisqu'il s'agit de segments finis, et non de lignes infinies).

De plus, en utilisant ces fonctions, vous pouvez comprendre si vous avez une intersection correcte ou incorrecte.

• Correcte : Il n'y a pas de points colinéaires. Les segments se croisent "de côté à côté".
• Incorrecte : Un segment "effleure" seulement l'autre (au moins un des points est colinéaire au segment ancré).

Answer 4

Supposons que les deux segments aient les extrémités A, B et C, D. La manière numériquement robuste de déterminer l'intersection est de vérifier le signe des quatre déterminants :

| Ax-Cx  Bx-Cx |    | Ax-Dx  Bx-Dx |
| Ay-Cy  By-Cy |    | Ay-Dy  By-Dy |

| Cx-Ax  Dx-Ax |    | Cx-Bx  Dx-Bx |
| Cy-Ay  Dy-Ay |    | Cy-By  Dy-By |

Pour l'intersection, chaque déterminant à gauche doit avoir le signe opposé de celui à droite, mais il n'y a pas besoin qu'il y ait de relation entre les deux droites. Vous vérifiez essentiellement chaque point d'un segment par rapport à l'autre segment pour vous assurer qu'ils se trouvent de chaque côté de la droite définie par l'autre segment.

Voir ici : http://www.cs.cmu.edu/~quake/robust.html

Answer 5

Basé sur Liran et Grumdrig d'excellentes réponses voici un code Python complet pour vérifier si des segments fermés s'intersectent. Fonctionne pour des segments colinéaires, des segments parallèles à l'axe Y, des segments dégénérés (le diable est dans les détails). Suppose des coordonnées entières. Les coordonnées en nombres flottants nécessitent une modification du test d'égalité des points.

def côté(a,b,c):
    """ Renvoie une position du point c par rapport à la ligne passant par a et b
        Il est attendu que les points a, b soient différents
    """
    d = (c[1]-a[1])*(b[0]-a[0]) - (b[1]-a[1])*(c[0]-a[0])
    return 1 if d > 0 else (-1 if d < 0 else 0)

def est_point_dans_segment_fermé(a, b, c):
    """ Renvoie True si c est à l'intérieur du segment fermé, False sinon.
        Il est attendu que a, b, c soient colinéaires
    """
    if a[0] < b[0]:
        return a[0] <= c[0] and c[0] <= b[0]
    if b[0] < a[0]:
        return b[0] <= c[0] and c[0] <= a[0]

    if a[1] < b[1]:
        return a[1] <= c[1] and c[1] <= b[1]
    if b[1] < a[1]:
        return b[1] <= c[1] and c[1] <= a[1]

    return a[0] == c[0] and a[1] == c[1]

#
def segment_fermé_s'intersectent(a,b,c,d):
    """ Vérifie si les segments fermés a, b, c, d s'intersectent.
    """
    if a == b:
        return a == c or a == d
    if c == d:
        return c == a or c == b

    s1 = côté(a,b,c)
    s2 = côté(a,b,d)

    # Tous les points sont colinéaires
    if s1 == 0 and s2 == 0:
        return \
            est_point_dans_segment_fermé(a, b, c) or est_point_dans_segment_fermé(a, b, d) or \
            est_point_dans_segment_fermé(c, d, a) or est_point_dans_segment_fermé(c, d, b)

    # Pas de contact et du même côté
    if s1 and s1 == s2:
        return False

    s1 = côté(c,d,a)
    s2 = côté(c,d,b)

    # Pas de contact et du même côté
    if s1 and s1 == s2:
        return False

    return True