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

Il existe une belle approche à ce problème qui utilise des produits croisés vectoriels. Définissez le produit vectoriel vectoriel bidimensionnel v  ×  w comme étant v _x  w _y  -  v _y  w _x .

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

Les deux droites se croisent si nous pouvons trouver t et u tels que:

p + t  r = q + u  s

Traversez les deux côtés avec s ,

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

Et puisque s  ×  s = 0, cela signifie

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

Et donc, résoudre pour t :

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

De la même manière, nous pouvons résoudre pour 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 souvenant que s  ×  r = -  r  ×  s ):

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

Maintenant, il y a quatre cas:

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

   Dans ce cas, exprimez les points d'extrémité du deuxième segment ( q et q  +  s ) en termes d'équation du premier segment de ligne ( 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 ₀ et t ₁ croise l'intervalle [0, 1] alors les segments de ligne sont colinéaires et se chevauchent; sinon, ils sont colinéaires et disjoints.

   Notez que si s et 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 droites sont parallèles et sans intersection.

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 Graphics Gems , page 304. En trois dimensions, le cas habituel est que les lignes sont asymétriques (ni parallèles ni entrecroisées) auquel cas la méthode donne les points d'approche les plus proches des deux lignes.

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

Je peux attester que cela fonctionne dans mon clone d'astéroïdes faibles et semble traiter correctement les cas marginaux décrits dans d'autres réponses par Elemental, Dan et Wodzu. Il est également probablement plus rapide que le code publié par KingNestor, car tout est multiplication et division, pas de racines carrées!

Je suppose qu'il y a un potentiel de division par zéro là-dedans, même si cela n'a pas été un problème dans mon cas. 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 le bon algorithme, l'exemple concret qu'il montre des prises avec de mauvais nombres 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 dérouté pendant des heures . :(

Le problème se résume à cette question: deux lignes de A à B et de C à D se coupent-elles? Ensuite, vous pouvez le demander 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 la ligne de C à D est l'une des lignes rectangulaires. Ma notation est Axla "coordonnée x de A" et Cyla "coordonnée y de C." Et " *" signifie produit scalaire, 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 hnuméro est la clé. Si hest entre 0et 1, les lignes se coupent, sinon elles ne le font pas. Si F*Pest nul, vous ne pouvez bien sûr pas faire le calcul, mais dans ce cas les lignes sont parallèles et ne se coupent donc que dans les cas évidents.

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

Plus amusant:

Si hest exactement 0 ou 1les lignes se touchent à un point final. Vous pouvez considérer cela comme une "intersection" ou non comme bon vous semble.

Plus précisément, hc'est combien vous devez multiplier la longueur de la ligne pour toucher exactement l'autre ligne.

Par conséquent, Si h<0, cela signifie que la ligne rectangle est "derrière" la ligne donnée (avec "direction" étant "de A à B"), et si h>1la ligne rectangle est "en face" de 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 deux lignes non parallèles dans le plan, il doit y avoir exactement une paire de scalaires get htelle que cette équation soit vraie:

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é et vous toucher.

( Au début, cela ressemble à une seule équation avec deux inconnues! Mais ce n'est pas quand vous considérez qu'il s'agit d'une équation vectorielle 2D, ce qui signifie qu'il s'agit vraiment d'une paire d'équations dans xet y.)

Nous devons éliminer l'une de ces variables. Un moyen simple est de rendre le Eterme zéro. Pour ce faire, prenez le produit scalaire des deux côtés de l'équation en utilisant un vecteur qui pointera à zéro avec E. Ce vecteur que j'ai appelé Pci-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

J'ai essayé d'implémenter l'algorithme si élégamment décrit par Jason ci-dessus; malheureusement, tout en travaillant bien que les mathématiques dans le débogage, j'ai trouvé de nombreux cas pour lesquels cela ne fonctionne pas.

Par exemple, considérons les points A (10,10) B (20,20) C (10,1) D (1,10) donne h = 0,5 et pourtant il est clair en examinant que ces segments ne sont nulle part près de chacun autre.

La représentation graphique de ceci montre clairement que les critères 0 <h <1 indiquent seulement que le point d'interception se situerait sur CD s'il existait, mais ne dit rien de si ce point se trouve sur AB. Pour vous assurer qu'il existe un point de croisement, vous devez effectuer le calcul symétrique pour la variable g et l'exigence d'interception est: 0 <g <1 ET 0 <h <1

Voici une amélioration de la réponse de Gavin. La solution de Marcp est également similaire, mais aucune ne retarde la division.

Cela s'avère en fait être une application pratique de la réponse de Gareth Rees également, car l'équivalent du produit croisé en 2D est le produit perp-dot, ce dont ce code utilise trois. Passer à la 3D et utiliser le produit croisé, interpoler à la fois s et t à la fin, entraîne les deux points les plus proches entre les lignes en 3D. Quoi qu'il en soit, 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;
}

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

Vous pouvez également envisager d'utiliser un test epsilon plutôt qu'une comparaison avec zéro. Les lignes extrêmement proches de la parallèle peuvent produire des résultats légèrement décalés. Ce n'est pas un bug, c'est une limitation avec les mathématiques à virgule flottante.

Question C: Comment détectez-vous si deux segments de ligne se croisent ou non?

J'ai cherché le même sujet et je n'étais pas satisfait des réponses. J'ai donc écrit un article qui explique très en détail comment vérifier si deux segments de ligne se croisent avec beaucoup d'images. Il existe un code Java complet (et testé).

Voici l'article, rogné aux parties les plus importantes:

L'algorithme, qui vérifie si le segment de ligne a croise le segment de ligne b, ressemble à ceci:

Que sont les boîtes englobantes? Voici deux boîtes englobantes de deux segments de ligne:

Si les deux boîtes englobantes ont une intersection, vous déplacez le segment de ligne a de sorte qu'un point soit à (0 | 0). Vous avez maintenant une ligne passant par l'origine définie par a. Maintenant, déplacez le segment de ligne b de la même manière et vérifiez si les nouveaux points du segment de ligne b se trouvent de différents côtés de la ligne a. Si tel est le cas, vérifiez-le dans l'autre sens. Si c'est également le cas, les segments de ligne se coupent. Sinon, ils ne se croisent pas.

Question A: Où se croisent deux segments de ligne?

Vous savez que deux segments de droite a et b se coupent. Si vous ne le savez pas, vérifiez-le avec les outils que je vous ai fournis dans la "Question C".

Vous pouvez maintenant passer en revue certains cas et obtenir la solution avec des mathématiques de 7e année (voir code et exemple interactif ).

Question B: Comment détectez-vous si deux lignes se croisent ou non?

Disons que votre point A = (x1, y1), le point B = (x2, y2), C = (x_3, y_3), D = (x_4, y_4). Votre première ligne est définie par AB (avec A! = B), et votre seconde par CD (avec C! = D).

function doLinesIntersect(AB, CD) {
    if (x1 == x2) {
        return !(x3 == x4 && x1 != x3);
    } else if (x3 == x4) {
        return true;
    } else {
        // Both lines are not parallel to the y-axis
        m1 = (y1-y2)/(x1-x2);
        m2 = (y3-y4)/(x3-x4);
        return m1 != m2;
    }
}

Question D: Où se croisent deux lignes?

Vérifiez avec la question B si elles se recoupent.

Les lignes a et b sont définies par deux points pour chaque ligne. Vous pouvez essentiellement appliquer la même logique que celle utilisée à la question A.

La réponse une fois acceptée ici est incorrecte (elle a depuis été refusée, alors hourra!). Il n'élimine pas correctement toutes les non-intersections. Trivialement, il peut sembler fonctionner, mais il peut échouer, en particulier dans le cas où 0 et 1 sont considérés comme valides pour h.

Considérez le cas suivant:

Lignes à (4,1) - (5,1) et (0,0) - (0,2)

Ce sont des lignes perpendiculaires qui ne se chevauchent clairement pas.

A = (4,1)
B = (5,1)
C = (0,0)
D = (0,2)
E = (5,1) - (4,1) = (- 1,0)
F = (0,2) - (0,0) = (0, -2)
P = (0,1)
h = ((4,1) - (0,0)) point (0,1) / ((0 , -2) point (0,1)) = 0

Selon la réponse ci-dessus, ces deux segments de ligne se rencontrent à un point final (valeurs de 0 et 1). Ce critère serait:

(0,0) + (0, -2) * 0 = (0,0)

Donc, apparemment, les deux segments de ligne se rencontrent en (0,0), qui est sur la ligne CD, mais pas sur la ligne AB. Donc, qu'est-ce qui ne va pas? La réponse est que les valeurs de 0 et 1 ne sont pas valides et seulement parfois HAPPEN pour prédire correctement l'intersection de point final. Lorsque l'extension d'une ligne (mais pas de l'autre) rencontrerait le segment de ligne, l'algorithme prédit une intersection de segments de ligne, mais ce n'est pas correct. J'imagine qu'en testant en commençant par AB vs CD puis en testant également avec CD vs AB, ce problème serait éliminé. Ce n'est que si les deux se situent entre 0 et 1 inclusivement qu'on peut dire qu'ils se coupent.

Je recommande d'utiliser la méthode des produits croisés vectoriels si vous devez prédire les points finaux.

-Dan

Version Python de la réponse d'iMalc:

def find_intersection( p0, p1, p2, p3 ) :

    s10_x = p1[0] - p0[0]
    s10_y = p1[1] - p0[1]
    s32_x = p3[0] - p2[0]
    s32_y = p3[1] - p2[1]

    denom = s10_x * s32_y - s32_x * s10_y

    if denom == 0 : return None # collinear

    denom_is_positive = denom > 0

    s02_x = p0[0] - p2[0]
    s02_y = p0[1] - p2[1]

    s_numer = s10_x * s02_y - s10_y * s02_x

    if (s_numer < 0) == denom_is_positive : return None # no collision

    t_numer = s32_x * s02_y - s32_y * s02_x

    if (t_numer < 0) == denom_is_positive : return None # no collision

    if (s_numer > denom) == denom_is_positive or (t_numer > denom) == denom_is_positive : return None # no collision


    # collision detected

    t = t_numer / denom

    intersection_point = [ p0[0] + (t * s10_x), p0[1] + (t * s10_y) ]


    return intersection_point

Trouver l'intersection correcte de deux segments de ligne est une tâche non triviale avec beaucoup de cas de bord. Voici une solution bien documentée, fonctionnelle et testée en Java.

Essentiellement, trois choses peuvent se produire lors de la recherche de l'intersection de deux segments de ligne:

1. Les segments ne se coupent pas

2. Il y a un point d'intersection unique

3. L'intersection est un autre segment

REMARQUE : dans le code, je suppose qu'un segment de ligne (x1, y1), (x2, y2) avec x1 = x2 et y1 = y2 est un segment de ligne valide. Mathématiquement parlant, un segment de ligne se compose de points distincts, mais je permets aux segments d'être des points dans cette implémentation pour être complet.

Le code est tiré de mon dépôt github

/**
 * This snippet finds the intersection of two line segments.
 * The intersection may either be empty, a single point or the
 * intersection is a subsegment there's an overlap.
 */

import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;

import java.util.ArrayList;
import java.util.List;

public class LineSegmentLineSegmentIntersection {

  // Small epsilon used for double value comparison.
  private static final double EPS = 1e-5;

  // 2D Point class.
  public static class Pt {
    double x, y;
    public Pt(double x, double y) {
      this.x = x; 
      this.y = y;
    }
    public boolean equals(Pt pt) {
      return abs(x - pt.x) < EPS && abs(y - pt.y) < EPS;
    }
  }

  // Finds the orientation of point 'c' relative to the line segment (a, b)
  // Returns  0 if all three points are collinear.
  // Returns -1 if 'c' is clockwise to segment (a, b), i.e right of line formed by the segment.
  // Returns +1 if 'c' is counter clockwise to segment (a, b), i.e left of line
  // formed by the segment.
  public static int orientation(Pt a, Pt b, Pt c) {
    double value = (b.y - a.y) * (c.x - b.x) - 
                   (b.x - a.x) * (c.y - b.y);
    if (abs(value) < EPS) return 0;
    return (value > 0) ? -1 : +1;
  }

  // Tests whether point 'c' is on the line segment (a, b).
  // Ensure first that point c is collinear to segment (a, b) and
  // then check whether c is within the rectangle formed by (a, b)
  public static boolean pointOnLine(Pt a, Pt b, Pt c) {
    return orientation(a, b, c) == 0 && 
           min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) && 
           min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
  }

  // Determines whether two segments intersect.
  public static boolean segmentsIntersect(Pt p1, Pt p2, Pt p3, Pt p4) {

    // Get the orientation of points p3 and p4 in relation
    // to the line segment (p1, p2)
    int o1 = orientation(p1, p2, p3);
    int o2 = orientation(p1, p2, p4);
    int o3 = orientation(p3, p4, p1);
    int o4 = orientation(p3, p4, p2);

    // If the points p1, p2 are on opposite sides of the infinite
    // line formed by (p3, p4) and conversly p3, p4 are on opposite
    // sides of the infinite line formed by (p1, p2) then there is
    // an intersection.
    if (o1 != o2 && o3 != o4) return true;

    // Collinear special cases (perhaps these if checks can be simplified?)
    if (o1 == 0 && pointOnLine(p1, p2, p3)) return true;
    if (o2 == 0 && pointOnLine(p1, p2, p4)) return true;
    if (o3 == 0 && pointOnLine(p3, p4, p1)) return true;
    if (o4 == 0 && pointOnLine(p3, p4, p2)) return true;

    return false;
  }

  public static List<Pt> getCommonEndpoints(Pt p1, Pt p2, Pt p3, Pt p4) {

    List<Pt> points = new ArrayList<>();

    if (p1.equals(p3)) {
      points.add(p1);
      if (p2.equals(p4)) points.add(p2);

    } else if (p1.equals(p4)) {
      points.add(p1);
      if (p2.equals(p3)) points.add(p2);

    } else if (p2.equals(p3)) {
      points.add(p2);
      if (p1.equals(p4)) points.add(p1);

    } else if (p2.equals(p4)) {
      points.add(p2);
      if (p1.equals(p3)) points.add(p1);
    }

    return points;
  }

  // Finds the intersection point(s) of two line segments. Unlike regular line 
  // segments, segments which are points (x1 = x2 and y1 = y2) are allowed.
  public static Pt[] lineSegmentLineSegmentIntersection(Pt p1, Pt p2, Pt p3, Pt p4) {

    // No intersection.
    if (!segmentsIntersect(p1, p2, p3, p4)) return new Pt[]{};

    // Both segments are a single point.
    if (p1.equals(p2) && p2.equals(p3) && p3.equals(p4))
      return new Pt[]{p1};

    List<Pt> endpoints = getCommonEndpoints(p1, p2, p3, p4);
    int n = endpoints.size();

    // One of the line segments is an intersecting single point.
    // NOTE: checking only n == 1 is insufficient to return early
    // because the solution might be a sub segment.
    boolean singleton = p1.equals(p2) || p3.equals(p4);
    if (n == 1 && singleton) return new Pt[]{endpoints.get(0)};

    // Segments are equal.
    if (n == 2) return new Pt[]{endpoints.get(0), endpoints.get(1)};

    boolean collinearSegments = (orientation(p1, p2, p3) == 0) && 
                                (orientation(p1, p2, p4) == 0);

    // The intersection will be a sub-segment of the two
    // segments since they overlap each other.
    if (collinearSegments) {

      // Segment #2 is enclosed in segment #1
      if (pointOnLine(p1, p2, p3) && pointOnLine(p1, p2, p4))
        return new Pt[]{p3, p4};

      // Segment #1 is enclosed in segment #2
      if (pointOnLine(p3, p4, p1) && pointOnLine(p3, p4, p2))
        return new Pt[]{p1, p2};

      // The subsegment is part of segment #1 and part of segment #2.
      // Find the middle points which correspond to this segment.
      Pt midPoint1 = pointOnLine(p1, p2, p3) ? p3 : p4;
      Pt midPoint2 = pointOnLine(p3, p4, p1) ? p1 : p2;

      // There is actually only one middle point!
      if (midPoint1.equals(midPoint2)) return new Pt[]{midPoint1};

      return new Pt[]{midPoint1, midPoint2};
    }

    /* Beyond this point there is a unique intersection point. */

    // Segment #1 is a vertical line.
    if (abs(p1.x - p2.x) < EPS) {
      double m = (p4.y - p3.y) / (p4.x - p3.x);
      double b = p3.y - m * p3.x;
      return new Pt[]{new Pt(p1.x, m * p1.x + b)};
    }

    // Segment #2 is a vertical line.
    if (abs(p3.x - p4.x) < EPS) {
      double m = (p2.y - p1.y) / (p2.x - p1.x);
      double b = p1.y - m * p1.x;
      return new Pt[]{new Pt(p3.x, m * p3.x + b)};
    }

    double m1 = (p2.y - p1.y) / (p2.x - p1.x);
    double m2 = (p4.y - p3.y) / (p4.x - p3.x);
    double b1 = p1.y - m1 * p1.x;
    double b2 = p3.y - m2 * p3.x;
    double x = (b2 - b1) / (m1 - m2);
    double y = (m1 * b2 - m2 * b1) / (m1 - m2);

    return new Pt[]{new Pt(x, y)};
  }

}

Voici un exemple d'utilisation simple:

  public static void main(String[] args) {

    // Segment #1 is (p1, p2), segment #2 is (p3, p4)
    Pt p1, p2, p3, p4;

    p1 = new Pt(-2, 4); p2 = new Pt(3, 3);
    p3 = new Pt(0, 0);  p4 = new Pt(2, 4);
    Pt[] points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
    Pt point = points[0];

    // Prints: (1.636, 3.273)
    System.out.printf("(%.3f, %.3f)\n", point.x, point.y);

    p1 = new Pt(-10, 0); p2 = new Pt(+10, 0);
    p3 = new Pt(-5, 0);  p4 = new Pt(+5, 0);
    points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
    Pt point1 = points[0], point2 = points[1];

    // Prints: (-5.000, 0.000) (5.000, 0.000)
    System.out.printf("(%.3f, %.3f) (%.3f, %.3f)\n", point1.x, point1.y, point2.x, point2.y);
  }

Je voulais juste mentionner qu'une bonne explication et une solution explicite peuvent être trouvées dans la série Recettes numériques. J'ai la 3e édition et la réponse se trouve à la page 1117, section 21.4. Une autre solution avec une nomenclature différente peut être trouvée dans un article de Marina Gavrilova Reliable Line Section Intersection Testing . Sa solution est, à mon avis, un peu plus simple.

Mon implémentation est ci-dessous:

bool NuGeometry::IsBetween(const double& x0, const double& x, const double& x1){
   return (x >= x0) && (x <= x1);
}

bool NuGeometry::FindIntersection(const double& x0, const double& y0, 
     const double& x1, const double& y1,
     const double& a0, const double& b0, 
     const double& a1, const double& b1, 
     double& xy, double& ab) {
   // four endpoints are x0, y0 & x1,y1 & a0,b0 & a1,b1
   // returned values xy and ab are the fractional distance along xy and ab
   // and are only defined when the result is true

   bool partial = false;
   double denom = (b0 - b1) * (x0 - x1) - (y0 - y1) * (a0 - a1);
   if (denom == 0) {
      xy = -1;
      ab = -1;
   } else {
      xy = (a0 * (y1 - b1) + a1 * (b0 - y1) + x1 * (b1 - b0)) / denom;
      partial = NuGeometry::IsBetween(0, xy, 1);
      if (partial) {
         // no point calculating this unless xy is between 0 & 1
         ab = (y1 * (x0 - a1) + b1 * (x1 - x0) + y0 * (a1 - x1)) / denom; 
      }
   }
   if ( partial && NuGeometry::IsBetween(0, ab, 1)) {
      ab = 1-ab;
      xy = 1-xy;
      return true;
   }  else return false;
}

De nombreuses solutions sont disponibles ci-dessus, mais je pense que la solution ci-dessous est assez simple et facile à comprendre.

Deux segments Vector AB et Vector CD se croisent si et seulement si

1. Les points d'extrémité a et b sont sur les côtés opposés du segment CD.
2. Les points d'extrémité c et d sont du côté opposé du segment AB.

Plus précisément, a et b sont sur le côté opposé du segment CD si et seulement si exactement l'un des deux triplets a, c, d et b, c, d est dans le sens antihoraire.

Intersect(a, b, c, d)
 if CCW(a, c, d) == CCW(b, c, d)
    return false;
 else if CCW(a, b, c) == CCW(a, b, d)
    return false;
 else
    return true;

Ici, CCW représente dans le sens antihoraire qui renvoie vrai / faux en fonction de l'orientation des points.

Source: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf Page 2

C et Objectif-C

D'après la réponse de Gareth Rees

const AGKLine AGKLineZero = (AGKLine){(CGPoint){0.0, 0.0}, (CGPoint){0.0, 0.0}};

AGKLine AGKLineMake(CGPoint start, CGPoint end)
{
    return (AGKLine){start, end};
}

double AGKLineLength(AGKLine l)
{
    return CGPointLengthBetween_AGK(l.start, l.end);
}

BOOL AGKLineIntersection(AGKLine l1, AGKLine l2, CGPoint *out_pointOfIntersection)
{
    // http://stackoverflow.com/a/565282/202451

    CGPoint p = l1.start;
    CGPoint q = l2.start;
    CGPoint r = CGPointSubtract_AGK(l1.end, l1.start);
    CGPoint s = CGPointSubtract_AGK(l2.end, l2.start);

    double s_r_crossProduct = CGPointCrossProductZComponent_AGK(r, s);
    double t = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), s) / s_r_crossProduct;
    double u = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), r) / s_r_crossProduct;

    if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
    {
        if(out_pointOfIntersection != NULL)
        {
            *out_pointOfIntersection = CGPointZero;
        }
        return NO;
    }
    else
    {
        if(out_pointOfIntersection != NULL)
        {
            CGPoint i = CGPointAdd_AGK(p, CGPointMultiply_AGK(r, t));
            *out_pointOfIntersection = i;
        }
        return YES;
    }
}

CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

CGPoint CGPointSubtract_AGK(CGPoint p1, CGPoint p2)
{
    return (CGPoint){p1.x - p2.x, p1.y - p2.y};
}

CGPoint CGPointAdd_AGK(CGPoint p1, CGPoint p2)
{
    return (CGPoint){p1.x + p2.x, p1.y + p2.y};
}

CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

CGPoint CGPointMultiply_AGK(CGPoint p1, CGFloat factor)
{
    return (CGPoint){p1.x * factor, p1.y * factor};
}

Beaucoup de fonctions et de structures sont privées, mais vous devriez assez facilement pouvoir savoir ce qui se passe. Ceci est public sur ce dépôt https://github.com/hfossli/AGGeometryKit/

Cela fonctionne bien pour moi. Pris d' ici .

 // calculates intersection and checks for parallel lines.  
 // also checks that the intersection point is actually on  
 // the line segment p1-p2  
 Point findIntersection(Point p1,Point p2,  
   Point p3,Point p4) {  
   float xD1,yD1,xD2,yD2,xD3,yD3;  
   float dot,deg,len1,len2;  
   float segmentLen1,segmentLen2;  
   float ua,ub,div;  

   // calculate differences  
   xD1=p2.x-p1.x;  
   xD2=p4.x-p3.x;  
   yD1=p2.y-p1.y;  
   yD2=p4.y-p3.y;  
   xD3=p1.x-p3.x;  
   yD3=p1.y-p3.y;    

   // calculate the lengths of the two lines  
   len1=sqrt(xD1*xD1+yD1*yD1);  
   len2=sqrt(xD2*xD2+yD2*yD2);  

   // calculate angle between the two lines.  
   dot=(xD1*xD2+yD1*yD2); // dot product  
   deg=dot/(len1*len2);  

   // if abs(angle)==1 then the lines are parallell,  
   // so no intersection is possible  
   if(abs(deg)==1) return null;  

   // find intersection Pt between two lines  
   Point pt=new Point(0,0);  
   div=yD2*xD1-xD2*yD1;  
   ua=(xD2*yD3-yD2*xD3)/div;  
   ub=(xD1*yD3-yD1*xD3)/div;  
   pt.x=p1.x+ua*xD1;  
   pt.y=p1.y+ua*yD1;  

   // calculate the combined length of the two segments  
   // between Pt-p1 and Pt-p2  
   xD1=pt.x-p1.x;  
   xD2=pt.x-p2.x;  
   yD1=pt.y-p1.y;  
   yD2=pt.y-p2.y;  
   segmentLen1=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);  

   // calculate the combined length of the two segments  
   // between Pt-p3 and Pt-p4  
   xD1=pt.x-p3.x;  
   xD2=pt.x-p4.x;  
   yD1=pt.y-p3.y;  
   yD2=pt.y-p4.y;  
   segmentLen2=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);  

   // if the lengths of both sets of segments are the same as  
   // the lenghts of the two lines the point is actually  
   // on the line segment.  

   // if the point isn’t on the line, return null  
   if(abs(len1-segmentLen1)>0.01 || abs(len2-segmentLen2)>0.01)  
     return null;  

   // return the valid intersection  
   return pt;  
 }  

 class Point{  
   float x,y;  
   Point(float x, float y){  
     this.x = x;  
     this.y = y;  
   }  

   void set(float x, float y){  
     this.x = x;  
     this.y = y;  
   }  
 }  

