محتويات هذه المقالة أساسية للغاية ، خاصة للمبتدئين مثلي ، لذا يرجى طلب جميع أباطرة الخوارزمية لإلقاء نظرة سريعة
يقتبس
من المعروف أن قطاع الخط 1 (أ ، ب) وقطعة الخط 2 (ج ، د) ، حيث ABCD هي نقطة النهاية ، ابحث عن نقطة التقاطع P في مقطع الخط. (تعتبر الخطوط المتوازية أو الخطية مفككة)
الخوارزمية 1: ابحث عن نقطة التقاطع للخط المستقيم حيث توجد شرائح الخطين ، ثم حدد ما إذا كانت نقطة التقاطع على قطعي الخطين.
عند العثور على نقطة التقاطع للخط المستقيم ، يمكننا أن نجدها من خلال المعادلة العامة لـ AX+بواسطة+C = 0 من الخط المستقيم (ABC في المعادلة هي معامل ، وليس نقطة النهاية المذكورة أعلاه. بالإضافة إلى ذلك ، يمكن أيضًا استخدام المعادلات المائلة للنقطة ومعادلات التقاطع المائل ، وليس هنا الآن).
بعد ذلك ، استنادًا إلى العلاقة الموضعية بين نقطة التقاطع ونقطة نهاية قطاع الخط ، يمكننا الحكم على ما إذا كانت نقطة التقاطع على شريحة الخط.
الصيغة كما يلي:
<code> SigmentSintr (A ، B ، C ، D) { /** 1 حل نظام المعادلات الخطية وإيجاد تقاطع شرائح الخط. **/// إذا كان المقام 0 ، فهو متوازي أو يتخطى ، ولا يتقاطع مع var var = (by - Ay)*(dx - cx) - (ax - bx)*(cy - dy) ؛ if (alminator == 0) {return false ؛ } // إحداثي التقاطع للخط المستقيم حيث يوجد جزء الخط (x ، y) var x = (bx - ax) * (dx - cx) * (cy - ay) + (by - ay) * (dx - cx) * ax - (dy - cy) * (bx - ax) * cx) / cenominator ؛ var y = - ((by - ay) * (dy - cy) * (cx - ax) + (bx - ax) * (dy - cy) * ay - (dx - cx) * (by - ay) * cy) / ** 2 تحديد ما إذا كان التقاطع موجودًا في قسمين **/ إذا (// التقاطع هو الجزء على الجزء 1 (x - ax) * (x - bx) <= 0 && (y - y) * (y - by) <= 0 // و intersection أيضًا على المقطع 2 && (x - cx) * (x - dx) <= 0 & ~ // العودة إلى التقاطع p return {x: x ، y: y}} // خلاف ذلك ، إرجاع disjoint false} </code>تحتوي الخوارزمية أولاً على فكرة واضحة وسهلة الفهم ، لكن أدائها ليس مرتفعًا. لأنه يحسب التقاطع قبل أن يكون غير متأكد مما إذا كان التقاطع صالحًا (في الجزء عبر الإنترنت) ، والذي يستغرق الكثير من الوقت.
إذا تم العثور على نقطة التقاطع في النهاية على أنها غير صالحة ، فسيكون الحساب السابق عبثًا. علاوة على ذلك ، فإن عملية الحساب بأكملها معقدة للغاية.
هل هناك طريقة لمعرفة ما إذا كانت هناك نقطة تقاطع فعالة أولاً ثم حسابها؟
من الواضح أن الجواب نعم. لذلك تم العثور على بعض الخوارزميات.
الخوارزمية 2: حدد ما إذا كانت النقطتين النهائيتين لكل مقطع خط على جانبي مقطع الخط الآخر. ثم ابحث عن تقاطع الخط المستقيم حيث يوجد شرحان من الخطين ، وإلا فإنهما لا يتقاطعان.
الخطوة الأولى هي تحديد ما إذا كانت نقطتان على جانبي مقطع خط معين. يمكن عادة استخدام طريقة الإسقاط:
ابحث عن المتجه الطبيعي لقطاع الخط ، ثم عرض النقطة على الخط العادي ، وأخيراً الحكم على العلاقة بين النقطة وشريحة الخط بناءً على الموضع المتوقع.
انظر الصورة أدناه
يظهر الإسقاط على قرص خطوط الخط العادي للنقطة A والنقطة B في الشكل. في هذا الوقت ، نحتاج أيضًا إلى عرض قرص خطوط خطوط خط على خطنا العادي (فقط حدد واحدة من النقطة C أو النقطة D).
يستخدم بشكل رئيسي للرجوع إليه.
في الشكل ، يتم إسقاط إسقاط النقطة A والنقطة B على جانبي الإسقاط من النقطة C ، مما يشير إلى كلا الجانبين من CD Sister CD لقطاع الخط AB.
وبالمثل ، فقط تحكم على ما إذا كان القرص المضغوط على جانبي الجزء الخط AB مرة أخرى.
يبدو العثور على القواعد الطبيعية والإسقاط وغيرها من الأشياء معقدة للغاية ، ولكن في الواقع ، فهي في الواقع معقدة للغاية بالنسبة لي. لم أكن أعرف الكثير عن المعرفة الهندسية قبل بضعة أشهر (لقد نسيت كل معرفة الهندسة عندما كنت أدرس: "()"
لحسن الحظ ، فإن التعلم والتنفيذ ليسوا معقدين ، وهناك صيغ يجب اتباعها.
ابحث عن الجزء الطبيعي لخط المقطع AB:
var nx = by - ay ، ny = ax - bx ؛ var normalline = {x: nx ، y: ny} ؛ ملاحظة: حيث تمثل المعاني الهندسية لـ normalLine.x و normalLine.y اتجاه الخط العادي ، وليس الإحداثيات.
ابحث عن موضع الإسقاط للنقطة C على الخط العادي:
var dist = normalline.x*cx + normalline.y*cy ؛
ملاحظة: "موضع الإسقاط" هنا هو عداد ، وهو يمثل المسافة إلى أصل الطبيعي ، وليس إحداثيات نقطة الإسقاط.
عادة ما يكون ذلك يكفي لمعرفة هذه المسافة.
بعد حساب إسقاط النقاط A (DISTA) ، النقطة B (DISTB) ، والنقطة C (DISTC) في الشكل ، يمكننا بسهولة الحكم على الموقف النسبي بناءً على أحجام كل منهما.
عندما dista == distb == distc ، فإن الجزءين هما خطية متداخلة
عندما dista == distb! = distc ، فإن قطعتين متوازيين
عندما يكون Dista و Distb على نفس الجانب من DISTC ، لا يتقاطع شرائح الخطان.
عندما يكون Dista و Distb على الجانب الآخر من DISTC ، ما إذا كان يجب الحكم على ما إذا كان يتقاطع الجزءان المتقاطعان مرة أخرى ما إذا كانت العلاقة بين النقطة C و SINE SISTION AB.
الخطوات السابقة تنفذ فقط "الحكم على شرائح الخطوط المتقاطعة". عندما تكون النتيجة صحيحة ، نحتاج إلى مزيد من العثور على نقطة التقاطع.
دعنا نتحدث عن عملية العثور على نقطة التقاطع لاحقًا. دعونا أولاً نلقي نظرة على التنفيذ الكامل لهذه الخوارزمية:
وظائف SigmentSintr (A ، B ، C ، D) {// natorm n1 var nx1 = (by - ay) ، ny1 = (ax - bx) ؛ // normal n2 var nx2 = (dy - cy) ، ny2 = (cx - dx) ؛ // يتم مضاعفة اثنين من القواعد الطبيعية ، إذا كانت النتيجة 0 ، فهذا يعني أن قطاع الخط AB و CD Segment CD متوازيين أو متداخلين ، ولا يتقاطعان مع FAR STIMMATITATOR = NX1*NY2 - NY1*NX2 ؛ if (alminator == 0) {return false ؛ } // الإسقاط على n2 var distc_n2 = nx2 * cx + ny2 * cy ؛ var dista_n2 = nx2 * ax + ny2 * ay-distc_n2 ؛ var distb_n2 = nx2 * bx + ny2 * by-distc_n2 ؛ // إسقاط النقطة A والنقطة B على نفس الجانب من الإسقاط النقطة C (بالنسبة للحالة الموجودة في شريحة الخط ، يتم التعامل مع هذا المثال على أنه مفكك) ؛ if (dista_n2*distb_n2> = 0) {return false ؛ } // // ugn exced in the point c point d point d and line spiction ab ، المبدأ هو نفسه كما هو موضح أعلاه // // الإسقاط على n1 var dista_n1 = nx1 * ax + ny1 * ay ؛ var distc_n1 = nx1 * cx + ny1 * cy-dista_n1 ؛ var distd_n1 = nx1 * dx + ny1 * dy-dista_n1 ؛ if (distc_n1*distd_n1> = 0) {return false ؛ }. var dx = fraction * ny1 ، dy = -fraction * nx1 ؛ إرجاع {x: ax + dx ، y: ay + dy} ؛ }تبدو الطريقة المستخدمة للعثور على إحداثيات نقطة التقاطع في النهاية غريبة بعض الشيء ، ويبدو أنها غير واضحة.
في الواقع ، فهو مشابه لخوارزمية في الخوارزمية 1 ، باستثناء أن العديد من مصطلحات الحساب تم حسابها مسبقًا.
وبعبارة أخرى ، فإن جزء الخوارزمية للعثور على إحداثيات نقطة التقاطع في ميلين مصنوعة بالفعل من معادلات خطية لخط مستقيم.
الآن دعونا نقارن الخوارزمية والخوارزمية اثنان بطريقة بسيطة وخشنة وغير علمية:
1. في أفضل حالة ، تعقيد الخوارزميات هو نفسه
2. في أسوأ الحالات ، فإن كمية الحساب للخوارزمية 1 والخوارزمية 2 هي نفسها تقريبًا
3. ومع ذلك ، توفر الخوارزمية 2 "شروط النهاية المبكرة" ، لذلك في المتوسط ، يجب أن تكون الخوارزمية 2 أفضل.
بعد الاختبار الفعلي ، يكون الوضع الفعلي هو الحال بالفعل.
الخوارزميات السابقة شائعة بشكل أساسي ويمكنها التعامل مع معظم المواقف. ولكن في الواقع ، هناك خوارزمية أفضل.
هذا ما تعلمته للتو مؤخرًا (لقد تعلمته الآن وبيعته الآن ، لا تمانع في ذلك ...)
الخوارزمية 3: حدد ما إذا كانت النقطتين النهائيتين لكل مقطع خط على جانبي قطاع الخط الآخر. إذا وجدت تقاطع الخط المستقيم حيث توجد قطعي الخطين ، وإلا فلن يتقاطعان.
(هاه؟ لماذا تشعر بنفس الخوارزمية 2؟ لا تشك في أنها هي نفسها ...)
ما يسمى الخوارزمية 3 هو في الواقع مجرد تحسن في الخوارزمية 2. التحسينات الرئيسية هي:
لا يتم الحكم على العلاقة الموضعية بين النقاط وشرائح الخط من خلال الإسقاط الطبيعي ، ولكن في مجال المثلثات المكونة من نقاط وقطاعات خط.
دعنا أولاً نراجع صيغة منطقة المثلث: من المعروف أن النقاط الثلاث (x ، y) b (x ، y) c (x ، y) من منطقة المثلث هي:
<code> var triarea = ((ax - cx) * (by - cy) - (Ay - cy) * (bx - cx)) /2 ؛ </code>
نظرًا لأن مساحة المتوازيين (متجهان متجاوران) يتكونان من اثنين من المتجهات المتجهة == المتجهين ، فإن الصيغة أعلاه ليس من الصعب فهمها.
علاوة على ذلك ، نظرًا لأن المتجهات لها اتجاهات ، فإن المنطقة لديها أيضًا اتجاهات. عادة ، نستخدم عكس اتجاه عقارب الساعة الإيجابية وعلى مدار الساعة السلبية.
النقاط الرئيسية للخوارزمية المحسنة هي:
إذا كانت العلامات الإيجابية والسلبية لمنطقة المثلث التي تشكلت بواسطة "خط الخط AB والنقطة C" تختلف عن منطقة المثلث التي تتكون من "خط خط AB والنقطة D" ،
ثم تقع النقطة C والنقطة D على جانبي الجزء AB.
كما هو مبين في الشكل أدناه:
يحتوي المثلث الذي يظهره الخط المنقط في الشكل على اتجاهات متعرج مختلفة (ترتيب تعريف الجوانب الثلاثة) ، وبالتالي فإن الرموز الإيجابية والسلبية للمنطقة مختلفة.
دعونا نلقي نظرة على الرمز أولاً:
نظرًا لأننا بحاجة فقط إلى الحكم على الرمز ، لا نحتاج إلى تقسيم ما يلي على 2 في صيغة منطقة المثلث السابقة.
وظائف SigmentSintr (A ، B ، C ، D) {// 2 أضعاف مساحة المثلث abc var area_abc = (ax - cx) * (by - cy) - (ay - cy) * (bx - cx) ؛ // 2 أضعاف مساحة المثلث abd var area_abd = (ax - dx) * (by - dy) - (ay - dy) * (bx - dx) ؛ // إذا كانت رموز المنطقة هي نفسها ، فإن النقطتين لا تتقاطعان على نفس الجانب (في حالة النقطة الموجودة على شريحة الخط ، يتم التعامل مع هذا المثال على أنه مفكك) ؛ if (area_abc*area_abd> = 0) {return false ؛ } // 2 أضعاف مساحة المثلث cda var area_cda = (cx - ax) * (dy - ay) - (cy - ay) * (dx - ax) ؛ // 2 أضعاف مساحة المثلث CDB // ملاحظة: هناك تحسين صغير هنا. ليست هناك حاجة لحساب المنطقة باستخدام الصيغة ، ولكن يتم اشتقاقها عن طريق إضافة وطرح المناطق الثلاثة المعروفة. var area_cdb = area_cda + area_abc - area_abd ؛ if (area_cda * area_cdb> = 0) {return false ؛ } // حساب إحداثيات التقاطع var t = area_cda / (area_abd- area_abc) ؛ var dx = t*(bx - ax) ، dy = t*(by - ay) ؛ إرجاع {x: ax + dx ، y: ay + dy} ؛ }أخيرًا ، الجزء الذي يحسب إحداثيات التقاطع هو نفس الخوارزمية.
استنادًا إلى الخوارزمية 2 ، تبسط الخوارزمية 3 بشكل كبير خطوات الحساب ويكون الرمز أكثر تبسيطًا. يمكن القول أنه الأفضل بين الخوارزميات الثلاث. وينطبق الشيء نفسه على نتائج الاختبار الفعلية.
بالطبع ، يجب أن نكون صادقين ، في JavaScript ، التعقيد الزمني للخوارزميات الثلاثة متشابهة في الواقع للحسابات العادية (وخاصة تحت محرك V8).
في حالة الاختبار الخاصة بي ، أجريت أيضًا اختبارات تقاطع قطاع الخط المليون غير الطبيعية لتوسيع الفجوة بين الخوارزميات الثلاثة.
لخص
ومع ذلك ، مع موقف السعي من أجل التميز والتعلم ، فإن متابعة خوارزمية أفضل دائمًا لها أهميتها الإيجابية. ما ورد أعلاه عبارة عن العديد من الخوارزميات التي تستخدم JS لتحقيق نقاط تقاطع قطاع الخط. المحتوى ليس عميقًا جدًا. آمل أن يكون من المفيد للجميع أن يتعلموا JS.