Page crée le 20/11/2000
Calcul des coordonnées du point d'intersectionde 2 lignes
en GFA-BASIC
Page d'accueil

Je vous propose ici 2 possibilités :



- Ma méthode, qui utilise les équations de droites. Elle est très lourde, ne gère pas les cas où l'un des segments est un point (merci à Alexandre Cognard pour cette remarque) mais intéressante quand même.

- Une autre méthode, décrite par Paul Bourke, avec des équations de segment, plus rapide et dont vous aurez l'explication sur sonsite









MA METHODE PAR EQUATIONS DE DROITE :

Le listing de la procédure

On appellera la procédure GetIntersection(x1,y1,x2,y2,x3,y3,x4,y4,varI%,ix,iy)
 
  où Valeur passées en paramètres :
 x1,y1,x2,y2 sont les coordonnées de la premièreligne 
 x3,y3,x4,y4 sont les coordonnées de la seconde ligne 
Valeur retournées dans :
 I% prend la valeur "VRAI" si il y a un point d'intersection et"FAUX" s'il n'y en a pas . 
 ix,iy sont les coordonnées du point d'intersection
La méthode choisie utilise les équations de droite, les 2lignes sont donc considérées comme des segments de droite.
2 types d'équation sont possibles : Type 1 :  y = ax + b

Type 2 :  x = ay + b

Une droite plutôt horizontale sera réprésentéepar le Type 1, et plutôt verticale par le Type 2, afin d'éviterdes dépacement de capacité de calcul . Si on gardaitune équation de TYPE 1 pour une ligne verticale la valeur de A seraitinfinie et celle de B n'aurait aucune signification . Il faut donc àpartir des coordonnées des lignes en déduire le Type d'équationet les variables A et B qui en découlent . Pour cela on va comparerles distance X et Y :

'Détermination du type d'équationpour la première ligne
lx1=x2-x1, ly1=y2-y1  'Distancex et y
IF ABS(lx1)>ABS(ly1) 'si la ligne est plutôthorizontale
  TYPE1%=1, A1 = ly1 / lx1, B1 = -(A1 * x1 - y1)
ELSE              'sinon
  TYPE1%=2, A1 = lx1 / ly1, B1 = -(A1 * y1 - x1)
ENDIF

'Détermination du type d'équationpour la seconde ligne
lx2=x4-x3,ly2=y4-y3  'Distance x ety
IF ABS(lx2)>ABS(ly2) 'si la ligne est plutôthorizontale
  TYPE2%=1, A2 = ly2 / lx2, B2 = -(A2 * x3 - y3)
ELSE              'sinon
  TYPE2%=2, A2 = lx2 / ly2,    B2 = -(A2 *y3 - x3)
ENDIF


CAS 1 : Les équations sont du même type.

IF TYPE1%=TYPE2%

Si les 2 lignes sont du même type on pourra calculer facilementle point d'intersection des 2 droites, puis vérifier en toute simplicitéque le point d'intersection est compris dans les 2 segments de droite .
 
Condition
Déduction
a1=a2 ET b1<>b2
Il n'y a pas de point d'intersection
a1=a2 ET b1=b2
Les 2 lignes sont confondues .
Il y a donc une infinité de point d'intersection
J'ai délibérément choisi de mettreI% = "FAUX" (pas de point d'intersection pour ce cas)
a1<>a2
Il existe un point d'intersection des 2 droites
Reste à savoir si il fait partie des 2 segments 
 CLR I%
 If TYPE1% = 1 And TYPE2% = 1
   If A1 <> A2
     ix = (B2 - B1) / (A1 - A2), iy = A1 *ix + B1 ' Coordonnées du point d'intersection
     ' Vérifionssi le point ix,iy est bien dans les 2 segments (I% sera VRAI si c'est lecas)
     I% = ix >= Min(x1, x2) And ix <= Max(x1,x2) And ix >= Min(x3, x4) And ix <= Max(x3, x4)
     I% = I% And iy >= Min(y1, y2) And iy <=Max(y1, y2) And iy >= Min(y3, y4) And iy <= Max(y3, y4)
   EndIf
 EndIf
 If TYPE1% = 2 And TYPE2% = 2
   If A1 <> A2
     iy = (B2 - B1) / (A1 - A2), ix = A1 *iy + B1 ' Coordonnées du point d'intersection
     ' Vérifionssi le point ix,iy est bien dans les 2 segments (I% sera VRAI si c'est lecas)
     I% = ix >= Min(x1, x2) And ix <= Max(x1,x2) And ix >= Min(x3, x4) And ix <= Max(x3, x4)
     I% = I% And iy >= Min(y1, y2) And iy <=Max(y1, y2) And iy >= Min(y3, y4) And iy <= Max(y3, y4)
   EndIf
 EndIf


