تقاطع خطين

_{أولاً ،} ندرس تقاطع خطين L1 و L2 ^{في فضاء} ثنائي الأبعاد، حيث ^يتم تعريف الخط L1 بنقطتين مختلفتين ( x1 , y1 ) و ( _x2 , _{y2 )} ، ويتم تعريف الخط L2 بنقطتين _{مختلفتين} ( x3 _, y3 ₎ و ( _{x4 , y4} ) _. [ 6 ]

يمكن تعريف نقطة التقاطع P للخطين L1 و _L2 باستخدام _{المحددات} .

${\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}}}\,\!}$

يمكن كتابة المحددات على النحو التالي:

${\displaystyle {\begin{aligned}P_{x}&={\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})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}\\[4px]P_{y}&={\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})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}\end{aligned}}}$

عندما يكون الخطان متوازيين أو متطابقين، يكون المقام صفرًا.

تمثل نقطة التقاطع المذكورة أعلاه الخطوط الطويلة جدًا المحددة بالنقاط، وليس القطع المستقيمة بين النقاط، ويمكن أن ينتج عنها نقطة تقاطع لا تقع ضمن أي من القطعتين المستقيمتين. ولإيجاد موضع التقاطع بالنسبة للقطعتين المستقيمتين، يمكننا تعريف الخطين L1 و _{L2 بدلالة معاملات} بيزير من الدرجة الأولى .

${\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}}}$

(حيث t و u عددان حقيقيان). يتم إيجاد نقطة تقاطع الخطوط بإحدى القيم التالية لـ t أو u ، حيث

${\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})}}}$

و

${\displaystyle u=-{\frac {\begin{vmatrix}x_{1}-x_{2}&x_{1}-x_{3}\\y_{1}-y_{2}&y_{1}-y_{3}\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_{2})(y_{1}-y_{3})-(y_{1}-y_{2})(x_{1}-x_{3})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}},}$

مع

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

يحدث تقاطع إذا كان 0 ≤ t ≤ 1 و 0 ≤ u ≤ 1. تقع نقطة التقاطع ضمن القطعة المستقيمة الأولى إذا كان 0 ≤ t ≤ 1 ، وتقع ضمن القطعة المستقيمة الثانية إذا كان 0 ≤ u ≤ 1. يمكن اختبار هذه المتباينات دون الحاجة إلى القسمة، مما يسمح بتحديد سريع لوجود أي تقاطع بين القطع المستقيمة قبل حساب نقطته بدقة. ^{[ 7 ]}

في حالة اشتراك القطعتين المستقيمتين في محور السينات و${\displaystyle x_{2}=x_{1}+1}$،${\displaystyle t}$و${\displaystyle u}$تبسيط إلى $${\displaystyle t=u={\frac {y_{1}-y_{3}}{y_{1}-y_{2}-y_{3}+y_{4}}},}$$ مع $${\displaystyle (P_{x},P_{y})={\bigl (}x_{1}+t,\;y_{1}+t(y_{2}-y_{1}){\bigr )}\quad {\text{or}}\quad (P_{x},P_{y})={\bigl (}x_{1}+t,\;y_{3}+t(y_{4}-y_{3}){\bigr )}.}$$

يمكن إيجاد إحداثيات x و y لنقطة تقاطع خطين غير رأسيين بسهولة باستخدام عمليات الاستبدال وإعادة الترتيب التالية.

لنفترض أن لدينا خطين مستقيمين معادلتيهما y = ax + c و y = bx + d، حيث a و b هما ميل الخطين (انحدارهما)، و c و d هما نقطتا تقاطع الخطين مع المحور y . عند نقطة تقاطع الخطين (إن وُجدت)، ستكون إحداثيات y متساوية، ومن ثمّ تتحقق المساواة التالية:

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

يمكننا إعادة ترتيب هذا التعبير لاستخراج قيمة x ،

${\displaystyle ax-bx=d-c,}$

وهكذا،

${\displaystyle x={\frac {d-c}{a-b}}.}$

لإيجاد الإحداثي y ، كل ما نحتاج إليه هو استبدال قيمة x في أي من معادلتي الخط، على سبيل المثال، في المعادلة الأولى:

${\displaystyle y=a{\frac {d-c}{a-b}}+c.}$

وبالتالي، فإن نقطة التقاطع هي

${\displaystyle P=\left({\frac {d-c}{a-b}},a{\frac {d-c}{a-b}}+c\right).}$