J'ai essayé certaines de ces réponses, mais elles n'ont pas fonctionné pour moi (désolé les gars); après quelques recherches sur Internet, j'ai trouvé cela .

Avec une petite modification de son code, j'ai maintenant cette fonction qui retournera le point d'intersection ou si aucune intersection n'est trouvée, elle retournera -1, -1.

    Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point
    '//  Determines the intersection point of the line segment defined by points A and B
    '//  with the line segment defined by points C and D.
    '//
    '//  Returns YES if the intersection point was found, and stores that point in X,Y.
    '//  Returns NO if there is no determinable intersection point, in which case X,Y will
    '//  be unmodified.

    Dim distAB, theCos, theSin, newX, ABpos As Double

    '//  Fail if either line segment is zero-length.
    If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1)

    '//  Fail if the segments share an end-point.
    If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1)

    '//  (1) Translate the system so that point A is on the origin.
    bx -= ax
    by -= ay
    cx -= ax
    cy -= ay
    dx -= ax
    dy -= ay

    '//  Discover the length of segment A-B.
    distAB = Math.Sqrt(bx * bx + by * by)

    '//  (2) Rotate the system so that point B is on the positive X axis.
    theCos = bx / distAB
    theSin = by / distAB
    newX = cx * theCos + cy * theSin
    cy = cy * theCos - cx * theSin
    cx = newX
    newX = dx * theCos + dy * theSin
    dy = dy * theCos - dx * theSin
    dx = newX

    '//  Fail if segment C-D doesn't cross line A-B.
    If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1)

    '//  (3) Discover the position of the intersection point along line A-B.
    ABpos = dx + (cx - dx) * dy / (dy - cy)

    '//  Fail if segment C-D crosses line A-B outside of segment A-B.
    If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)

    '//  (4) Apply the discovered position to line A-B in the original coordinate system.
    '*X=Ax+ABpos*theCos
    '*Y=Ay+ABpos*theSin

    '//  Success.
    Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function