CAS 2 : Les équations sont de types différents.

IF TYPE1%<>TYPE2%

Si les 2 lignes sont de types différents, j'utilise alors uneméthode d'approximation (rassurez-vous le résultat est aussiexact) . Le calcul prend donc plus de temp .
On prend une des 2 lignes et on calcule 1 point tx1,ty1 ( représentéen bleu) au milieu de cette ligne (segment primitif)  . 
Dans quelle direction  de ce point  (segment 1 ou segment2) se rapproche-t'on d'un point de l'autre ligne avec x ou y équivalent(v1 ou v2) ? 
On garde la distance la plus courte pour déterminer quel estla portion (AB ou BC) du segment primitif sur lequel on calculera un nouveaupoint central tx1,ty1 .
 

J'ai choisi de faire ce calcul 40 fois car au-delà le segment primitif à une longueur égale à zéro,ou du moins il n'y a plus de chiffres significatif .
Si quelqu'un a une autre méthode qu'il n'hésite pas àme le signaler, merci d'avance . (scalion@free.fr).

  If TYPE1% = 1 And TYPE2% = 2
    ix = x3, iy = y3, ix2 = x4, iy2 = y4
    For k% = 0 To 40
      tx1 = (ix + ix2) / 2, ty1 = (iy+ iy2) / 2      ' pointcentral
      ppx = (ix2 - tx1) / 2, ppy = (iy2- ty1) / 2    ' distance x et y dedéplacement
      v1 = Abs((ty1 + ppy) - (A1 * (tx1+ ppx) + B1)) ' comparaison sens 1
      v2 = Abs((ty1 - ppy) - (A1 * (tx1- ppx) + B1)) ' comparaison sens 2
      If v1 < v2                                   ' si distance sens 1 inférieure ( meilleur)
        ix = tx1, iy = ty1                         ' nouvelle coordonnées du segment primitifsens 1
      Else                                         ' sinon
         ix2 = tx1, iy2= ty1                      ' nouvelle coordonnées du segment primitifsens 2
      EndIf
    Next k%
    ty1 = A1 * ix + B1, tx1 = A2 * iy + B2         ' Vérification d'appartenance aux 2 segments
    i% = (Abs(ty1 - iy) < 0.000000001) And (Abs(tx1- ix) < 0.000000001) And (ix >= Min(x1, x2) And ix <= Max(x1, x2))
  EndIf

  If TYPE1% = 2 And TYPE2% = 1
    ix = x1, iy = y1, ix2 = x2, iy2 = y2
    For k% = 0 To 40
      tx1 = (ix + ix2) / 2, ty1 = (iy+ iy2) / 2       'point central
      ppx = (ix2 - tx1) / 2, ppy = (iy2- ty1) / 2     ' distance x ety de déplacement
      v1 = Abs((ty1 + ppy) - (A2 * (tx1+ ppx) + B2))  ' comparaison sens 1
      v2 = Abs((ty1 - ppy) - (A2 * (tx1- ppx) + B2))  ' comparaison sens 2
      If v1 < v2                                    ' si distance sens 1 inférieure ( meilleur)
        ix = tx1, iy = ty1                          ' nouvelle coordonnées du segment primitifsens 1
      Else                                          ' sinon
        ix2 = tx1, iy2 = ty1                        ' nouvelle coordonnées du segment primitifsens 2
      EndIf
    Next k%
    ty1 = A2 * ix + B2, tx1 = A1 * iy + B1          ' Vérification d'appartenance aux 2 segments
    i% = (Abs(ty1 - iy) < 0.000000001) And (Abs(tx1- ix) < 0.000000001) And (ix >= Min(x3, x4) And ix= < Max(x3, x4))
  EndIf