لاحظ أنه إذا كان a = b فإن الخطين متوازيان ولا يتقاطعان، إلا إذا كان c = d أيضًا، وفي هذه الحالة يكون الخطان متطابقين ويتقاطعان عند كل نقطة.

باستخدام الإحداثيات المتجانسة ، يمكن تحديد نقطة تقاطع خطين مُعرَّفين ضمنيًا بسهولة تامة. في بُعدين، يمكن تعريف كل نقطة على أنها إسقاط لنقطة ثلاثية الأبعاد، مُعطاة بالثلاثية المرتبة ( س ، ص ، ع ) . التحويل من الإحداثيات ثلاثية الأبعاد إلى ثنائية الأبعاد هو ( س '، ص ') = ( س / ع ، ص / ع ) . يمكننا تحويل النقاط ثنائية الأبعاد إلى إحداثيات متجانسة بتعريفها على أنها ( س ، ص ، ١ ) .

^{لنفترض أننا} _{نريد إيجاد نقطة} تقاطع خطين لانهائيين في فضاء ثنائي الأبعاد، مُعرَّفين بالمعادلتين: _a₁x + b₁y + c₁ = 0 _و a₂x + b₂y ₊ c₂ = 0. يمكننا تمثيل هذين الخطين بإحداثيات خطية كالتالي : U₁ = ( a₁ , b₁ , _c₁ ) و U₂ ₌ ( _a₂ , _b₂ , c₂ ₎ . وبالتالي ، _فإن نقطة التقاطع P ′ بين الخطين _تُعطى ببساطة ^{بالمعادلة} [ _{8 ] .}

${\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})}$

إذا كانت قيمة c _p تساوي 0 ، فإن الخطوط لا تتقاطع.

في بُعدين، من شبه المؤكد أن أكثر من خطين لا يتقاطعان في نقطة واحدة. لتحديد ما إذا كانا يتقاطعان، وإذا كان الأمر كذلك، لإيجاد نقطة التقاطع، اكتب المعادلة رقم i (حيث i = 1، ...، n ) على النحو التالي:

${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}=b_{i},}$

وقم بتجميع هذه المعادلات في شكل مصفوفة كما يلي:

${\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} ,}$

حيث يمثل الصف i من المصفوفة A ذات الأبعاد n × 2 العنصر [ a _{i 1} , a _{i 2} ] ، و w هو المتجه ذو الأبعاد 2 × 1 [ ^x _y ] ، والعنصر i من متجه العمود b هو b _i . إذا كانت أعمدة A مستقلة، فإن رتبتها تساوي 2. عندئذٍ ، إذا وفقط إذا كانت رتبة المصفوفة الموسعة [ A | b ] تساوي 2 أيضًا، يوجد حل لمعادلة المصفوفة، وبالتالي توجد نقطة تقاطع للخطوط n . تُعطى نقطة التقاطع، إن وُجدت، بالعلاقة التالية:

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

حيث A ^g هي المعكوس المعمم لمور-بنروز للمصفوفة A ( والتي تأخذ الشكل الموضح لأن A ذات رتبة عمودية كاملة). بدلاً من ذلك، يمكن إيجاد الحل بحل أي معادلتين مستقلتين معًا. ولكن إذا كانت رتبة A هي 1 فقط، فإذا كانت رتبة المصفوفة الموسعة 2، فلا يوجد حل، أما إذا كانت رتبتها 1، فإن جميع الخطوط تتطابق.

يمكن بسهولة تطبيق المنهج المذكور أعلاه على ثلاثة أبعاد. في ثلاثة أبعاد أو أكثر، يكاد يكون من المستحيل ألا يتقاطع خطان؛ وتُسمى أزواج الخطوط غير المتوازية التي لا تتقاطع بالخطوط المتخالفة . ولكن إذا وُجد تقاطع، فيمكن إيجاده كما يلي.

في ثلاثة أبعاد، يُمثَّل الخط بتقاطع مستويين، لكل منهما معادلة على الصورة التالية:

${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}&a_{i3}\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}=b_{i}.}$

وبالتالي، يمكن تمثيل مجموعة من n خطًا بواسطة 2^ n معادلة في متجه الإحداثيات ثلاثي الأبعاد w :

${\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} }$

حيث A الآن من الرتبة 2n × 3 و b من الرتبة 2n × 1. وكما في السابق، توجد نقطة تقاطع وحيدة إذا وفقط إذا كانت A ذات رتبة عمودية كاملة والمصفوفة الموسعة [ A | b ] ليست كذلك، والتقاطع الوحيد، إن وُجد، يُعطى بالعلاقة التالية:

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

