خوارزمية للكشف عن تقاطع مستطيلين؟

Question

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

اختبار ما إذا كان أحد أركانه موجودًا في الآخر تقريبًا.يفشل إذا شكلت المستطيلات شكلًا متقاطعًا.

يبدو أنها فكرة جيدة تجنب استخدام منحدرات الخطوط، الأمر الذي قد يتطلب حالات خاصة للخطوط الرأسية.

Answer 1

ستكون الطريقة القياسية هي القيام بذلك اختبار محور الفصل (قم بالبحث في جوجل عن ذلك).

باختصار:

• لا يتقاطع كائنان إذا تمكنت من العثور على خط يفصل بين الكائنين.على سبيل المثالالكائنات / جميع نقاط الكائن موجودة على جوانب مختلفة من الخط.

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

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

  edge = v(n) - v(n-1)

يمكنك الحصول على شكل عمودي على هذا عن طريق تدويره بمقدار 90 درجة.في الوضع ثنائي الأبعاد يكون الأمر سهلاً كما يلي:

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

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

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

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it's on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

الآن اختبر جميع نقاط المستطيل A على حواف المستطيل B والعكس.إذا وجدت حافة فاصلة فإن الكائنات لا تتقاطع (بشرط أن تكون جميع النقاط الأخرى في B على الجانب الآخر من الحافة التي يتم اختبارها - انظر الرسم أدناه).إذا لم تجد أي حافة فاصلة، فإما أن تكون المستطيلات متقاطعة أو أن أحد المستطيلين موجود في المستطيل الآخر.

يعمل الاختبار مع أي مضلعات محدبة بالمناسبة.

تعديل: لتحديد حافة فاصلة، لا يكفي اختبار جميع نقاط أحد المستطيلات مقابل كل حافة من حواف المستطيل الآخر.سيتم تحديد الحافة المرشحة E (أدناه) على أنها حافة فاصلة، حيث أن جميع النقاط في A تقع في نفس المستوى النصفي لـ E.ومع ذلك، فهي ليست حافة فاصلة لأن القمم Vb1 وVb2 من B موجودة أيضًا في ذلك النصف المستوي.ولم يكن من الممكن أن تكون إلا حافة فاصلة إذا لم يكن الأمر كذلكhttp://www.iassess.com/collision.png

Answer 2

انظر بشكل أساسي إلى الصورة التالية:

إذا اصطدم الصندوقان، فسوف يتداخل الخطان A وB.

لاحظ أن هذا يجب أن يتم على كل من المحورين X وY، وكلاهما يحتاج إلى التداخل حتى يتصادم المستطيلان.

هناك مقالة جيدة في gamasutra.com الذي يجيب على السؤال (الصورة من المقال).لقد قمت بعمل خوارزمية مماثلة منذ 5 سنوات ولا بد لي من العثور على مقتطف الكود الخاص بي لنشره هنا لاحقًا

تعديل:تنص نظرية المحور الفاصل على وجود شكلين محدبين لا يتداخل في حالة وجود محور فاصل (أيواحد حيث التوقعات كما هو مبين لا تداخل).إذن "يوجد محور فاصل" => "لا يوجد تداخل".هذا ليس ضمنيًا لذا لا يمكنك إنهاء الحديث.

Answer 3

إجابة m_pGladiator صحيحة وأنا أفضل ذلك.اختبار محور الفصل هي الطريقة الأبسط والمعيارية للكشف عن تداخل المستطيل.الخط الذي لا تتداخل فيه فترات الإسقاط نسميه أ محور الفصل.الحل الذي قدمه نيلس بيبينبرينك عام للغاية.انها تستخدم المنتج نقطة للتحقق مما إذا كان أحد الأشكال يقع تمامًا على جانب واحد من حافة الآخر.يمكن أن يؤدي هذا الحل في الواقع إلى مضلعات محدبة ذات حافة n.ومع ذلك، لم يتم تحسينه لمستطيلين.

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

بالنسبة للوضع البسيط ، إذا لم يتم تدوير اثنين من المستطيلتين ، فإننا نقدم مستطيلًا بهيكل:

struct Rect {
    x, // the center in x axis
    y, // the center in y axis
    width,
    height
}

نسمي المستطيل A، B بالمستطيل A، والمستطيل B.

    if Math.abs(rectA.x - rectB.x) < (Math.abs(rectA.width + rectB.width) / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(rectA.height + rectB.height) / 2))
    then
        // A and B collide
    end if

إذا تم تدوير أي من المستطيلتين ، فقد يحتاج إلى بعض الجهود لتحديد إسقاطهما على محاور X و Y.تعريف البنية RotatedRect على النحو التالي:

struct RotatedRect : Rect {
    double angle; // the rotating angle oriented to its center
}

