Intersection ligne-ligne - Line–line intersection

En géométrie euclidienne , l' intersection d'une ligne et d'une ligne peut être l' ensemble vide , un point ou une ligne. Distinguer ces cas et trouver le point d'intersection sont utiles, par exemple, dans l'infographie , la planification de mouvement et la détection de collision .

Dans la géométrie euclidienne tridimensionnelle , si deux lignes ne sont pas dans le même plan, elles sont appelées lignes obliques et n'ont pas de point d'intersection. S'ils sont dans le même plan, il y a trois possibilités : s'ils coïncident (ne sont pas des droites distinctes) ils ont une infinité de points en commun (c'est-à-dire tous les points de l'un d'eux) ; s'ils sont distincts mais ont la même pente, ils sont dits parallèles et n'ont pas de points communs ; sinon, ils ont un seul point d'intersection.

Les caractéristiques distinctives de la géométrie non euclidienne sont le nombre et les emplacements des intersections possibles entre deux lignes et le nombre de lignes possibles sans intersection (lignes parallèles) avec une ligne donnée.

Formules

Une condition nécessaire pour que deux lignes se coupent est qu'elles soient dans le même plan, c'est-à-dire qu'elles ne soient pas des lignes obliques. La satisfaction de cette condition équivaut au tétraèdre dont les sommets à deux des points d'une ligne et deux des points de l'autre ligne sont dégénérés dans le sens d'avoir un volume nul . Pour la forme algébrique de cette condition, voir Skew lines § Testing for skewness .

Étant donné deux points sur chaque ligne

Nous considérons d'abord l'intersection de deux lignes et dans un espace à 2 dimensions, la ligne étant définie par deux points distincts et , et la ligne étant définie par deux points distincts et . ${\style d'affichage L_{1}}$${\style d'affichage L_{2}}$${\style d'affichage L_{1}}$${\style d'affichage (x_{1},y_{1})}$${\style d'affichage (x_{2},y_{2})}$${\style d'affichage L_{2}}$${\style d'affichage (x_{3},y_{3})}$${\style d'affichage (x_{4},y_{4})}$

L'intersection de la ligne et peut être définie à l'aide de déterminants . ${\style d'affichage P}$${\style d'affichage L_{1}}$${\style d'affichage L_{2}}$

${\displaystyle P_{x}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\ begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4} \end{vmatrix}}&{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_ {1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{ vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix} }}\,\!\qquad P_{y}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix }}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4 }&y_{4}\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\ begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\ \{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}} \end{vmatrix}}}\,\!}$

Les déterminants peuvent s'écrire sous la forme :

${\displaystyle {\begin{aligned}(P_{x},P_{y})={\Biggl (}&{\frac {(x_{1}y_{2}-y_{1}x_{2}) (x_{3}-x_{4})-(x_{1}-x_{2})(x_{3}y_{4}-y_{3}x_{4})}{D}},\\ &{\frac {(x_{1}y_{2}-y_{1}x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{ 3}y_{4}-y_{3}x_{4})}{D}}{\Biggr )}\end{aligned}}}$

où le dénominateur est :

${\displaystyle D=(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4}) }$

Lorsque les deux droites sont parallèles ou coïncidentes, le dénominateur est zéro. Si les lignes sont presque parallèles, alors une solution informatique peut rencontrer des problèmes numériques mettant en œuvre la solution décrite ci-dessus : la reconnaissance de cette condition peut nécessiter un test approximatif dans une application pratique. Une autre approche pourrait consister à faire pivoter les segments de ligne de sorte que l'un d'eux soit horizontal, d'où la solution de la forme paramétrique tournée de la deuxième ligne est facilement obtenue. Une discussion approfondie des cas particuliers est nécessaire (lignes parallèles/lignes coïncidentes, intervalles chevauchants/non chevauchants).

Étant donné deux points sur chaque segment de ligne

