كشف تصادم الدائرة والمستطيل (التقاطع)

https://stackoverflow.com/questions/401847

03-07-2019
|

سؤال

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

المحلول

هناك حالتان فقط عندما تتقاطع الدائرة مع المستطيل:

إما أن يقع مركز الدائرة داخل المستطيل، أو
تحتوي إحدى حواف المستطيل على نقطة في الدائرة.

لاحظ أن هذا لا يتطلب أن يكون المستطيل موازيًا للمحور.

(طريقة واحدة لرؤية هذا:إذا لم يكن لأي من الحواف نقطة في الدائرة (إذا كانت جميع الحواف "خارج" الدائرة تمامًا)، فإن الطريقة الوحيدة التي يمكن أن تتقاطع بها الدائرة مع المضلع هي إذا كان يقع بالكامل داخل المضلع.)

مع هذه الرؤية، سيعمل شيء مثل ما يلي، حيث يكون للدائرة مركز P ونصف القطر R, ، والمستطيل له رؤوس A, B, C, D بهذا الترتيب (الكود غير كامل):

def intersect(Circle(P, R), Rectangle(A, B, C, D)):
    S = Circle(P, R)
    return (pointInRectangle(P, Rectangle(A, B, C, D)) or
            intersectCircle(S, (A, B)) or
            intersectCircle(S, (B, C)) or
            intersectCircle(S, (C, D)) or
            intersectCircle(S, (D, A)))

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

0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD

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

الشيء الرائع هو أن نفس الفكرة لا تعمل فقط مع المستطيلات ولكن أيضًا مع تقاطع الدائرة مع أي منها مضلع بسيط - ليس من الضروري حتى أن تكون محدبة!

نصائح أخرى

هنا كيف سأفعل ذلك:

bool intersects(CircleType circle, RectType rect)
{
    circleDistance.x = abs(circle.x - rect.x);
    circleDistance.y = abs(circle.y - rect.y);

    if (circleDistance.x > (rect.width/2 + circle.r)) { return false; }
    if (circleDistance.y > (rect.height/2 + circle.r)) { return false; }

    if (circleDistance.x <= (rect.width/2)) { return true; } 
    if (circleDistance.y <= (rect.height/2)) { return true; }

    cornerDistance_sq = (circleDistance.x - rect.width/2)^2 +
                         (circleDistance.y - rect.height/2)^2;

    return (cornerDistance_sq <= (circle.r^2));
}

وإليك كيف يعمل:

illusration

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

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

// clamp(value, min, max) - limits value to the range min..max

// Find the closest point to the circle within the rectangle
float closestX = clamp(circle.X, rectangle.Left, rectangle.Right);
float closestY = clamp(circle.Y, rectangle.Top, rectangle.Bottom);

// Calculate the distance between the circle's center and this closest point
float distanceX = circle.X - closestX;
float distanceY = circle.Y - closestY;

// If the distance is less than the circle's radius, an intersection occurs
float distanceSquared = (distanceX * distanceX) + (distanceY * distanceY);
return distanceSquared < (circle.Radius * circle.Radius);

ومع أي مكتبة الرياضيات لائقة، والتي يمكن اختصارها إلى 3 أو 4 خطوط.

والخاص المجال، والمستطيل تتقاطع معهد التمويل الدولي
المسافة بين الوسط دائرة وقمة الرأس واحدة من المستطيل الخاص بك هو أصغر من نصف قطر المجال الخاص بك
OR
المسافة بين الوسط دائرة وحافة واحدة من المستطيل الخاص بك هو أصغر من نصف قطر المجال الخاص بك ([<لأ href = "http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html" يختلط = "noreferrer "> خط نقطة بعد ])
OR
مركز الدائرة هو داخل المستطيل

بعد نقطة نقطة:

P1 = [x1,y1]
P2 = [x2,y2]
Distance = sqrt(abs(x1 - x2)+abs(y1-y2))