الفرق هو كيف أصبح العرض الآن مختلفًا قليلاً:widthA' لـ rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle)widthB' لـrectB: Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)

    if Math.abs(rectA.x - rectB.x) < (Math.abs(widthA' + widthB') / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(heightA' + heightB') / 2))
    then
        // A and B collide
    end if

يمكن الرجوع إلى GDC (مؤتمر تطوير الألعاب 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

Answer 4

في Cocoa، يمكنك بسهولة اكتشاف ما إذا كان مستطيل المنطقة المحددة يتقاطع مع مستطيل إطار NSView الذي تم تدويره.لا تحتاج حتى إلى حساب المضلعات، أو ما شابه ذلك.ما عليك سوى إضافة هذه الأساليب إلى فئة NSView الفرعية الخاصة بك.على سبيل المثال، يقوم المستخدم بتحديد منطقة في عرض NSView، ثم تقوم باستدعاء الطريقة DoesThisRectSelectMe لتمرير المنطقة المحددة.تحويل API:سوف تفعل هذه المهمة.تعمل نفس الحيلة عند النقر فوق NSView لتحديده.في هذه الحالة، قم ببساطة بتجاوز طريقة hitTest كما هو موضح أدناه.نقطة تحويل واجهة برمجة التطبيقات:سوف أقوم بهذه المهمة ;-)

- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
    NSRect localArea = [self convertRect:selectedArea fromView:self.superview];

    return NSIntersectsRect(localArea, self.bounds);
}


- (NSView *)hitTest:(NSPoint)aPoint
{
    NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
    return NSPointInRect(localPoint, self.bounds) ? self : nil;
}

Answer 5

تحقق لمعرفة ما إذا كان أي من الخطوط من أحد المستطيلات يتقاطع مع أي من الخطوط من الآخر.من السهل ترميز تقاطع مقطع الخط الساذج.

إذا كنت بحاجة إلى المزيد من السرعة، فهناك خوارزميات متقدمة لتقاطع مقطع الخط (خط الاجتياح).يرى http://en.wikipedia.org/wiki/Line_segment_intersection

Answer 6

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

قم بالبحث عن No Fit Polygon على الويب ومعرفة ما إذا كان يمكنك العثور على خوارزمية للمضلعات المحدبة (سيصبح الأمر أكثر تعقيدًا إذا كان لديك مضلعات مقعرة).إذا لم تتمكن من العثور على أي شيء، أرسل لي بريدًا إلكترونيًا على howard dot J dot may gmail dot com

Answer 7

هذا ما أعتقد أنه سيهتم بجميع الحالات المحتملة.قم بإجراء الاختبارات التالية.

1. تحقق من وجود أي من رؤوس المستطيل 1 داخل المستطيل 2 والعكس صحيح.في أي وقت تجد فيه قمة موجودة داخل المستطيل الآخر، يمكنك استنتاج أنها تتقاطع وتوقف البحث.سيعتني هذا بمستطيل واحد موجود بالكامل داخل الآخر.
2. إذا كان الاختبار أعلاه غير حاسم، فأوجد نقاط التقاطع لكل خط من مستطيل واحد مع كل خط من المستطيل الآخر.بمجرد العثور على نقطة التقاطع، تحقق مما إذا كانت تقع بين داخل المستطيل الوهمي الذي تم إنشاؤه بواسطة النقاط الأربع المقابلة.عندما يتم العثور على مثل هذه النقطة، استنتج أنها تتقاطع وتوقف البحث.

إذا أظهر الاختباران أعلاه خطأ، فهذا يعني أن هذين المستطيلين لا يتداخلان.

Answer 8

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

Answer 9

حسنًا، طريقة القوة الغاشمة هي السير على حواف المستطيل الأفقي والتحقق من كل نقطة على طول الحافة لمعرفة ما إذا كانت تقع على المستطيل الآخر أو داخله.

الإجابة الرياضية هي تكوين معادلات تصف كل حافة من المستطيلين.الآن يمكنك ببساطة معرفة ما إذا كان أي من الخطوط الأربعة من المستطيل A يتقاطع مع أي من خطوط المستطيل B، والذي يجب أن يكون حلاً للمعادلات الخطية البسيطة (السريعة).

-آدم

Answer 10

يمكنك العثور على تقاطع كل جانب من المستطيل الزاوي مع كل جانب من الجوانب المحاذية للمحور.قم بذلك عن طريق إيجاد معادلة الخط اللانهائي الذي يقع عليه كل جانب (أي:v1 + t(v2-v1) و v'1 + t'(v'2-v'1) بشكل أساسي)، وإيجاد النقطة التي يلتقي عندها الخطان عن طريق حل t عندما تكون هاتان المعادلتان متساويتان (إذا كانتا بالتوازي، يمكنك اختبار ذلك) ثم اختبار ما إذا كانت تلك النقطة تقع على القطعة المستقيمة بين الرأسين، أي.هل صحيح أن 0 <= t <= 1 و 0 <= t' <= 1.