Il semble y avoir un certain intérêt dans la réponse de Gavin pour laquelle cortijon a proposé une version javascript dans les commentaires et iMalc a fourni une version avec un peu moins de calculs . Certains ont signalé des lacunes dans diverses propositions de code et d'autres ont commenté l'efficacité de certaines propositions de code.

L'algorithme fourni par iMalc via la réponse de Gavin est celui que j'utilise actuellement dans un projet javascript et je voulais juste fournir une version nettoyée ici si cela peut aider quelqu'un.

// Some variables for reuse, others may do this differently
var p0x, p1x, p2x, p3x, ix,
    p0y, p1y, p2y, p3y, iy,
    collisionDetected;

// do stuff, call other functions, set endpoints...

// note: for my purpose I use |t| < |d| as opposed to
// |t| <= |d| which is equivalent to 0 <= t < 1 rather than
// 0 <= t <= 1 as in Gavin's answer - results may vary

var lineSegmentIntersection = function(){
    var d, dx1, dx2, dx3, dy1, dy2, dy3, s, t;

    dx1 = p1x - p0x;      dy1 = p1y - p0y;
    dx2 = p3x - p2x;      dy2 = p3y - p2y;
    dx3 = p0x - p2x;      dy3 = p0y - p2y;

    collisionDetected = 0;

    d = dx1 * dy2 - dx2 * dy1;

    if(d !== 0){
        s = dx1 * dy3 - dx3 * dy1;
        if((s <= 0 && d < 0 && s >= d) || (s >= 0 && d > 0 && s <= d)){
            t = dx2 * dy3 - dx3 * dy2;
            if((t <= 0 && d < 0 && t > d) || (t >= 0 && d > 0 && t < d)){
                t = t / d;
                collisionDetected = 1;
                ix = p0x + t * dx1;
                iy = p0y + t * dy1;
            }
        }
    }
};

