إيجاد نقطة تقاطع خطين (ومقاطع خطية)

المقدمة

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

الأساليب الشعبية ونقدها

ربما يتذكر الكثيرون طريقة من الجبر المدرسي - لعمل معادلات من خطين مستقيمين ، ومساواة جانبيهما الأيمن ، وإيجاد x ، واستبدالها في معادلة الخط المستقيم لإيجاد y ( مزيد من التفاصيل هنا ).



ومع ذلك ، تصبح هذه الطريقة مرهقة للغاية عند كتابة التعليمات البرمجية (ربما هذا هو السبب في أنك تقرأ هذه المقالة الآن) ، علاوة على ذلك ، فهي ليست عامة: إذا كان أحد الخطوط المستقيمة موازيًا للمحور Y ، فسنحصل على قسمة على صفر خطأ عند حساب الميل ، وعلينا تسجيل رمز لهذه الحالة ؛ إذا كان هناك خطان متوازيان ، فأنت بحاجة إلى العبث بمعالجة هذه الحالة أيضًا. يصبح هذا الرمز طويلًا وقبيحًا.



بحثًا عن حل أكثر أناقة لهذه المشكلة ، عثرت على بعض الطرق الشيقة للغاية القائمة على ضرب المتجهات (habr.com/ru/post/267037 ) وصب الأشعة ( ru.wikipedia.org/wiki/Ray_casting#Concept ). لكن في رأيي ، فهي معقدة من الناحية الحسابية بشكل غير ضروري. لذلك ، أقدم انتباهك (وانتقادك) إلى طريقي.

طريقى

مهمة

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

القرار

وسيلة إيضاح لتجنب سوء الفهم: a - المتجه a ، a (y) - إسقاط المتجه a على المحور Y ، a {x1 ، y1} - المتجه a ، المحدد بالإحداثيات x1 ، y1.



دعنا نمثل المقطعين في شكل متجهين: a {x2-x1؛ y2-y1} و b {x3-x4 ؛ y3-x4}. لاحظ أن المتجه b في الاتجاه المعاكس لما هو متوقع. دعنا نقدم المتجه c {x3-x1؛ y3-y1}. لاحظ أن أ * ك + ب * ن = ج ، حيث ك ، ن هي بعض المعاملات. وبالتالي ، نحصل على نظام المعادلات:



a (x) * k + b (x) * n = c (x)

a (y) * k + b (y) * n = c (y)

يتم تقليل مهمتنا لإيجاد هذه المعاملات (باعتراف الجميع ، يكفي العثور على واحد منهم فقط).



أقترح ضرب طرفي المعادلة السفلية في q = -a (x) / a (y). إذن بعد إضافة معادلتين ، نتخلص فورًا من k. يتم تقليل إيجاد n إلى حل معادلة خطية عادية. من المهم ملاحظة أن n قد لا يكون له حل.



سيلاحظ القارئ اليقظ أنه عندما (y) = 0 ، نحصل على خطأ. لنكتب التفرع في مرحلة إيجاد (ص). هذه الحالة أبسط ، لأننا نحصل على معادلة واحدة غير معروفة على الفور.



أوصي بمحاولة طباعة n بنفسك ، لذلك سيكون من الواضح ما يأتي من الكود أدناه.



بمعرفة n ، يمكنك إيجاد نقطة التقاطع ، ولهذا نطرح المتجه b * n من إحداثيات النقطة (x3 ، y3)

تجميعها

float dot[2];  //  

bool cross(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
    float n;
    if (y2 - y1 != 0) {  // a(y)
        float q = (x2 - x1) / (y1 - y2);   
        float sn = (x3 - x4) + (y3 - y4) * q; if (!sn) { return 0; }  // c(x) + c(y)*q
        float fn = (x3 - x1) + (y3 - y1) * q;   // b(x) + b(y)*q
        n = fn / sn;
    }
    else {
        if (!(y3 - y4)) { return 0; }  // b(y)
        n = (y3 - y1) / (y3 - y4);   // c(y)/b(y)
    }
    dot[0] = x3 + (x4 - x3) * n;  // x3 + (-b(x))*n
    dot[1] = y3 + (y4 - y3) * n;  // y3 +(-b(y))*n
    return 1;
}

تأخذ هذه الوظيفة إحداثيات الرؤوس وتعيد القيمة 1 إذا تقاطعت الخطوط المستقيمة للقطاعات (أي الخطوط المستقيمة) ، وإلا 0. إذا كنت بحاجة إلى إحداثيات الرؤوس ، فيمكنك أخذها من مجموعة النقاط [].



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



دعنا نطبق الوظيفة:

int main() {
    if (cross(1,1,7,2, 7,3,5,6)) {
        std::cout << dot[0] << " " << dot[1] << std::endl;
    }
    else {
        std::cout<<"Not cross!"<<std::endl;
    }
    return 0;
}

خاتمة

على الرغم من أنني لم أجد هذه الطريقة في عملية البحث عن مشكلتي على Google وطوّرت الخوارزمية بنفسي ، إلا أنني لا أتظاهر بأنني أصلي تمامًا (وصحيح). لذا أهلا بك في التعليقات!