في الحالة ثنائية الأبعاد، نمثل أولاً الخط i بنقطة pᵢ على الخط ومتجه وحدة عمودي n̂ᵢ عليه. أي، إذا كانت x₁ و x₂ نقطتين على الخط i _{، فإن} p₁ = _x₁ و n̂ᵢ _{= n̂ᵢ .}

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

وهو متجه الوحدة على طول الخط، بعد تدويره بزاوية قائمة.

المسافة من النقطة x إلى الخط ( p , n̂ ) تُعطى بالعلاقة التالية:

${\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}={\bigl |}(\mathbf {x} -\mathbf {p} )\cdot \mathbf {\hat {n}} {\bigr |}=\left|(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \right|=\left|\mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )\right|={\sqrt {(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )}}.}$

وبالتالي فإن مربع المسافة من النقطة س إلى الخط هو

${\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}^{2}=(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\left(\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} ).}$

مجموع مربعات المسافات إلى العديد من الخطوط هو دالة التكلفة :

${\displaystyle E(\mathbf {x} )=\sum _{i}(\mathbf {x} -\mathbf {p} _{i})^{\mathsf {T}}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} _{i}).}$

يمكن إعادة ترتيب هذا:

${\displaystyle {\begin{aligned}E(\mathbf {x} )&=\sum _{i}\mathbf {x} ^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {x} -\mathbf {x} ^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}-\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {x} +\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\\&=\mathbf {x} ^{\mathsf {T}}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} -2\mathbf {x} ^{\mathsf {T}}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)+\sum _{i}\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}.\end{aligned}}}$

لإيجاد القيمة الصغرى، نقوم بالتفاضل بالنسبة إلى x ونجعل النتيجة مساوية للمتجه الصفري:

${\displaystyle {\frac {\partial E(\mathbf {x} )}{\partial \mathbf {x} }}={\boldsymbol {0}}=2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} -2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)}$

لذا

${\displaystyle \left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} =\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}}$

وهكذا

${\displaystyle \mathbf {x} =\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right).}$

على الرغم من أن n̂ _i غير مُعرَّف جيدًا في أكثر من بُعدين، إلا أنه يُمكن تعميم ذلك على أي عدد من الأبعاد بملاحظة أن n̂ _i n̂ _i ^T هي ببساطة مصفوفة متناظرة جميع قيمها الذاتية تساوي واحدًا باستثناء قيمة ذاتية صفرية في الاتجاه الموازي للخط الذي يُوفر شبه معيار للمسافة بين p _i ونقطة أخرى تُعطي المسافة إلى الخط. في أي عدد من الأبعاد، إذا كان v̂ _i متجه وحدة على طول الخط i ، فإن

${\displaystyle \mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}}$يصبح${\displaystyle \mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}}$

حيث I هي مصفوفة الوحدة ، وبالتالي ^{[ 9 ]}

${\displaystyle x=\left(\sum _{i}\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)\mathbf {p} _{i}\right).}$

لإيجاد نقطة تقاطع مجموعة من الخطوط، نحسب النقطة الأقرب إليها. يُعرَّف كل خط بنقطة أصل aᵢ ومتجه اتجاه وحدة n̂ᵢ _. يُعطى مربع المسافة من نقطة p إلى أحد الخطوط باستخدام نظرية فيثاغورس _.

${\displaystyle d_{i}^{2}=\left\|\mathbf {p} -\mathbf {a} _{i}\right\|^{2}-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}=\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}$

حيث ( p − ai ₎ ^Tn̂i هو إسقاط p − ai على الخط i . مجموع المسافات إلى المربع لجميع _{الخطوط هو}

${\displaystyle \sum _{i}d_{i}^{2}=\sum _{i}\left({\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-{\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}\right)}$

لتقليل هذا التعبير، نقوم بتفاضله بالنسبة إلى p .

${\displaystyle \sum _{i}\left(2\left(\mathbf {p} -\mathbf {a} _{i}\right)-2\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)\mathbf {\hat {n}} _{i}\right)={\boldsymbol {0}}}$

${\displaystyle \sum _{i}\left(\mathbf {p} -\mathbf {a} _{i}\right)=\sum _{i}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\left(\mathbf {p} -\mathbf {a} _{i}\right)}$

مما ينتج عنه

${\displaystyle \left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\right)\mathbf {p} =\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {a} _{i}}$

حيث I هي مصفوفة الوحدة . هذه مصفوفة Sp = C ، وحلها p = S ⁺ C ، حيث S ⁺ هي المعكوس الزائف لـ S.