Je pense qu'il existe une solution beaucoup plus simple à ce problème. J'ai eu une autre idée aujourd'hui et elle semble fonctionner très bien (au moins en 2D pour l'instant). Tout ce que vous avez à faire est de calculer l'intersection entre deux lignes, puis de vérifier si le point d'intersection calculé se trouve dans les zones de délimitation des deux segments de ligne. Si tel est le cas, les segments de ligne se coupent. C'est ça.

ÉDITER:

Voici comment je calcule l'intersection (je ne sais plus où j'ai trouvé cet extrait de code)

Point3D

vient de

System.Windows.Media.Media3D

public static Point3D? Intersection(Point3D start1, Point3D end1, Point3D start2, Point3D end2) {

        double a1 = end1.Y - start1.Y;
        double b1 = start1.X - end1.X;
        double c1 = a1 * start1.X + b1 * start1.Y;

        double a2 = end2.Y - start2.Y;
        double b2 = start2.X - end2.X;
        double c2 = a2 * start2.X + b2 * start2.Y;

        double det = a1 * b2 - a2 * b1;
        if (det == 0) { // lines are parallel
            return null;
        }

        double x = (b2 * c1 - b1 * c2) / det;
        double y = (a1 * c2 - a2 * c1) / det;

        return new Point3D(x, y, 0.0);
    }

et voici ma classe BoundingBox (simplifiée aux fins de la réponse):

public class BoundingBox {
    private Point3D min = new Point3D();
    private Point3D max = new Point3D();

    public BoundingBox(Point3D point) {
        min = point;
        max = point;
    }

    public Point3D Min {
        get { return min; }
        set { min = value; }
    }

    public Point3D Max {
        get { return max; }
        set { max = value; }
    }

    public bool Contains(BoundingBox box) {
        bool contains =
            min.X <= box.min.X && max.X >= box.max.X &&
            min.Y <= box.min.Y && max.Y >= box.max.Y &&
            min.Z <= box.min.Z && max.Z >= box.max.Z;
        return contains;
    }

    public bool Contains(Point3D point) {
        return Contains(new BoundingBox(point));
    }

}

Cette solution peut aider