وبعد خط النقطة:

L1 = [x1,y1],L2 = [x2,y2] (two points of your line, ie the vertex points)
P1 = [px,py] some point

Distance d =  abs( (x2-x1)(y1-py)-(x1-px)(y2-y1) ) / Distance(L1,L2)

و
مركز الدائرة داخل المستطيل:
تأخذ aproach محور إفصل: في حال وجود من الإسقاط على الخط الذي يفصل المستطيل من هذه النقطة، وأنها لا تتقاطع

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

وكنت بحاجة فقط لالداخلي المنتج (س = [X1، X2]، ص = [Y1، Y2]، س * ص = X1 * Y1 + X2 * Y2)

وسيكون الاختبار الخاصة بك تبدو وكأنها ما يلي:

//rectangle edges: TL (top left), TR (top right), BL (bottom left), BR (bottom right)
//point to test: POI

seperated = false
for egde in { {TL,TR}, {BL,BR}, {TL,BL},{TR-BR} }:  // the edges
    D = edge[0] - edge[1]
    innerProd =  D * POI
    Interval_min = min(D*edge[0],D*edge[1])
    Interval_max = max(D*edge[0],D*edge[1])
    if not (  Interval_min ≤ innerProd ≤  Interval_max ) 
           seperated = true
           break  // end for loop 
    end if
end for
if (seperated is true)    
      return "no intersection"
else 
      return "intersection"
end if

وهذا لا تتحمل مستطيل الانحياز محور وغير قابلة للتمديد بسهولة لاختبار التقاطعات بين المجموعات المحدبة.

وهذا هو أسرع حل:

public static boolean intersect(Rectangle r, Circle c)
{
    float cx = Math.abs(c.x - r.x - r.halfWidth);
    float xDist = r.halfWidth + c.radius;
    if (cx > xDist)
        return false;
    float cy = Math.abs(c.y - r.y - r.halfHeight);
    float yDist = r.halfHeight + c.radius;
    if (cy > yDist)
        return false;
    if (cx <= r.halfWidth || cy <= r.halfHeight)
        return true;
    float xCornerDist = cx - r.halfWidth;
    float yCornerDist = cy - r.halfHeight;
    float xCornerDistSq = xCornerDist * xCornerDist;
    float yCornerDistSq = yCornerDist * yCornerDist;
    float maxCornerDistSq = c.radius * c.radius;
    return xCornerDistSq + yCornerDistSq <= maxCornerDistSq;
}

ملاحظة الأمر بتنفيذه، ونصف العرض / الارتفاع حسابها مسبقا. كما ويتم تربيع "يدويا" لانقاذ بعض الدورات على مدار الساعة.

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