LE LISTING
Faites un copier-coller
PROCEDURE GetIntersection(x1, y1, x2, y2, x3, y3, x4, y4,var I%, ix, iy ) 
  LOCALlx1, ly1, TYPE1%, A1, B1, lx2, ly2, TYPE2%, A2, B2
  LOCAL ix2, iy2, k%, tx1, ty1,ppx, ppy, v1, v2

  ' Procédure écritele 10/10/2000 par Nicolas Rey 
  ' http://scalion.free.fr
  ' e-mail : scalion@free.fr 

  ' x1,y1,x2,y2 = coordonnéesde la première ligne 
  ' x3,y3,x4,y4 = coordonnéesde la seconde ligne 
  ' I% = VRAI si il y a un pointd'intersection et FAUX s'il n'y en a pas . 
  ' ix,iy = coordonnéesdu point d'intersection

  ' lx1 = Distance x de la premièreligne
  ' ly1 = Distance y de la premièreligne
  ' TYPE1% = Type d'équationde la première ligne
  ' A1 et B1 = Variable A et Bde l'équation de la première ligne
  ' lx2 = Distance x de la secondeligne
  ' ly2 = Distance y de la secondeligne
  ' TYPE2% = Type d'équationde la seconde ligne
  ' A2 et B2 = Variable A et Bde l'équation de la seconde ligne
  ' ix2 et iy2 = Coordonnéesde d'une des extrémité du segment primitif utilisédans l'approximation 
  ' tx1 et ty1 = point centraldu segment primitif
  ' ppx et ppy = distance x ety de déplacement dans un sens ou dans l'autre
  '            à partir du point central du segment primitif 
  ' v1 = Eloignement dans un sens 
  ' v2 = Eloignement dans l'autresens

  'Détermination du typed'équation pour la première ligne
  lx1=x2-x1, ly1=y2-y1  'Distancex et y
  IF ABS(lx1)>ABS(ly1)  'sila ligne est plutôt horizontale
    TYPE1%=1, A1 = ly1 / lx1, B1 = -(A1 *x1 - y1) 
  ELSE               'sinon
    TYPE1%=2, A1 = lx1 / ly1, B1 = -(A1 *y1 - x1) 
  ENDIF 

  'Détermination du typed'équation pour la seconde ligne
  lx2=x4-x3,ly2=y4-y3  'Distancex et y
  IF ABS(lx2)>ABS(ly2) 'si laligne est plutôt horizontale
    TYPE2%=1, A2 = ly2 / lx2, B2 = -(A2 *x3 - y3) 
  ELSE              'sinon
    TYPE2%=2, A2 = lx2 / ly2,   B2 = -(A2 * y3 - x3) 
  ENDIF 

  CLR I%            'Initialiser I% à zéro (A priori pasde point d'intersection)

  IF TYPE1% = 1 AND TYPE2% = 1 
    IF A1 <> A2 
      ix = (B2 - B1) / (A1 - A2),iy = A1 * ix + B1 ' Coordonnées du point d'intersection
      ' Vérifionssi le point ix,iy est bien dans les 2 segments (I% sera VRAI si c'est lecas)
      I% = ix >= Min(x1, x2) Andix <= Max(x1, x2) And ix >= Min(x3, x4) And ix <= Max(x3, x4) 
      I% = I% And iy >= Min(y1,y2) And iy <= Max(y1, y2) And iy >= Min(y3, y4) And iy <= Max(y3,y4) 
    ENDIF 
  ENDIF

  IF TYPE1% = 2 AND TYPE2% = 2 
    IF A1 <> A2 
      iy = (B2 - B1) / (A1 - A2),ix = A1 * iy + B1 ' Coordonnées du point d'intersection
      ' Vérifionssi le point ix,iy est bien dans les 2 segments (I% sera VRAI si c'est lecas)
      I% = ix >= Min(x1, x2) Andix <= Max(x1, x2) And ix >= Min(x3, x4) And ix <= Max(x3, x4) 
      I% = I% And iy >= Min(y1,y2) And iy <= Max(y1, y2) And iy >= Min(y3, y4) And iy <= Max(y3,y4) 
   ENDIF 
  ENDIF 

  IF TYPE1% = 1 AND TYPE2% = 2 
    ix = x3, iy = y3, ix2 = x4, iy2 = y4 
    FOR k% = 0 TO 40 
      tx1 = (ix + ix2) / 2, ty1= (iy + iy2) / 2      'point central
      ppx = (ix2 - tx1) / 2, ppy= (iy2 - ty1) / 2    ' distance xet y de déplacement
      v1 = Abs((ty1 + ppy) - (A1* (tx1 + ppx) + B1)) ' comparaison sens 1
      v2 = Abs((ty1 - ppy) - (A1* (tx1 - ppx) + B1)) ' comparaison sens 2
      IF v1 < v2                                   ' si distance sens 1 inférieure ( meilleur)
        ix = tx1, iy =ty1                         ' nouvelle coordonnées du segment primitifsens 1
      ELSE                                         ' sinon
        ix2 = tx1, iy2= ty1                       ' nouvelle coordonnées du segment primitifsens 2
      ENDIF 
    NEXT k% 
    ty1 = A1 * ix + B1, tx1 = A2 * iy + B2         ' Vérification d'appartenance aux 2 segments
    i% = (Abs(ty1 - iy) < 0.000000001)AND (Abs(tx1 - ix) < 0.000000001) AND (ix >= Min(x1, x2) And ix <=Max(x1, x2)) 
  ENDIF

  IF TYPE1% = 2 AND TYPE2% = 1 
    ix = x1, iy = y1, ix2 = x2, iy2 = y2 
    FOR k% = 0 TO 40 
      tx1 = (ix + ix2) / 2, ty1= (iy + iy2) / 2       'point central
      ppx = (ix2 - tx1) / 2, ppy= (iy2 - ty1) / 2     ' distancex et y de déplacement
      v1 = Abs((ty1 + ppy) - (A2* (tx1 + ppx) + B2))  ' comparaison sens 1
      v2 = Abs((ty1 - ppy) - (A2* (tx1 - ppx) + B2))  ' comparaison sens 2
      IF v1 < v2                                    ' si distance sens 1 inférieure ( meilleur)
        ix = tx1, iy =ty1                          ' nouvelle coordonnées du segment primitifsens 1
      ELSE                                          ' sinon
        ix2 = tx1, iy2= ty1                        ' nouvelle coordonnées du segment primitifsens 2
      ENDIF 
    NEXT k% 
    ty1 = A2 * ix + B2, tx1 = A1 * iy + B1          ' Vérification d'appartenance aux 2 segments
    i% = (Abs(ty1 - iy) < 0.000000001)AND (Abs(tx1 - ix) < 0.000000001) AND (ix >= Min(x3, x4) AND ix =<Max(x3, x4)) 
  ENDIF