public static float GetLineYIntesept(PointF p, float slope)
    {
        return p.Y - slope * p.X;
    }

    public static PointF FindIntersection(PointF line1Start, PointF line1End, PointF line2Start, PointF line2End)
    {

        float slope1 = (line1End.Y - line1Start.Y) / (line1End.X - line1Start.X);
        float slope2 = (line2End.Y - line2Start.Y) / (line2End.X - line2Start.X);

        float yinter1 = GetLineYIntesept(line1Start, slope1);
        float yinter2 = GetLineYIntesept(line2Start, slope2);

        if (slope1 == slope2 && yinter1 != yinter2)
            return PointF.Empty;

        float x = (yinter2 - yinter1) / (slope1 - slope2);

        float y = slope1 * x + yinter1;

        return new PointF(x, y);
    }

J'ai porté la réponse ci-dessus de Kris sur JavaScript. Après avoir essayé de nombreuses réponses différentes, la sienne a fourni les bons points. Je pensais devenir fou que je n'obtenais pas les points dont j'avais besoin.

function getLineLineCollision(p0, p1, p2, p3) {
    var s1, s2;
    s1 = {x: p1.x - p0.x, y: p1.y - p0.y};
    s2 = {x: p3.x - p2.x, y: p3.y - p2.y};

    var s10_x = p1.x - p0.x;
    var s10_y = p1.y - p0.y;
    var s32_x = p3.x - p2.x;
    var s32_y = p3.y - p2.y;

    var denom = s10_x * s32_y - s32_x * s10_y;

    if(denom == 0) {
        return false;
    }

    var denom_positive = denom > 0;

    var s02_x = p0.x - p2.x;
    var s02_y = p0.y - p2.y;

    var s_numer = s10_x * s02_y - s10_y * s02_x;

    if((s_numer < 0) == denom_positive) {
        return false;
    }

    var t_numer = s32_x * s02_y - s32_y * s02_x;

    if((t_numer < 0) == denom_positive) {
        return false;
    }

    if((s_numer > denom) == denom_positive || (t_numer > denom) == denom_positive) {
        return false;
    }

    var t = t_numer / denom;

    var p = {x: p0.x + (t * s10_x), y: p0.y + (t * s10_y)};
    return p;
}

J'ai essayé de nombreuses façons et j'ai décidé d'écrire la mienne. Voici donc:

bool IsBetween (float x, float b1, float b2)
{
   return ( ((x >= (b1 - 0.1f)) && 
        (x <= (b2 + 0.1f))) || 
        ((x >= (b2 - 0.1f)) &&
        (x <= (b1 + 0.1f))));
}

bool IsSegmentsColliding(   POINTFLOAT lineA,
                POINTFLOAT lineB,
                POINTFLOAT line2A,
                POINTFLOAT line2B)
{
    float deltaX1 = lineB.x - lineA.x;
    float deltaX2 = line2B.x - line2A.x;
    float deltaY1 = lineB.y - lineA.y;
    float deltaY2 = line2B.y - line2A.y;

    if (abs(deltaX1) < 0.01f && 
        abs(deltaX2) < 0.01f) // Both are vertical lines
        return false;
    if (abs((deltaY1 / deltaX1) -
        (deltaY2 / deltaX2)) < 0.001f) // Two parallel line
        return false;

    float xCol = (  (   (deltaX1 * deltaX2) * 
                        (line2A.y - lineA.y)) - 
                    (line2A.x * deltaY2 * deltaX1) + 
                    (lineA.x * deltaY1 * deltaX2)) / 
                 ((deltaY1 * deltaX2) - (deltaY2 * deltaX1));
    float yCol = 0;
    if (deltaX1 < 0.01f) // L1 is a vertical line
        yCol = ((xCol * deltaY2) + 
                (line2A.y * deltaX2) - 
                (line2A.x * deltaY2)) / deltaX2;
    else // L1 is acceptable
        yCol = ((xCol * deltaY1) +
                (lineA.y * deltaX1) -
                (lineA.x * deltaY1)) / deltaX1;

    bool isCol =    IsBetween(xCol, lineA.x, lineB.x) &&
            IsBetween(yCol, lineA.y, lineB.y) &&
            IsBetween(xCol, line2A.x, line2B.x) &&
            IsBetween(yCol, line2A.y, line2B.y);
    return isCol;
}

Basé sur ces deux formules: (je les ai simplifiées à partir de l'équation des lignes et d'autres formules)

Ceci basé sur la réponse de Gareth Ree. Il renvoie également le chevauchement des segments de ligne s'ils le font. Codé en C ++, V est une classe vectorielle simple. Où le produit croisé de deux vecteurs en 2D renvoie un seul scalaire. Il a été testé et approuvé par le système de test automatique de mon école.

//Required input point must be colinear with the line
bool on_segment(const V& p, const LineSegment& l)
{
    //If a point is on the line, the sum of the vectors formed by the point to the line endpoints must be equal
    V va = p - l.pa;
    V vb = p - l.pb;
    R ma = va.magnitude();
    R mb = vb.magnitude();
    R ml = (l.pb - l.pa).magnitude();
    R s = ma + mb;
    bool r = s <= ml + epsilon;
    return r;
}

//Compute using vector math
// Returns 0 points if the lines do not intersect or overlap
// Returns 1 point if the lines intersect
//  Returns 2 points if the lines overlap, contain the points where overlapping start starts and stop
std::vector<V> intersect(const LineSegment& la, const LineSegment& lb)
{
    std::vector<V> r;

    //http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
    V oa, ob, da, db; //Origin and direction vectors
    R sa, sb; //Scalar values
    oa = la.pa;
    da = la.pb - la.pa;
    ob = lb.pa;
    db = lb.pb - lb.pa;

    if (da.cross(db) == 0 && (ob - oa).cross(da) == 0) //If colinear
    {
        if (on_segment(lb.pa, la) && on_segment(lb.pb, la))
        {
            r.push_back(lb.pa);
            r.push_back(lb.pb);
            dprintf("colinear, overlapping\n");
            return r;
        }

        if (on_segment(la.pa, lb) && on_segment(la.pb, lb))
        {
            r.push_back(la.pa);
            r.push_back(la.pb);
            dprintf("colinear, overlapping\n");
            return r;
        }

        if (on_segment(la.pa, lb))
            r.push_back(la.pa);

        if (on_segment(la.pb, lb))
            r.push_back(la.pb);

        if (on_segment(lb.pa, la))
            r.push_back(lb.pa);

        if (on_segment(lb.pb, la))
            r.push_back(lb.pb);

        if (r.size() == 0)
            dprintf("colinear, non-overlapping\n");
        else
            dprintf("colinear, overlapping\n");

        return r;
    }

    if (da.cross(db) == 0 && (ob - oa).cross(da) != 0)
    {
        dprintf("parallel non-intersecting\n");
        return r;
    }

    //Math trick db cross db == 0, which is a single scalar in 2D.
    //Crossing both sides with vector db gives:
    sa = (ob - oa).cross(db) / da.cross(db);

    //Crossing both sides with vector da gives
    sb = (oa - ob).cross(da) / db.cross(da);

    if (0 <= sa && sa <= 1 && 0 <= sb && sb <= 1)
    {
        dprintf("intersecting\n");
        r.push_back(oa + da * sa);
        return r;
    }

    dprintf("non-intersecting, non-parallel, non-colinear, non-overlapping\n");
    return r;
}