Notez que le point d'intersection ci-dessus concerne les lignes infiniment longues définies par les points, plutôt que les segments de ligne entre les points, et peut produire un point d'intersection non contenu dans l'un des deux segments de ligne. Afin de trouver la position de l'intersection par rapport aux segments de droite, on peut définir des droites et en termes de paramètres de Bézier du premier degré : ${\style d'affichage L_{1}}$${\style d'affichage L_{2}}$

${\displaystyle L_{1}={\begin{bmatrix}x_{1}\\y_{1}\end{bmatrix}}+t{\begin{bmatrix}x_{2}-x_{1}\\y_ {2}-y_{1}\end{bmatrix}},\qquad L_{2}={\begin{bmatrix}x_{3}\\y_{3}\end{bmatrix}}+u{\begin{ bmatrix}x_{4}-x_{3}\\y_{4}-y_{3}\end{bmatrix}}}$

(où t et u sont des nombres réels). Le point d'intersection des lignes se trouve avec l'une des valeurs suivantes de t ou u , où

${\displaystyle t={\frac {\begin{vmatrix}x_{1}-x_{3}&x_{3}-x_{4}\\y_{1}-y_{3}&y_{3}-y_{ 4}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{ 4}\end{vmatrix}}}={\frac {(x_{1}-x_{3})(y_{3}-y_{4})-(y_{1}-y_{3})(x_ {3}-x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3} -x_{4})}}}$

et

${\displaystyle u={\frac {\begin{vmatrix}x_{1}-x_{3}&x_{1}-x_{2}\\y_{1}-y_{3}&y_{1}-y_{ 2}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{ 4}\end{vmatrix}}}={\frac {(x_{1}-x_{3})(y_{1}-y_{2})-(y_{1}-y_{3})(x_ {1}-x_{2})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3} -x_{4})}},}$

avec:

${\displaystyle (P_{x},P_{y})=(x_{1}+t(x_{2}-x_{1}),\;y_{1}+t(y_{2}-y_{ 1}))\quad {\text{ou}}\quad (P_{x},P_{y})=(x_{3}+u(x_{4}-x_{3}),\;y_{ 3}+u(y_{4}-y_{3}))}$

Il y aura une intersection si 0,0  t  ≤ 1,0 et 0,0  u  1,0. Le point d'intersection se situe dans le premier segment de ligne si 0,0  t  1,0, et il se trouve dans le deuxième segment de ligne si 0,0  u  1,0. Ces inégalités peuvent être testées sans avoir besoin de division, ce qui permet de déterminer rapidement l'existence de toute intersection de segment de ligne avant de calculer son point exact.

Étant donné deux équations de droite

Les coordonnées et du point d'intersection de deux lignes non verticales peuvent être facilement trouvées en utilisant les substitutions et réarrangements suivants. ${\style d'affichage x}$${\style d'affichage y}$

Supposons que deux lignes ont les équations et où et sont les pentes (gradients) des lignes et où et sont les ordonnées à l' origine des lignes. Au point d'intersection des deux droites (si c'est le cas), les deux coordonnées seront les mêmes, d'où l'égalité suivante : ${\style d'affichage y=ax+c}$${\style d'affichage y=bx+d}$${\style d'affichage a}$${\style d'affichage b}$${\style d'affichage c}$${\style d'affichage d}$${\style d'affichage y}$

${\displaystyle hache+c=bx+d.}$

Nous pouvons réarranger cette expression afin d'extraire la valeur de , ${\style d'affichage x}$

${\displaystyle ax-bx=dc,}$

et donc,

${\displaystyle x={\frac {dc}{ab}}.}$

Pour trouver la coordonnée y , tout ce que nous avons à faire est de substituer la valeur de x dans l'une des deux équations linéaires, par exemple, dans la première :

${\displaystyle y=a{\frac {dc}{ab}}+c.}$

Le point d'intersection est donc

${\displaystyle P\left({\frac {dc}{ab}},a{\frac {dc}{ab}}+c\right).}$

