كيفية معرفة ما إذا كانت الأجزاء متقاطعة. تحديد نقطة تقاطع جزأين. نقطة التقاطع

نقطة التقاطع

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

حل

إذا كان المستقيمان غير متوازيين فإنهما متقاطعان. للعثور على نقطة التقاطع يكفي إنشاء نظام من معادلتين للخط المستقيم وحلها:

باستخدام صيغة كرامر، نجد على الفور حلاً للنظام، وهو الحل المطلوب نقطة التقاطع:

إذا كان المقام صفراً، أي.

ثم النظام ليس لديه حلول (direct موازيولا تتطابق) أو لديها عدد لا نهائي (مباشر مباراة). وإذا كان لا بد من التمييز بين هاتين الحالتين، فلا بد من التأكد من أن معاملات الخطوط متناسبة مع نفس معامل التناسب مثل المعاملات و، والتي يكفي لها حساب المحددين، إذا كانا كلاهما يساوي الصفر، فإن السطور متطابقة:

تطبيق

البنية pt(double x, y;); خط الهيكل (مزدوج أ، ب، ج؛)؛ ربحية السهم المزدوجة = 1e-9؛ det مزدوج (double a، double b، double c، double d)(return a * d - b * c;) bool intersect (line m، line n، pt & res) (double zn = det (m.a، m.b، n.a ، ن.ب)؛إذا (عبس (زن)< EPS)returnfalse; res.x=- det (m.c, m.b, n.c, n.b)/ zn; res.y=- det (m.a, m.c, n.a, n.c)/ zn;returntrue;} bool parallel (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS;} bool equivalent (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS &&abs(det (m.a, m.c, n.a, n.c))< EPS &&abs(det (m.b, m.c, n.b, n.c))< EPS;}

درس من سلسلة " الخوارزميات الهندسية»

مرحبا عزيزي القارئ.

نصيحة 1: كيفية العثور على إحداثيات نقطة تقاطع خطين

دعونا نكتب ثلاث وظائف جديدة أخرى.

ستحدد الدالة LinesCross() ما إذا كان تتقاطعسواء كان اثنان شريحة. في ذلك، يتم تحديد الموضع النسبي للقطاعات باستخدام منتجات المتجهات. لحساب منتجات المتجهات، سنكتب دالة – ​​VektorMulti().

سيتم استخدام الدالة RealLess() لتنفيذ عملية المقارنة "<” (строго меньше) для вещественных чисел.

مهمة 1. يتم إعطاء جزأين بواسطة إحداثياتهما. اكتب البرنامج الذي يحدد هل تتقاطع هذه القطع؟دون العثور على نقطة التقاطع.

حل
. والثاني يعطى بالنقاط.

النظر في الجزء والنقاط و .

تقع النقطة على يسار الخط، فهي حاصل الضرب المتجه > 0، لأن المتجهات موجهة بشكل إيجابي.

تقع النقطة على يمين الخط الذي يوجد به منتج المتجه < 0, так как векторы отрицательно ориентированы.

وحتى تكون النقاط على طرفي نقيض من الخط المستقيم، يكفي أن يكون الشرط متوافرا< 0 (векторные произведения имели противоположные знаки).

يمكن تنفيذ تفكير مماثل للقطعة والنقاط و .

حتى إذا ، ثم تتقاطع الأجزاء.

للتحقق من هذا الشرط، يتم استخدام الدالة LinesCross()، ويتم استخدام الدالة VektorMulti() لحساب المنتجات المتجهة.

الفأس، المنعم يوسف – إحداثيات المتجه الأول،

bx، بواسطة – إحداثيات المتجه الثاني.

برنامج Geometr4؛ (هل يتقاطع الجزءان؟) Const _Eps: Real=1e-4; (دقة الحساب) var x1,y1,x2,y2,x3,y3,x4,y4: حقيقي; var v1,v2,v3,v4: real;function RealLess(Const a, b: Real): Boolean; (بدقة أقل من) تبدأ RealLess:= b-a> _Eps end؛ (RealLess) وظيفة VektorMulti(ax,ay,bx,by:real): حقيقي; (ax,ay - إحداثيات bx,by - b إحداثيات) begin vektormulti:= ax*by-bx*ay; end;Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): منطقي; (هل تتقاطع المقاطع؟) تبدأ v1:=vektormulti(x4-x3,y4-y3,x1-x3,y1-y3); v2:=vektormulti(x4-x3,y4-y3,x2-x3,y2-y3); v3:=vektormulti(x2-x1,y2-y1,x3-x1,y3-y1); v4:=vektormulti(x2-x1,y2-y1,x4-x1,y4-y1); إذا كان RealLess(v1*v2,0) وRealLess(v3*v4,0) (v1v2)<0 и v3v4<0, отрезки пересекаются} then LinesCross:= true else LinesCross:= false end; {LinesCross}begin {main} writeln(‘Введите координаты отрезков: x1,y1,x2,y2,x3,y3,x4,y4’); readln(x1,y1,x2,y2,x3,y3,x4,y4); if LinesCross(x1,y1,x2,y2,x3,y3,x4,y4) then writeln (‘Да’) else writeln (‘Нет’) end.