Voici une implémentation de base d'un segment de ligne en C #, avec le code de détection d'intersection correspondant. Il nécessite une structure vectorielle / point 2D appelée Vector2f, bien que vous puissiez la remplacer par tout autre type ayant des propriétés X / Y. Vous pouvez également remplacer floatpardouble si cela convient mieux à vos besoins.

Ce code est utilisé dans ma bibliothèque de physique .NET, Boing .

public struct LineSegment2f
{
    public Vector2f From { get; }
    public Vector2f To { get; }

    public LineSegment2f(Vector2f @from, Vector2f to)
    {
        From = @from;
        To = to;
    }

    public Vector2f Delta => new Vector2f(To.X - From.X, To.Y - From.Y);

    /// <summary>
    /// Attempt to intersect two line segments.
    /// </summary>
    /// <remarks>
    /// Even if the line segments do not intersect, <paramref name="t"/> and <paramref name="u"/> will be set.
    /// If the lines are parallel, <paramref name="t"/> and <paramref name="u"/> are set to <see cref="float.NaN"/>.
    /// </remarks>
    /// <param name="other">The line to attempt intersection of this line with.</param>
    /// <param name="intersectionPoint">The point of intersection if within the line segments, or empty..</param>
    /// <param name="t">The distance along this line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
    /// <param name="u">The distance along the other line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
    /// <returns><c>true</c> if the line segments intersect, otherwise <c>false</c>.</returns>
    public bool TryIntersect(LineSegment2f other, out Vector2f intersectionPoint, out float t, out float u)
    {
        var p = From;
        var q = other.From;
        var r = Delta;
        var s = other.Delta;

        // t = (q − p) × s / (r × s)
        // u = (q − p) × r / (r × s)

        var denom = Fake2DCross(r, s);

        if (denom == 0)
        {
            // lines are collinear or parallel
            t = float.NaN;
            u = float.NaN;
            intersectionPoint = default(Vector2f);
            return false;
        }

        var tNumer = Fake2DCross(q - p, s);
        var uNumer = Fake2DCross(q - p, r);

        t = tNumer / denom;
        u = uNumer / denom;

        if (t < 0 || t > 1 || u < 0 || u > 1)
        {
            // line segments do not intersect within their ranges
            intersectionPoint = default(Vector2f);
            return false;
        }

        intersectionPoint = p + r * t;
        return true;
    }

    private static float Fake2DCross(Vector2f a, Vector2f b)
    {
        return a.X * b.Y - a.Y * b.X;
    }
}

Un programme C ++ pour vérifier si deux segments de ligne donnés se croisent

#include <iostream>
using namespace std;

struct Point
{
    int x;
    int y;
};

// Given three colinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(Point p, Point q, Point r)
{
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
       return true;

    return false;
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
    // See 10th slides from following link for derivation of the formula
    // http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // colinear

    return (val > 0)? 1: 2; // clock or counterclock wise
}

// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    // General case
    if (o1 != o2 && o3 != o4)
        return true;

    // Special Cases
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

     // p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false; // Doesn't fall in any of the above cases
}

// Driver program to test above functions
int main()
{
    struct Point p1 = {1, 1}, q1 = {10, 1};
    struct Point p2 = {1, 2}, q2 = {10, 2};

    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {10, 0}, q1 = {0, 10};
    p2 = {0, 0}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {-5, -5}, q1 = {0, 0};
    p2 = {1, 1}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    return 0;
}

Basé sur la réponse de @Gareth Rees, version pour Python:

import numpy as np

def np_perp( a ) :
    b = np.empty_like(a)
    b[0] = a[1]
    b[1] = -a[0]
    return b

def np_cross_product(a, b):
    return np.dot(a, np_perp(b))

def np_seg_intersect(a, b, considerCollinearOverlapAsIntersect = False):
    # /programming/563198/how-do-you-detect-where-two-line-segments-intersect/565282#565282
    # http://www.codeproject.com/Tips/862988/Find-the-intersection-point-of-two-line-segments
    r = a[1] - a[0]
    s = b[1] - b[0]
    v = b[0] - a[0]
    num = np_cross_product(v, r)
    denom = np_cross_product(r, s)
    # If r x s = 0 and (q - p) x r = 0, then the two lines are collinear.
    if np.isclose(denom, 0) and np.isclose(num, 0):
        # 1. If either  0 <= (q - p) * r <= r * r or 0 <= (p - q) * s <= * s
        # then the two lines are overlapping,
        if(considerCollinearOverlapAsIntersect):
            vDotR = np.dot(v, r)
            aDotS = np.dot(-v, s)
            if (0 <= vDotR  and vDotR <= np.dot(r,r)) or (0 <= aDotS  and aDotS <= np.dot(s,s)):
                return True
        # 2. If neither 0 <= (q - p) * r = r * r nor 0 <= (p - q) * s <= s * s
        # then the two lines are collinear but disjoint.
        # No need to implement this expression, as it follows from the expression above.
        return None
    if np.isclose(denom, 0) and not np.isclose(num, 0):
        # Parallel and non intersecting
        return None
    u = num / denom
    t = np_cross_product(v, s) / denom
    if u >= 0 and u <= 1 and t >= 0 and t <= 1:
        res = b[0] + (s*u)
        return res
    # Otherwise, the two line segments are not parallel but do not intersect.
    return None