Notez que si a = b alors les deux droites sont parallèles . Si c ≠ d ainsi, les lignes sont différentes et il n'y a pas d' intersection, sinon les deux lignes sont identiques.

Utiliser des coordonnées homogènes

En utilisant des coordonnées homogènes , le point d'intersection de deux lignes définies implicitement peut être déterminé assez facilement. En 2D, chaque point peut être défini comme une projection d'un point 3D, donné comme le triple ordonné . Le mappage des coordonnées 3D aux coordonnées 2D est . Nous pouvons convertir des points 2D en coordonnées homogènes en les définissant comme . ${\style d'affichage (x,y,w)}$${\displaystyle (x',y')=(x/w,y/w)}$${\style d'affichage (x,y,1)}$

Supposons que nous voulions trouver l'intersection de deux lignes infinies dans un espace à 2 dimensions, défini par et . Nous pouvons représenter ces deux lignes en coordonnées linéaires comme et , ${\displaystyle a_{1}x+b_{1}y+c_{1}=0}$${\style d'affichage a_{2}x+b_{2}y+c_{2}=0}$${\displaystyle U_{1}=(a_{1},b_{1},c_{1})}$${\displaystyle U_{2}=(a_{2},b_{2},c_{2})}$

L'intersection de deux droites est alors simplement donnée par, ${\style d'affichage P'}$