نتائج تنفيذ البرنامج:

أدخل إحداثيات المقاطع: -1 1 2 2.52 2 1 -1 3
نعم.

لقد كتبنا برنامجًا يحدد ما إذا كانت القطع المحددة بإحداثياتها تتقاطع أم لا.

في الدرس التالي، سنقوم بإنشاء خوارزمية يمكن استخدامها لتحديد ما إذا كانت النقطة تقع داخل المثلث.

عزيزي القارئ.

لقد تعرفت بالفعل على العديد من الدروس من سلسلة الخوارزميات الهندسية. هل كل شيء مكتوب بطريقة يسهل الوصول إليها؟ سأكون ممتنًا جدًا إذا تركت تعليقات حول هذه الدروس. ربما لا يزال هناك شيء يحتاج إلى تحسين.

مع خالص التقدير، فيرا جوسبوداريتس.

دعونا نعطي جزأين. يتم إعطاء الأول بالنقاط ف 1 (س 1 ؛ص 1)و ف 2 (س 2 ؛ ص 2). والثاني يتم إعطاءه بالنقاط ص 3 (× 3 ؛ص 3)و ص 4 (× 4 ؛ص 4).

يمكن التحقق من الموضع النسبي للقطاعات باستخدام منتجات المتجهات:

النظر في هذا الجزء ص 3 ص 4والنقاط ص 1و ص2.

نقطة ص 1تقع على يسار الخط ص 3 ص 4، لها المنتج المتجه الخامس 1 > 0، لأن المتجهات موجهة بشكل إيجابي.
نقطة ص2يقع على يمين السطر، لأنه المنتج المتجه ضد 2< 0 ، لأن المتجهات موجهة بشكل سلبي.

لتوضيح هذه النقطة ص 1و ص2تقع على جانبي متقابلين من خط مستقيم ص 3 ص 4، فإنه يكفي لتحقيق الشرط ضد 1 ضد 2< 0 (كانت المنتجات المتجهة لها علامات معاكسة).

ويمكن تنفيذ منطق مماثل لهذا القطاع ف1 ف2والنقاط ص 3و ص 4.

حتى إذا ضد 1 ضد 2< 0 و الخامس 3 ضد 4< 0 ، ثم تتقاطع الأجزاء.

يتم حساب المنتج المتجه لمتجهين باستخدام الصيغة:

أين:
فأس, نعم- إحداثيات المتجه الأول،
bx, بواسطة— إحداثيات المتجه الثاني.

معادلة الخط الذي يمر عبر نقطتين مختلفتين تحددهما إحداثياتهما.

افترض وجود نقطتين غير متطابقتين على خط مستقيم: ص 1بالإحداثيات ( × 1 ؛ص 1)و ص2مع الإحداثيات (س 2 ؛ ص 2).

تقاطع الخطوط

وبناء على ذلك، فإن المتجه له أصل عند هذه النقطة ص 1وتنتهي عند نقطة ما ص2لديه إحداثيات (س 2 - س 1 , ص 2 - ص 1). لو ف(س، ص)هي نقطة تعسفية على الخط، ثم إحداثيات المتجه ص 1 صمتساوي (س - س 1، ص - ص 1).

باستخدام منتج المتجهات، شرط العلاقة الخطية المتداخلة بين المتجهات ص 1 صو ف1 ف2يمكن كتابتها مثل هذا:
|P 1 P,P 1 P 2 |=0، أي. (س-س 1)(ص 2 -ص 1)-(ص-ص 1)(س 2 -س 1)=0
أو
(ص 2 -ص 1)س + (س 1 -س 2)ص + س 1 (ص 1 -ص 2) + ص 1 (س 2 -س 1) = 0

تتم إعادة كتابة المعادلة الأخيرة على النحو التالي:
الفأس + بواسطة + ج = 0، (1)
أين
أ = (ص 2 -ص 1)،
ب = (س 1 - س 2)،
ج = س 1 (ص 1 -ص 2) + ص 1 (س 2 - س 1)

لذلك يمكن تحديد الخط المستقيم بمعادلة على الصورة (1).

كيفية العثور على نقطة تقاطع الخطوط؟
الحل الواضح هو حل نظام المعادلات الخطية:

الفأس 1 + بمقدار 1 = - ج 1
الفأس 2 + ب 2 = - ج 2 (2)

أدخل الرموز:

هنا دهو المحدد للنظام، و دي إكس، دي— المحددات الناتجة عن استبدال عمود المعاملات بالمجهول المقابل بعمود المصطلحات الحرة. لو د ≠ 0، فإن النظام (2) محدد، أي أن له حلًا فريدًا. يمكن العثور على هذا الحل باستخدام الصيغ التالية: × 1 =د × /د، ص 1 =د ذ /دوالتي تسمى صيغ كرامر. تذكير سريع بكيفية حساب محدد الدرجة الثانية. يميز المحدد بين قطرين: الرئيسي والثانوي. يتكون القطر الرئيسي من عناصر مأخوذة في الاتجاه من الزاوية اليسرى العليا للمحدد إلى الزاوية اليمنى السفلية. قطري جانبي - من أعلى اليمين إلى أسفل اليسار. المحدد الثاني يساوي حاصل ضرب عناصر القطر الرئيسي مطروحًا منه حاصل ضرب عناصر القطر الثانوي.

دعونا نعطي جزأين. يتم إعطاء الأول بالنقاط ف 1 (س 1 ؛ص 1)و ف 2 (س 2 ؛ ص 2). والثاني يتم إعطاءه بالنقاط ص 3 (× 3 ؛ص 3)و ص 4 (× 4 ؛ص 4).

يمكن التحقق من الموضع النسبي للقطاعات باستخدام منتجات المتجهات:

النظر في هذا الجزء ص 3 ص 4والنقاط ص 1و ص2.

نقطة ص 1تقع على يسار الخط ص 3 ص 4، لها المنتج المتجه الخامس 1 > 0، لأن المتجهات موجهة بشكل إيجابي.
نقطة ص2يقع على يمين السطر، لأنه المنتج المتجه ضد 2< 0 ، لأن المتجهات موجهة بشكل سلبي.

لتوضيح هذه النقطة ص 1و ص2تقع على جانبي متقابلين من خط مستقيم ص 3 ص 4، فإنه يكفي لتحقيق الشرط ضد 1 ضد 2< 0 (كانت المنتجات المتجهة لها علامات معاكسة).

ويمكن تنفيذ منطق مماثل لهذا القطاع ف1 ف2والنقاط ص 3و ص 4.

حتى إذا ضد 1 ضد 2< 0 و الخامس 3 ضد 4< 0 ، ثم تتقاطع الأجزاء.

يتم حساب المنتج المتجه لمتجهين باستخدام الصيغة:

أين:
فأس, نعم- إحداثيات المتجه الأول،
bx, بواسطة- إحداثيات المتجه الثاني.

معادلة الخط الذي يمر عبر نقطتين مختلفتين تحددهما إحداثياتهما.

افترض وجود نقطتين غير متطابقتين على خط مستقيم: ص 1بالإحداثيات ( × 1 ؛ص 1)و ص2مع الإحداثيات (س 2 ؛ ص 2). وبناء على ذلك، فإن المتجه له أصل عند هذه النقطة ص 1وتنتهي عند نقطة ما ص2لديه إحداثيات (س 2 - س 1 , ص 2 - ص 1). لو ف(س، ص)هي نقطة تعسفية على الخط، ثم إحداثيات المتجه ص 1 صمتساوي (س - س 1، ص - ص 1).

باستخدام منتج المتجهات، شرط العلاقة الخطية المتداخلة بين المتجهات ص 1 صو ف1 ف2يمكن كتابتها مثل هذا:
|P 1 P ,P 1 P 2 |=0، أي. (س-س 1)(ص 2 -ص 1)-(ص-ص 1)(س 2 -س 1)=0
أو
(ص 2 -ص 1)س + (س 1 -س 2)ص + س 1 (ص 1 -ص 2) + ص 1 (س 2 -س 1) = 0

تتم إعادة كتابة المعادلة الأخيرة على النحو التالي:
الفأس + بواسطة + ج = 0، (1)
أين
أ = (ص 2 -ص 1)،
ب = (س 1 - س 2)،
ج = س 1 (ص 1 -ص 2) + ص 1 (س 2 - س 1)

لذلك يمكن تحديد الخط المستقيم بمعادلة على الصورة (1).

كيفية العثور على نقطة تقاطع الخطوط؟
الحل الواضح هو حل نظام المعادلات الخطية:

الفأس 1 + بمقدار 1 = - ج 1
الفأس 2 + ب 2 = - ج 2 (2)

أدخل الرموز:

هنا دهو المحدد للنظام، و دي إكس، دي- المحددات الناتجة عن استبدال عمود المعاملات بالمجهول المقابل بعمود المصطلحات الحرة. لو د ≠ 0، فإن النظام (2) محدد، أي أن له حلًا فريدًا. يمكن العثور على هذا الحل باستخدام الصيغ التالية: × 1 =د × /د، ص 1 =د ذ /دوالتي تسمى صيغ كرامر. تذكير سريع بكيفية حساب محدد الدرجة الثانية. يميز المحدد بين قطرين: الرئيسي والثانوي. يتكون القطر الرئيسي من عناصر مأخوذة في الاتجاه من الزاوية اليسرى العليا للمحدد إلى الزاوية اليمنى السفلية. قطري جانبي - من أعلى اليمين إلى أسفل اليسار. المحدد الثاني يساوي حاصل ضرب عناصر القطر الرئيسي مطروحًا منه حاصل ضرب عناصر القطر الثانوي.