Si chaque côté du rectangle est un segment de ligne et que la partie dessinée par l'utilisateur est un segment de ligne, vous devez simplement vérifier le segment dessiné par l'utilisateur pour l'intersection avec les quatre segments de ligne latéraux. Cela devrait être un exercice assez simple étant donné les points de début et de fin de chaque segment.

Basé sur la réponse de t3chb0t:

int intersezione_linee(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
   //L1: estremi (x1,y1)(x2,y2) L2: estremi (x3,y3)(x3,y3)
   int d;
   d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
   if(!d)
       return 0;
   p_x = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d;
   p_y = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d;
   return 1;
}

int in_bounding_box(int x1, int y1, int x2, int y2, int p_x, int p_y)
{
    return p_x>=x1 && p_x<=x2 && p_y>=y1 && p_y<=y2;

}

int intersezione_segmenti(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
    if (!intersezione_linee(x1,y1,x2,y2,x3,y3,x4,y4,p_x,p_y))
        return 0;

    return in_bounding_box(x1,y1,x2,y2,p_x,p_y) && in_bounding_box(x3,y3,x4,y4,p_x,p_y);
}

J'ai lu ces algorithmes du livre "géométrie à vues multiples"

texte suivant utilisant

'comme signe de transposition

* comme produit scalaire

x comme produit croisé, en cas d'utilisation comme opérateur

1. définition de la ligne

un point x_vec = (x, y) 'se trouve sur la ligne ax + de + c = 0

nous notons L = (a, b, c) ', le point comme (x, y, 1)' comme coordonnées homogènes

l'équation de la ligne peut s'écrire

(x, y, 1) (a, b, c) '= 0 ou x' * L = 0

2. intersection de lignes

nous avons deux lignes L1 = (a1, b1, c1) ', L2 = (a2, b2, c2)'

supposons que x est un point, un vecteur et x = L1 x L2 (produit croisé L1 L2).

attention, x est toujours un point 2D, veuillez lire les coordonnées homogènes si vous êtes confus (L1xL2) est un vecteur à trois éléments, et x est une coordonnée 2D.

selon le triple produit, nous savons que

L1 * (L1 x L2) = 0, et L2 * (L1 x L2) = 0, en raison du co-plan L1, L2

nous substituons (L1xL2) par le vecteur x, puis nous avons L1 * x = 0, L2 * x = 0, ce qui signifie que x se trouve à la fois sur L1 et L2, x est le point d'intersection.

attention, ici x est des coordonnées homogènes, si le dernier élément de x est nul, cela signifie que L1 et L2 sont parallèles.

De nombreuses réponses ont regroupé tous les calculs dans une seule fonction. Si vous devez calculer les pentes de ligne, les intersections y ou les intersections x pour les utiliser ailleurs dans votre code, vous effectuerez ces calculs de manière redondante. J'ai séparé les fonctions respectives, utilisé des noms de variables évidents et commenté mon code pour le rendre plus facile à suivre. J'avais besoin de savoir si les lignes se croisent infiniment au-delà de leurs points de terminaison, donc en JavaScript:

http://jsfiddle.net/skibulk/evmqq00u/

var point_a = {x:0, y:10},
    point_b = {x:12, y:12},
    point_c = {x:10, y:0},
    point_d = {x:0, y:0},
    slope_ab = slope(point_a, point_b),
    slope_bc = slope(point_b, point_c),
    slope_cd = slope(point_c, point_d),
    slope_da = slope(point_d, point_a),
    yint_ab = y_intercept(point_a, slope_ab),
    yint_bc = y_intercept(point_b, slope_bc),
    yint_cd = y_intercept(point_c, slope_cd),
    yint_da = y_intercept(point_d, slope_da),
    xint_ab = x_intercept(point_a, slope_ab, yint_ab),
    xint_bc = x_intercept(point_b, slope_bc, yint_bc),
    xint_cd = x_intercept(point_c, slope_cd, yint_cd),
    xint_da = x_intercept(point_d, slope_da, yint_da),
    point_aa = intersect(slope_da, yint_da, xint_da, slope_ab, yint_ab, xint_ab),
    point_bb = intersect(slope_ab, yint_ab, xint_ab, slope_bc, yint_bc, xint_bc),
    point_cc = intersect(slope_bc, yint_bc, xint_bc, slope_cd, yint_cd, xint_cd),
    point_dd = intersect(slope_cd, yint_cd, xint_cd, slope_da, yint_da, xint_da);

console.log(point_a, point_b, point_c, point_d);
console.log(slope_ab, slope_bc, slope_cd, slope_da);
console.log(yint_ab, yint_bc, yint_cd, yint_da);
console.log(xint_ab, xint_bc, xint_cd, xint_da);
console.log(point_aa, point_bb, point_cc, point_dd);

function slope(point_a, point_b) {
  var i = (point_b.y - point_a.y) / (point_b.x - point_a.x);
  if (i === -Infinity) return Infinity;
  if (i === -0) return 0;
  return i;
}

function y_intercept(point, slope) {
    // Horizontal Line
    if (slope == 0) return point.y;
  // Vertical Line
    if (slope == Infinity)
  {
    // THE Y-Axis
    if (point.x == 0) return Infinity;
    // No Intercept
    return null;
  }
  // Angled Line
  return point.y - (slope * point.x);
}

function x_intercept(point, slope, yint) {
    // Vertical Line
    if (slope == Infinity) return point.x;
  // Horizontal Line
    if (slope == 0)
  {
    // THE X-Axis
    if (point.y == 0) return Infinity;
    // No Intercept
    return null;
  }
  // Angled Line
  return -yint / slope;
}

// Intersection of two infinite lines
function intersect(slope_a, yint_a, xint_a, slope_b, yint_b, xint_b) {
  if (slope_a == slope_b)
  {
    // Equal Lines
    if (yint_a == yint_b && xint_a == xint_b) return Infinity;
    // Parallel Lines
    return null;
  }
  // First Line Vertical
    if (slope_a == Infinity)
  {
    return {
        x: xint_a,
      y: (slope_b * xint_a) + yint_b
    };
  }
  // Second Line Vertical
    if (slope_b == Infinity)
  {
    return {
        x: xint_b,
      y: (slope_a * xint_b) + yint_a
    };
  }
  // Not Equal, Not Parallel, Not Vertical
  var i = (yint_b - yint_a) / (slope_a - slope_b);
  return {
    x: i,
    y: (slope_a * i) + yint_a
  };
}