float physicsProcessCollisionBetweenSelfAndActorRect(SPhysics *self, SPhysics *actor)
{
    float diff = 99999;

    SVector relative_position_of_circle = getDifference2DBetweenVectors(&self->worldPosition, &actor->worldPosition);
    rotateVector2DBy(&relative_position_of_circle, -actor->axis.angleZ); // This aligns the coord system so the rect becomes an AABB

    float x_clamped_within_rectangle = relative_position_of_circle.x;
    float y_clamped_within_rectangle = relative_position_of_circle.y;
    LIMIT(x_clamped_within_rectangle, actor->physicsRect.l, actor->physicsRect.r);
    LIMIT(y_clamped_within_rectangle, actor->physicsRect.b, actor->physicsRect.t);

    // Calculate the distance between the circle's center and this closest point
    float distance_to_nearest_edge_x = relative_position_of_circle.x - x_clamped_within_rectangle;
    float distance_to_nearest_edge_y = relative_position_of_circle.y - y_clamped_within_rectangle;

    // If the distance is less than the circle's radius, an intersection occurs
    float distance_sq_x = SQUARE(distance_to_nearest_edge_x);
    float distance_sq_y = SQUARE(distance_to_nearest_edge_y);
    float radius_sq = SQUARE(self->physicsRadius);
    if(distance_sq_x + distance_sq_y < radius_sq)   
    {
        float half_rect_w = (actor->physicsRect.r - actor->physicsRect.l) * 0.5f;
        float half_rect_h = (actor->physicsRect.t - actor->physicsRect.b) * 0.5f;

        CREATE_VECTOR(push_vector);         

        // If we're at one of the corners of this object, treat this as a circular/circular collision
        if(fabs(relative_position_of_circle.x) > half_rect_w && fabs(relative_position_of_circle.y) > half_rect_h)
        {
            SVector edges;
            if(relative_position_of_circle.x > 0) edges.x = half_rect_w; else edges.x = -half_rect_w;
            if(relative_position_of_circle.y > 0) edges.y = half_rect_h; else edges.y = -half_rect_h;   

            push_vector = relative_position_of_circle;
            moveVectorByInverseVector2D(&push_vector, &edges);

            // We now have the vector from the corner of the rect to the point.
            float delta_length = getVector2DMagnitude(&push_vector);
            float diff = self->physicsRadius - delta_length; // Find out how far away we are from our ideal distance

            // Normalise the vector
            push_vector.x /= delta_length;
            push_vector.y /= delta_length;
            scaleVector2DBy(&push_vector, diff); // Now multiply it by the difference
            push_vector.z = 0;
        }
        else // Nope - just bouncing against one of the edges
        {
            if(relative_position_of_circle.x > 0) // Ball is to the right
                push_vector.x = (half_rect_w + self->physicsRadius) - relative_position_of_circle.x;
            else
                push_vector.x = -((half_rect_w + self->physicsRadius) + relative_position_of_circle.x);

            if(relative_position_of_circle.y > 0) // Ball is above
                push_vector.y = (half_rect_h + self->physicsRadius) - relative_position_of_circle.y;
            else
                push_vector.y = -((half_rect_h + self->physicsRadius) + relative_position_of_circle.y);

            if(fabs(push_vector.x) < fabs(push_vector.y))
                push_vector.y = 0;
            else
                push_vector.x = 0;
        }

        diff = 0; // Cheat, since we don't do anything with the value anyway
        rotateVector2DBy(&push_vector, actor->axis.angleZ);
        SVector *from = &self->worldPosition;       
        moveVectorBy2D(from, push_vector.x, push_vector.y);
    }   
    return diff;
}

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

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

ثانيًا، عليك إيجاد المسافة بين مركز الدائرة ومركز المستطيل، فلن تكون دائرتك داخل المستطيل إذا كانت المسافة أكبر من نصف طول قطر المستطيل.

حظ سعيد!

والحل أبسط جئت مع واضحة جدا.

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

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

public boolean intersects(float cx, float cy, float radius, float left, float top, float right, float bottom)
{
   float closestX = (cx < left ? left : (cx > right ? right : cx));
   float closestY = (cy < top ? top : (cy > bottom ? bottom : cy));
   float dx = closestX - cx;
   float dy = closestY - cy;

   return ( dx * dx + dy * dy ) <= radius * radius;
}

وهذا كل شيء! الحل أعلاه يفترض أصل في الجانب الأيسر العلوي من العالم مع محور س إلى الانخفاض.

إذا كنت ترغب في حل لمعالجة التصادمات بين دائرة التحرك والمستطيل، انها أبعد ما تكون أكثر تعقيدا وغطت <لأ href = "https://stackoverflow.com/questions/18704999/how-to-fix-circle-and -rectangle-تداخل في والاصطدام استجابة / 18790389 # 18790389 "> في إجابة أخرى من الألغام.

للتصور، خذ لوحة المفاتيح الرقمية الخاصة بك.إذا كان المفتاح "5" يمثل المستطيل الخاص بك، فإن جميع المفاتيح من 1 إلى 9 تمثل الأرباع التسعة للمساحة مقسومة على الخطوط التي تشكل المستطيل (حيث يمثل الرقم 5 الجزء الداخلي).