RETURN 





LA METHODE DE PAUL BOURKE




Le listing en GFA-Basic

Il s'agit d'utiliser des équations de segment :

Segment 1 (x1,y1,x2,y2) :
Idem pour le Segment 2 (x3,y3,x4,y4) :
Si il y a un point d'intersection des droites alors on sait que pour ce point :
Ce qui donne l'équation suivante:
Solution Finale :
Comme je l'ai dit plus haut il suffit alors de vérifier que Ua et Ub soient compris tous deux entre 0 et 1 pour vérifier qu'il y a effectivement un point d'intersection !


LISTING En Gfa Basic :
Faites un COPIER-COLLER


PROCEDURE GetIntersectionPB(x1, y1, x2, y2, x3, y3, x4, y4, VAR I%, ix, iy )
  LOCAL S1,S2,S3,S4,S5,S6,S7,Ua,Ub,M1,M2

  I% = FALSE

  S1 = x4 - x3
  S2 = x2 - x1
  S5 = y2 - y1
  S6 = y4 - y3

  M1 = S1 * S5
  M2 = S6 * S2

  IF M1 <> M2  ' Si les lignes ne sont pas parallèles

    S3 = y1 - y3
    S4 = x1 - x3
    S7 = M2 - M1

    Ua = ( S1 * S3 - S6 * S4   )   / S7
    Ub = (  S2 * S3 - S5 * S4   )   / S7

    IF Ua > 0
      IF Ua < 1
        IF Ub > 0
          IF Ub < 1
            I% = TRUE
            ix = x1 + Ua * S2
            iy = y1 + Ua * S5
          ENDIF
        ENDIF
      ENDIF
    ENDIF

  ENDIF

RETURN