Comment trouver l'intersection de deux lignes avec un point sur chaque ligne et un vecteur parallèle

Question

J'ai besoin d'un algorithme capable de trouver l'intersection de deux lignes 2D. Chaque ligne viendra sous la forme un point sur la ligne et le dx/dy d'un vecteur parallèle. J'ai essayé de paramétrer chaque ligne et de résoudre le système d'équations à résoudre pour la variable paramétrée que je pourrais replacer dans l'équation paramétrique des lignes et obtenir mon x/y, mais ma tentative a échoué. Des idées? Je suis en programmation en Python mais le langage n'a pas beaucoup d'importance.

Answer 1

Vous avez essentiellement pour résoudre l'équation suivante:

x = x _{0, un} + dx _un × t
y = y _{0, un} + dy _un × t
x = x _{0, b} + dx _b × u
y = y _{0, b} + dy _b × u

Or:

x _{0, a} + dx _un × t = x _{0, b} + dx _b × u
x _{0, un} + dx _un × t = x _{0, b} + dx _b × u

Maintenant, si vous faites une manipulation algébrique, vous constaterez que:

t = dy _b × (x _{0, b} -x _{0, un}) -DX _b × (y _{0, b} -y _{0, un})/d
u = dy _un × (x _{0, b} -x _{0, un}) -DX _un × (y _{0, b} -y _{0, un})/d; où
d = dx _un × dy _b -dx _b × dy _un

Maintenant, il est donc seulement une question de déterminer soit t ou u (vous n'avez pas à calculer à la fois) , et branchez ensuite dans la formule ci-dessus.Alors

def intersect(x0a,y0a,dxa,dya,x0b,y0b,dxb,dyb): 
    t = (dyb*(x0b-x0a)-dxb*(y0b-y0a))/(dxa*dyb-dxb*dya) 
    return (x0a+dxa*t,y0a+dya*t) 

Si l'd dans l'équation (le dénominateur) est égal à zéro, cela signifie qu'il n'y a pas d'intersection (les deux lignes sont parallèles). Vous pouvez décider de modifier la fonction et par exemple retourner None ou déclencher une exception dans un tel cas.

Si vous le testez, par exemple avec un vecteur (1,0) décalage et direction (0,1); et un vecteur avec décalage (0,2) et direction (1,1); vous obtenez le résultat pas très surprenant de:

$ python3 
Python 3.5.2 (default, Nov 17 2016, 17:05:23) 
[GCC 5.4.0 20160609] on linux 
Type "help", "copyright", "credits" or "license" for more information. 
>>> def intersect(x0a,y0a,dxa,dya,x0b,y0b,dxb,dyb): 
...  t = (dyb*(x0b-x0a)-dxb*(y0b-y0a))/(dxa*dyb-dxb*dya) 
...  return (x0a+dxa*t,y0a+dya*t) 
... 
>>> intersect(1,0,0,1,0,2,1,1) 
(1.0, 3.0)