ومع ذلك، فإن هذا لا يغطي الحالة عندما يغطي أحد المستطيلين الآخر بالكامل.يمكنك تغطيته عن طريق اختبار ما إذا كانت النقاط الأربع لأي من المستطيلين تقع داخل المستطيل الآخر.

Answer 11

هذا ما سأفعله، من أجل 3D نسخة هذه المشكلة:

قم بتمثيل المستطيلين كمستويات موصوفة بالمعادلتين P1 وP2، ثم اكتب P1=P2 واشتق منها خط معادلة التقاطع، والذي لن يكون موجودًا إذا كان المستويان متوازيين (بدون تقاطع)، أو كانا في نفس المستوى، وفي هذه الحالة تحصل على 0=0.في هذه الحالة، ستحتاج إلى استخدام خوارزمية تقاطع المستطيل ثنائي الأبعاد.

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

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

هذه هي الأوصاف الرياضية، ولسوء الحظ ليس لدي رمز للقيام بما ورد أعلاه.

Answer 12

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

هذه الخوارزمية أطول إلى حد ما من اختبار المحور الفاصل، ولكنها أسرع لأنها تتطلب فقط اختبار نصف المستوى إذا كانت الحواف تتقاطع مع ربعين (على عكس ما يصل إلى 32 اختبارًا باستخدام طريقة المحور الفاصل)

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

Answer 13

إما أنني أفتقد شيئًا آخر، لماذا تجعل هذا الأمر معقدًا للغاية؟

إذا كانت (x1,y1) و (X1,Y1) زوايا المستطيلات، فللبحث عن التقاطع قم بما يلي:

    xIntersect = false;
    yIntersect = false;
    if (!(Math.min(x1, x2, x3, x4) > Math.max(X1, X2, X3, X4) || Math.max(x1, x2, x3, x4) < Math.min(X1, X2, X3, X4))) xIntersect = true;
    if (!(Math.min(y1, y2, y3, y4) > Math.max(Y1, Y2, Y3, Y4) || Math.max(y1, y2, y3, y4) < Math.min(Y1, Y2, Y3, Y4))) yIntersect = true;
    if (xIntersect && yIntersect) {alert("Intersect");}

Answer 14

لقد نفذته مثل هذا:

bool rectCollision(const CGRect &boundsA, const Matrix3x3 &mB, const CGRect &boundsB)
{
    float Axmin = boundsA.origin.x;
    float Axmax = Axmin + boundsA.size.width;
    float Aymin = boundsA.origin.y;
    float Aymax = Aymin + boundsA.size.height;

    float Bxmin = boundsB.origin.x;
    float Bxmax = Bxmin + boundsB.size.width;
    float Bymin = boundsB.origin.y;
    float Bymax = Bymin + boundsB.size.height;

    // find location of B corners in A space
    float B0x = mB(0,0) * Bxmin + mB(0,1) * Bymin + mB(0,2);
    float B0y = mB(1,0) * Bxmin + mB(1,1) * Bymin + mB(1,2);

    float B1x = mB(0,0) * Bxmax + mB(0,1) * Bymin + mB(0,2);
    float B1y = mB(1,0) * Bxmax + mB(1,1) * Bymin + mB(1,2);

    float B2x = mB(0,0) * Bxmin + mB(0,1) * Bymax + mB(0,2);
    float B2y = mB(1,0) * Bxmin + mB(1,1) * Bymax + mB(1,2);

    float B3x = mB(0,0) * Bxmax + mB(0,1) * Bymax + mB(0,2);
    float B3y = mB(1,0) * Bxmax + mB(1,1) * Bymax + mB(1,2);

    if(B0x<Axmin && B1x<Axmin && B2x<Axmin && B3x<Axmin)
        return false;
    if(B0x>Axmax && B1x>Axmax && B2x>Axmax && B3x>Axmax)
        return false;
    if(B0y<Aymin && B1y<Aymin && B2y<Aymin && B3y<Aymin)
        return false;
    if(B0y>Aymax && B1y>Aymax && B2y>Aymax && B3y>Aymax)
        return false;

    float det = mB(0,0)*mB(1,1) - mB(0,1)*mB(1,0);
    float dx = mB(1,2)*mB(0,1) - mB(0,2)*mB(1,1);
    float dy = mB(0,2)*mB(1,0) - mB(1,2)*mB(0,0);

    // find location of A corners in B space
    float A0x = (mB(1,1) * Axmin - mB(0,1) * Aymin + dx)/det;
    float A0y = (-mB(1,0) * Axmin + mB(0,0) * Aymin + dy)/det;

    float A1x = (mB(1,1) * Axmax - mB(0,1) * Aymin + dx)/det;
    float A1y = (-mB(1,0) * Axmax + mB(0,0) * Aymin + dy)/det;

    float A2x = (mB(1,1) * Axmin - mB(0,1) * Aymax + dx)/det;
    float A2y = (-mB(1,0) * Axmin + mB(0,0) * Aymax + dy)/det;

    float A3x = (mB(1,1) * Axmax - mB(0,1) * Aymax + dx)/det;
    float A3y = (-mB(1,0) * Axmax + mB(0,0) * Aymax + dy)/det;

    if(A0x<Bxmin && A1x<Bxmin && A2x<Bxmin && A3x<Bxmin)
        return false;
    if(A0x>Bxmax && A1x>Bxmax && A2x>Bxmax && A3x>Bxmax)
        return false;
    if(A0y<Bymin && A1y<Bymin && A2y<Bymin && A3y<Bymin)
        return false;
    if(A0y>Bymax && A1y>Bymax && A2y>Bymax && A3y>Bymax)
        return false;

    return true;
}