1) إذا كان مركز الدائرة في الربع الخامس (أي:داخل المستطيل) ثم يتقاطع الشكلان.

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

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

2) إذا كانت إحدى زوايا المستطيل A، B، C، D تقع داخل الدائرة، فإن الشكلين يتقاطعان.

الحالة الثانية أصعب.يجب أن نلاحظ أن هذا قد يحدث فقط عندما يقع مركز الدائرة في أحد الأرباع 2 أو 4 أو 6 أو 8.(في الواقع، إذا كان المركز يقع على أي من الأرباع 1، 3، 7، 8، فإن الزاوية المقابلة ستكون أقرب نقطة إليه.)

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

3) لكل خط AB، BC، CD، DA، أنشئ خطوطًا متعامدة p(AB,P)، p(BC,P)، p(CD,P)، p(DA,P) عبر مركز الدائرة P.لكل خط متعامد، إذا كان التقاطع مع الحافة الأصلية يقع داخل الدائرة، فإن الشكلين يتقاطعان.

هناك اختصار لهذه الخطوة الأخيرة.إذا كان مركز الدائرة في الربع 8 والحافة AB هي الحافة العلوية، فإن نقطة التقاطع سيكون لها إحداثي y لـ A وB، وإحداثي x للمركز P.

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

يحرر:كما اتضح، لقد تجاهلت الحقيقة البسيطة وهي أن الرقم 2 هو حالة فرعية من الرقم 3 أعلاه.بعد كل شيء، الزوايا هي أيضا نقاط على الحواف.راجع إجابة @ ShreevatsaR أدناه للحصول على شرح رائع.وفي هذه الأثناء، انسَ رقم 2 أعلاه إلا إذا كنت تريد فحصًا سريعًا ولكن زائدًا عن الحاجة.

تكتشف هذه الوظيفة الاصطدامات (التقاطعات) بين الدائرة والمستطيل.إنه يعمل مثل طريقة e.James في إجابته، ولكن هذه الطريقة تكتشف الاصطدامات لجميع زوايا المستطيل (وليس فقط الزاوية اليمنى).

ملحوظة:

aRect.origin.x و aRect.origin.y هي إحداثيات الزاوية اليسرى السفلية للمستطيل!

aCircle.x و aCircle.y هي إحداثيات مركز الدائرة!

static inline BOOL RectIntersectsCircle(CGRect aRect, Circle aCircle) {

    float testX = aCircle.x;
    float testY = aCircle.y;

    if (testX < aRect.origin.x)
        testX = aRect.origin.x;
    if (testX > (aRect.origin.x + aRect.size.width))
        testX = (aRect.origin.x + aRect.size.width);
    if (testY < aRect.origin.y)
        testY = aRect.origin.y;
    if (testY > (aRect.origin.y + aRect.size.height))
        testY = (aRect.origin.y + aRect.size.height);

    return ((aCircle.x - testX) * (aCircle.x - testX) + (aCircle.y - testY) * (aCircle.y - testY)) < aCircle.radius * aCircle.radius;
}

وأنا خلقت طبقة للعمل مع الأشكال آمل أن تستمتع