${\displaystyle P'=(a_{p},b_{p},c_{p})=U_{1}\times U_{2}=(b_{1}c_{2}-b_{2}c_{ 1},a_{2}c_{1}-a_{1}c_{2},a_{1}b_{2}-a_{2}b_{1})}$

Si les lignes ne se croisent pas. ${\style d'affichage c_{p}=0}$

Plus de deux lignes

L'intersection de deux lignes peut être généralisée pour impliquer des lignes supplémentaires. L'existence et l'expression du problème d'intersection à n lignes sont les suivantes.

En deux dimensions

En deux dimensions, plus de deux lignes ne se coupent presque certainement pas en un seul point. Pour déterminer si c'est le cas et, si c'est le cas, pour trouver le point d'intersection, écrivez la i- ième équation ( i = 1, …, n ) comme et empilez ces équations sous forme de matrice comme ${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}\end{bmatrix}}{\begin{bmatrix}x&y\end{bmatrix}}^{\mathsf {T}}=b_{i}, }$

${\style d'affichage Aw=b,}$

où la i -ième rangée de la matrice n × 2 A est , w est le vecteur 2 × 1 ( x, y ) ^T , et le i -ième élément du vecteur colonne b est b _i . Si A a des colonnes indépendantes, son rang est 2. Alors si et seulement si le rang de la matrice augmentée [ A | b ] vaut aussi 2, il existe une solution de l'équation matricielle et donc un point d'intersection des n droites. Le point d'intersection, s'il existe, est donné par ${\style d'affichage (a_{i1},a_{i2})}$

${\displaystyle w=A^{g}b=\left(A^{\mathsf {T}}A\right)^{-1}A^{\mathsf {T}}b,}$

où est l' inverse généralisé de Moore-Penrose de (qui a la forme indiquée car A a un rang de colonne complet). Alternativement, la solution peut être trouvée en résolvant conjointement deux équations indépendantes. Mais si le rang de A n'est que de 1, alors si le rang de la matrice augmentée est de 2, il n'y a pas de solution mais si son rang est de 1, alors toutes les lignes coïncident les unes avec les autres. ${\style d'affichage A^{g}}$${\style d'affichage A}$

En trois dimensions

L'approche ci-dessus peut être facilement étendue à trois dimensions. Dans trois dimensions ou plus, même deux lignes ne se coupent presque certainement pas ; les paires de lignes non parallèles qui ne se coupent pas sont appelées lignes obliques . Mais si une intersection existe, elle peut être trouvée, comme suit.

En trois dimensions une ligne est représentée par l'intersection de deux plans, dont chacun a une équation de la forme Ainsi un ensemble de n lignes peut être représenté par 2 n équations dans le vecteur de coordonnées tridimensionnel w = ( x , y , z ) ^T : ${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}&a_{i3}\end{bmatrix}}{\begin{bmatrix}x&y&z\end{bmatrix}}^{\mathsf {T}}=b_ {je}.}$

${\style d'affichage Aw=b}$

où maintenant A vaut 2 n × 3 et b vaut 2 n × 1. Comme précédemment, il existe un point d'intersection unique si et seulement si A a un rang de colonne complet et la matrice augmentée [ A | b ] ne le fait pas, et l'unique intersection si elle existe est donnée par

${\displaystyle w=\left(A^{\mathsf {T}}A\right)^{-1}A^{\mathsf {T}}b.}$

Points les plus proches des lignes obliques

Dans deux dimensions ou plus, nous pouvons généralement trouver un point qui est mutuellement le plus proche de deux ou plusieurs lignes au sens des moindres carrés .

En deux dimensions

Dans le cas à deux dimensions, d'une part, représente la ligne i à un point, sur la ligne et une unité de vecteur normal , perpendiculaire à cette ligne. Autrement dit, si et sont des points sur la ligne 1, alors laissez et laissez ${\style d'affichage p_{i}}$ ${\displaystyle {\hat {n}}_{i}}$${\style d'affichage x_{1}}$${\style d'affichage x_{2}}$${\style d'affichage p_{1}=x_{1}}$

${\displaystyle {\hat {n}}_{1} :={\begin{bmatrix}0&-1\\1&0\end{bmatrix}}{\frac {x_{2}-x_{1}}{\ |x_{2}-x_{1}\|}}}$

qui est le vecteur unitaire le long de la ligne, tourné de 90 degrés.

Notez que la distance d'un point, x à la ligne est donnée par ${\displaystyle (p,{\hat {n}})}$

${\displaystyle d(x,(p,n))=|(xp)\cdot {\hat {n}}|=\left|(xp)^{\top }{\hat {n}}\right| =\left|{\hat {n}}^{\top }(xp)\right|={\sqrt {(xp)^{\top }{\hat {n}}{\hat {n}}^ {\top }(xp)}}.}$

Et donc la distance au carré d'un point, x , à une ligne est

${\displaystyle d(x,(p,n))^{2}=(xp)^{\top }\left({\hat {n}}{\hat {n}}^{\top }\right )(xp).}$

La somme des carrés des distances à plusieurs lignes est la fonction de coût :

${\displaystyle E(x)=\sum _{i}(x-p_{i})^{\top }\left({\hat {n}}_{i}{\hat {n}}_{ i}^{\top }\right)(x-p_{i}).}$

Cela peut être réorganisé :

${\displaystyle {\begin{aligned}E(x)&=\sum _{i}x^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^ {\top }xx^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}-p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }x+p_{i}^{\top }{\hat {n}}_{i} {\hat {n}}_{i}^{\top }p_{i}\\&=x^{\top }\left(\sum _{i}{\hat {n}}_{i} {\hat {n}}_{i}^{\top }\right)x-2x^{\top }\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right)+\sum _{i}p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}.\end{aligned}}}$

Pour trouver le minimum, nous différencions par rapport à x et fixons le résultat égal au vecteur zéro :

${\displaystyle {\frac {\partial E(x)}{\partial x}}=0=2\left(\sum _{i}{\hat {n}}_{i}{\hat {n} }_{i}^{\top }\right)x-2\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\ haut }p_{i}\droit)}$

donc

${\displaystyle \left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x=\sum _{i} {\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}}$

et donc

${\displaystyle x=\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)^{-1}\ gauche(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right).}$

En plus de deux dimensions