المصفوفة mB هي أي مصفوفة تحويل متقاربة تقوم بتحويل النقاط في الفضاء B إلى نقاط في الفضاء A.يتضمن ذلك التدوير والترجمة البسيطة، والتدوير بالإضافة إلى القياس، والالتواءات المتقاربة الكاملة، ولكن ليس التواءات المنظور.

قد لا يكون الأمثل قدر الإمكان.لم تكن السرعة مصدر قلق كبير.ومع ذلك يبدو أنه يعمل بشكل جيد بالنسبة لي.

Answer 15

فيما يلي تطبيق matlab للإجابة المقبولة:

function olap_flag = ol(A,B,sub)

%A and B should be 4 x 2 matrices containing the xy coordinates of the corners in clockwise order

if nargin == 2
  olap_flag = ol(A,B,1) && ol(B,A,1);
  return;
end

urdl = diff(A([1:4 1],:));
s = sum(urdl .* A, 2);
sdiff = B * urdl' - repmat(s,[1 4]);

olap_flag = ~any(max(sdiff)<0);

Answer 16

هذه هي الطريقة التقليدية، انتقل سطرًا تلو الآخر وتحقق مما إذا كانت الخطوط متقاطعة.هذا هو الكود الموجود في MATLAB.

C1 = [0, 0];    % Centre of rectangle 1 (x,y)
C2 = [1, 1];    % Centre of rectangle 2 (x,y)
W1 = 5; W2 = 3; % Widths of rectangles 1 and 2
H1 = 2; H2 = 3; % Heights of rectangles 1 and 2
% Define the corner points of the rectangles using the above
R1 = [C1(1) + [W1; W1; -W1; -W1]/2, C1(2) + [H1; -H1; -H1; H1]/2];
R2 = [C2(1) + [W2; W2; -W2; -W2]/2, C2(2) + [H2; -H2; -H2; H2]/2];

R1 = [R1 ; R1(1,:)] ;
R2 = [R2 ; R2(1,:)] ;

plot(R1(:,1),R1(:,2),'r')
hold on
plot(R2(:,1),R2(:,2),'b')


%% lines of Rectangles 
L1 = [R1(1:end-1,:) R1(2:end,:)] ;
L2 = [R2(1:end-1,:) R2(2:end,:)] ;
%% GEt intersection points
P = zeros(2,[]) ;
count = 0 ;
for i = 1:4
    line1 = reshape(L1(i,:),2,2) ;
    for j = 1:4
        line2 = reshape(L2(j,:),2,2) ;
        point = InterX(line1,line2) ;
        if ~isempty(point)
            count = count+1 ;
            P(:,count) = point ;
        end
    end
end
%%
if ~isempty(P)
    fprintf('Given rectangles intersect at %d points:\n',size(P,2))
    plot(P(1,:),P(2,:),'*k')
end

يمكن تنزيل وظيفة InterX من: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

Answer 17

لدي طريقة أبسط خاصة بي، إذا كان لدينا مستطيلين:

R1 = (min_x1، max_x1، min_y1، max_y1)

R2 = (min_x2، max_x2، min_y2، max_y2)

أنها تتداخل إذا وفقط إذا:

التداخل = (max_x1 > min_x2) و (max_x2 > min_x1) و (max_y1 > min_y2) و (max_y2 > min_y1)

يمكنك القيام بذلك للمربعات ثلاثية الأبعاد أيضًا، في الواقع إنه يعمل مع أي عدد من الأبعاد.

Answer 18

لقد قيل ما يكفي في الإجابات الأخرى، لذلك سأضيف فقط سطرًا واحدًا من الكود الكاذب:

!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);