public class Geomethry {
  public static boolean intersectionCircleAndRectangle(int circleX, int circleY, int circleR, int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight){
    boolean result = false;

    float rectHalfWidth = rectangleWidth/2.0f;
    float rectHalfHeight = rectangleHeight/2.0f;

    float rectCenterX = rectangleX + rectHalfWidth;
    float rectCenterY = rectangleY + rectHalfHeight;

    float deltax = Math.abs(rectCenterX - circleX);
    float deltay = Math.abs(rectCenterY - circleY);

    float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;

    do{
        // check that distance between the centerse is more than the distance between the circumcircle of rectangle and circle
        if(lengthHypotenuseSqure > ((rectHalfWidth+circleR)*(rectHalfWidth+circleR) + (rectHalfHeight+circleR)*(rectHalfHeight+circleR))){
            //System.out.println("distance between the centerse is more than the distance between the circumcircle of rectangle and circle");
            break;
        }

        // check that distance between the centerse is less than the distance between the inscribed circle
        float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
        if(lengthHypotenuseSqure < ((rectMinHalfSide+circleR)*(rectMinHalfSide+circleR))){
            //System.out.println("distance between the centerse is less than the distance between the inscribed circle");
            result=true;
            break;
        }

        // check that the squares relate to angles
        if((deltax > (rectHalfWidth+circleR)*0.9) && (deltay > (rectHalfHeight+circleR)*0.9)){
            //System.out.println("squares relate to angles");
            result=true;
        }
    }while(false);

    return result;
}

public static boolean intersectionRectangleAndRectangle(int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight, int rectangleX2, int rectangleY2, int rectangleWidth2, int rectangleHeight2){
    boolean result = false;

    float rectHalfWidth = rectangleWidth/2.0f;
    float rectHalfHeight = rectangleHeight/2.0f;
    float rectHalfWidth2 = rectangleWidth2/2.0f;
    float rectHalfHeight2 = rectangleHeight2/2.0f;

    float deltax = Math.abs((rectangleX + rectHalfWidth) - (rectangleX2 + rectHalfWidth2));
    float deltay = Math.abs((rectangleY + rectHalfHeight) - (rectangleY2 + rectHalfHeight2));

    float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;

    do{
        // check that distance between the centerse is more than the distance between the circumcircle
        if(lengthHypotenuseSqure > ((rectHalfWidth+rectHalfWidth2)*(rectHalfWidth+rectHalfWidth2) + (rectHalfHeight+rectHalfHeight2)*(rectHalfHeight+rectHalfHeight2))){
            //System.out.println("distance between the centerse is more than the distance between the circumcircle");
            break;
        }

        // check that distance between the centerse is less than the distance between the inscribed circle
        float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
        float rectMinHalfSide2 = Math.min(rectHalfWidth2, rectHalfHeight2);
        if(lengthHypotenuseSqure < ((rectMinHalfSide+rectMinHalfSide2)*(rectMinHalfSide+rectMinHalfSide2))){
            //System.out.println("distance between the centerse is less than the distance between the inscribed circle");
            result=true;
            break;
        }

        // check that the squares relate to angles
        if((deltax > (rectHalfWidth+rectHalfWidth2)*0.9) && (deltay > (rectHalfHeight+rectHalfHeight2)*0.9)){
            //System.out.println("squares relate to angles");
            result=true;
        }
    }while(false);

    return result;
  } 
}

وهنا هو modfied قانون 100٪ للعمل:

public static bool IsIntersected(PointF circle, float radius, RectangleF rectangle)
{
    var rectangleCenter = new PointF((rectangle.X +  rectangle.Width / 2),
                                     (rectangle.Y + rectangle.Height / 2));

    var w = rectangle.Width  / 2;
    var h = rectangle.Height / 2;

    var dx = Math.Abs(circle.X - rectangleCenter.X);
    var dy = Math.Abs(circle.Y - rectangleCenter.Y);

    if (dx > (radius + w) || dy > (radius + h)) return false;

    var circleDistance = new PointF
                             {
                                 X = Math.Abs(circle.X - rectangle.X - w),
                                 Y = Math.Abs(circle.Y - rectangle.Y - h)
                             };

    if (circleDistance.X <= (w))
    {
        return true;
    }

    if (circleDistance.Y <= (h))
    {
        return true;
    }

    var cornerDistanceSq = Math.Pow(circleDistance.X - w, 2) + 
                                    Math.Pow(circleDistance.Y - h, 2);

    return (cornerDistanceSq <= (Math.Pow(radius, 2)));
}

وبسام Alugili

وهنا سريع اختبار خط واحد لذلك:

if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
  // They intersect.
}

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

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

إنها فعالة، لأنها:

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

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

وسوف تعمل مع غير الإقليدية أيضًا:

class Circle {
 // create the bounding box of the circle only once
 BBox bbox;

 public boolean intersect(BBox b) {
    // test top intersect
    if (lat > b.maxLat) {
        if (lon < b.minLon)
            return normDist(b.maxLat, b.minLon) <= normedDist;
        if (lon > b.maxLon)
            return normDist(b.maxLat, b.maxLon) <= normedDist;
        return b.maxLat - bbox.minLat > 0;
    }

    // test bottom intersect
    if (lat < b.minLat) {
        if (lon < b.minLon)
            return normDist(b.minLat, b.minLon) <= normedDist;
        if (lon > b.maxLon)
            return normDist(b.minLat, b.maxLon) <= normedDist;
        return bbox.maxLat - b.minLat > 0;
    }

    // test middle intersect
    if (lon < b.minLon)
        return bbox.maxLon - b.minLon > 0;
    if (lon > b.maxLon)
        return b.maxLon - bbox.minLon > 0;
    return true;
  }
}

minLat,maxLat يمكن استبداله بـ minY,maxY ونفس الشيء بالنسبة لـ minLon, maxLon:استبدله بـ minX، maxX
تعد NordDist طريقة أسرع قليلاً من حساب المسافة الكاملة.على سبيل المثالبدون الجذر التربيعي في الفضاء الإقليدي (أو بدون الكثير من الأشياء الأخرى للهافرسين): dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon.بالطبع إذا كنت تستخدم طريقة normDist، فستحتاج إلى إنشاء ملف normedDist = dist*dist; للدائرة

شاهد كاملا بي بوكس و دائرة رمز بلدي غراف هوبر مشروع.

وبالنسبة لأولئك ديك لحساب الدائرة / مستطيل الاصطدام في الاحداثيات الجغرافية مع SQL،
هذا هو اقترح تنفيذ بلدي في أوراكل 11 من e.James href="https://stackoverflow.com/a/402010/2186777"> .

في إدخال إحداثيات أنه يتطلب دائرة، دائرة نصف قطرها في كم واثنين من القمم ينسق المستطيل:

CREATE OR REPLACE FUNCTION "DETECT_CIRC_RECT_COLLISION"
(
    circleCenterLat     IN NUMBER,      -- circle Center Latitude
    circleCenterLon     IN NUMBER,      -- circle Center Longitude
    circleRadius        IN NUMBER,      -- circle Radius in KM
    rectSWLat           IN NUMBER,      -- rectangle South West Latitude
    rectSWLon           IN NUMBER,      -- rectangle South West Longitude
    rectNELat           IN NUMBER,      -- rectangle North Est Latitude
    rectNELon           IN NUMBER       -- rectangle North Est Longitude
)
RETURN NUMBER
AS
    -- converts km to degrees (use 69 if miles)
    kmToDegreeConst     NUMBER := 111.045;

    -- Remaining rectangle vertices 
    rectNWLat   NUMBER;
    rectNWLon   NUMBER;
    rectSELat   NUMBER;
    rectSELon   NUMBER;

    rectHeight  NUMBER;
    rectWIdth   NUMBER;

    circleDistanceLat   NUMBER;
    circleDistanceLon   NUMBER;
    cornerDistanceSQ    NUMBER;