Bien qu'il ne soit pas bien défini dans plus de deux dimensions, cela peut être généralisé à n'importe quel nombre de dimensions en notant qu'il s'agit simplement de la matrice (symétrique) avec toutes les valeurs propres unité à l'exception d'une valeur propre nulle dans la direction le long de la ligne fournissant une semi - norme sur la distance entre et un autre point donnant la distance à la ligne. Dans n'importe quel nombre de dimensions, si est un vecteur unitaire le long de la i- ème ligne, alors ${\displaystyle {\hat {n}}_{i}}$${\displaystyle {\hat {n}}_{i}{\hat {n}}_{i}^{\top }}$${\style d'affichage p_{i}}$${\displaystyle {\hat {v}}_{i}}$

${\displaystyle {\hat {n}}_{i}{\hat {n}}_{i}^{\top }}$ devient ${\displaystyle I-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }}$

où I est la matrice identité, et donc

${\displaystyle x=\left(\sum _{i}I-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }\right)^{-1 }\left(\sum _{i}\left(I-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }\right)p_{i}\ droit).}$

Dérivation générale

Afin de trouver le point d'intersection d'un ensemble de lignes, nous calculons le point à distance minimale d'elles. Chaque ligne est définie par une origine et un vecteur directeur unitaire, . Le carré de la distance d'un point à l'une des droites est donné par Pythagore : ${\style d'affichage a_{i}}$${\style d'affichage n_{i}}$${\style d'affichage p}$

${\displaystyle d_{i}^{2}=\left\|p-a_{i}\right\|^{2}-\left[\left(p-a_{i}\right)^{\mathsf {T}}*n_{i}\right]^{2}=\left(p-a_{i}\right)^{\mathsf {T}}*\left(p-a_{i}\right) -\left[\left(p-a_{i}\right)^{\mathsf {T}}*n_{i}\right]^{2}}$

Où : est la projection de sur la ligne . La somme des distances au carré à toutes les lignes est : ${\displaystyle {\left(p-a_{i}\right)}^{\mathsf {T}}*n_{i}}$${\displaystyle \left(p-{{a}_{i}}\right)}$${\style d'affichage i}$

${\displaystyle \sum _{i}d_{i}^{2}=\sum _{i}\left[{\left(p-a_{i}\right)^{\mathsf {T}}}* \left(p-a_{i}\right)-{\left[\left(p-a_{i}\right)^{\mathsf {T}}*n_{i}\right]^{2}} \droit]}$

Pour minimiser cette expression, nous la différencions par rapport à . ${\style d'affichage p}$

${\displaystyle \sum _{i}\left[2*\left(p-a_{i}\right)-2*\right[{{\left(p-a_{i}\right)}^{\ mathsf {T}}}*n_{i}]*n_{i}]=0}$

${\displaystyle \sum _{i}\left(p-a_{i}\right)=\sum _{i}\left[n_{i}*n_{i}^{\mathsf {T}}\right ]*\gauche(p-a_{i}\droit)}$

Il en résulte:

${\displaystyle \left[\sum _{i}\left[I-{n_{i}}*{n_{i}}^{\mathsf {T}}\right]\right]*p=\sum _ {i}\left[I-{n_{i}}*{n_{i}}^{\mathsf {T}}\right]*{a_{i}}}$

Où est la matrice d'identité. Il s'agit d'une matrice , de solution , où est le pseudo-inverse de . ${\style d'affichage I}$${\style d'affichage S*p=C}$${\style d'affichage p={S^{+}}*C}$${\style d'affichage {S}^{+}}$${\style d'affichage S}$

Voir également

• Intersection de segments de ligne
• Intersection de lignes dans l'espace projectif
• Distance entre deux droites parallèles
• Distance d'un point à une ligne
• Intersection ligne-plan
• Postulat parallèle
• Triangulation (vision par ordinateur)
• Intersection (géométrie euclidienne) § Deux segments de droite

Les références

Liens externes

• Distance entre les lignes et les segments avec leur point d'approche le plus proche , applicable à deux, trois ou plusieurs dimensions.