BEGIN
    -- Initialization of remaining rectangle vertices  
    rectNWLat := rectNELat;
    rectNWLon := rectSWLon;
    rectSELat := rectSWLat;
    rectSELon := rectNELon;

    -- Rectangle sides length calculation
    rectHeight := calc_distance(rectSWLat, rectSWLon, rectNWLat, rectNWLon);
    rectWidth := calc_distance(rectSWLat, rectSWLon, rectSELat, rectSELon);

    circleDistanceLat := abs( (circleCenterLat * kmToDegreeConst) - ((rectSWLat * kmToDegreeConst) + (rectHeight/2)) );
    circleDistanceLon := abs( (circleCenterLon * kmToDegreeConst) - ((rectSWLon * kmToDegreeConst) + (rectWidth/2)) );

    IF circleDistanceLon > ((rectWidth/2) + circleRadius) THEN
        RETURN -1;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLat > ((rectHeight/2) + circleRadius) THEN
        RETURN -1;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLon <= (rectWidth/2) THEN
        RETURN 0;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLat <= (rectHeight/2) THEN
        RETURN 0;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;


    cornerDistanceSQ := POWER(circleDistanceLon - (rectWidth/2), 2) + POWER(circleDistanceLat - (rectHeight/2), 2);

    IF cornerDistanceSQ <=  POWER(circleRadius, 2) THEN
        RETURN 0;  --  -1 => NO Collision ; 0 => Collision Detected
    ELSE
        RETURN -1;  --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    RETURN -1;  --  -1 => NO Collision ; 0 => Collision Detected
END;

والأشغال، فكنت فقط من ذلك قبل أسبوع، والآن فقط حصلت على اختباره.

double theta = Math.atan2(cir.getX()-sqr.getX()*1.0,
                          cir.getY()-sqr.getY()*1.0); //radians of the angle
double dBox; //distance from box to edge of box in direction of the circle

if((theta >  Math.PI/4 && theta <  3*Math.PI / 4) ||
   (theta < -Math.PI/4 && theta > -3*Math.PI / 4)) {
    dBox = sqr.getS() / (2*Math.sin(theta));
} else {
    dBox = sqr.getS() / (2*Math.cos(theta));
}
boolean touching = (Math.abs(dBox) >=
                    Math.sqrt(Math.pow(sqr.getX()-cir.getX(), 2) +
                              Math.pow(sqr.getY()-cir.getY(), 2)));

def colision(rect, circle):
dx = rect.x - circle.x
dy = rect.y - circle.y
distance = (dy**2 + dx**2)**0.5
angle_to = (rect.angle + math.atan2(dx, dy)/3.1415*180.0) % 360
if((angle_to>135 and angle_to<225) or (angle_to>0 and angle_to<45) or (angle_to>315 and angle_to<360)):
    if distance <= circle.rad/2.+((rect.height/2.0)*(1.+0.5*abs(math.sin(angle_to*math.pi/180.)))):
        return True
else:
    if distance <= circle.rad/2.+((rect.width/2.0)*(1.+0.5*abs(math.cos(angle_to*math.pi/180.)))):
        return True
return False

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

if sqrt((rectangleRight.x - circleCenter.x)^2 +
        (rectangleBottom.y - circleCenter.y)^2) < radius
// then they intersect

if sqrt((rectangleRight.x - circleCenter.x)^2 +
        (rectangleTop.y - circleCenter.y)^2) < radius
// then they intersect

if sqrt((rectangleLeft.x - circleCenter.x)^2 +
        (rectangleTop.y - circleCenter.y)^2) < radius
// then they intersect

if sqrt((rectangleLeft.x - circleCenter.x)^2 +
        (rectangleBottom.y - circleCenter.y)^2) < radius
// then they intersect

إذا يتقاطع المستطيل إلى الدائرة، وينبغي أن يكون واحد أو أكثر من نقاط ركن من أركان المستطيل داخل في الدائرة. لنفترض أن المستطيل أربع نقاط هي A، B، C، D. ما لا يقل عن واحد منهم يجب أن تتقاطع الدائرة. حتى إذا كانت المسافة من نقطة واحدة إلى مركز الدائرة أقل من نصف قطر الدائرة يجب أن تتقاطع الدائرة. للحصول على المسافة التي يمكن استخدام نظرية فيثاغورس،

H^2 = A^2 + B^2

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

وإنه لتحديث جيدة لأرفو في خوارزمية

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow