الكشف السريع عن تصادم الدائرة

Question

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

private static boolean isCollision(Point2D p1, float r1, Point2D p2, float r2)
{
    float a,dx, dy;
    a = (r1+r2) * (r1+r2);
    dx = (float) (p1.getX() - p2.getX());
    dy = (float) (p1.getY() - p2.getY());

    if (a > (dx*dx) + (dy*dy))
    {
        return true;
    }
    return false;
}

Answer 1

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

• إذا استخدمت أعدادًا مزدوجة بدلًا من العوامات لنصف القطر، فلن تضطر إلى إسقاط المضاعفات إلى العوامات.
• إذا طلبت على وجه التحديد معلمات Point2D.Double، فيمكنك استخدام الحقول العامة x وy الخاصة بها بدلاً من استخدام الحروف.
• وأيضاً لماذا if (foo) { return true; } else { return false; }? فقط افعل return foo;!

نسخة محسنة، ثم:

private static boolean isCollision(Point2D.Double p1, double r1, Point2D.Double p2, double r2)
{
    final double a = r1 + r2;
    final double dx = p1.x - p2.x;
    final double dy = p1.y - p2.y;
    return a * a > (dx * dx + dy * dy);
}

(لاحظ أنه إذا كانت التعليمات البرمجية الخاصة بك تعتمد على التعويم بالكامل، فيمكنك فعل الشيء نفسه باستخدام Point2D.Float و floatس.)

Answer 2

والتداخل أو تتقاطع؟

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

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

Answer 3

هل كنت حقا بحاجة لتلبية أي تنفيذ Point2D ممكن؟ إذا لم يكن لديك ل، سيوفر مكالمة افتراضية:

private static boolean isCollisionFloat (Point2D.Float p1, float r1, Point2D.Float p2, float r2)
{
    final float r = r1+r2;
    final float dx = p1.x - p2.x;
    final float dy = p1.y - p2.y;

    return (r*r) > (dx*dx) + (dy*dy);
}

testing 1000x1000 points:
Doing nothing took 6 ms
Doing isCollision passing Point2D.Float took 128 ms
Doing isCollision passing Point2D.Double took 127 ms
Doing isCollisionFloat took 71 ms
Doing isCollisionDouble took 72 ms

إذا كنت تستطيع، واختيار واحد أو الآخر، بدلا من تقديم الطعام على حد سواء.

---

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

Answer 4

وأنا لا أعرف إذا كان لها صلة في قضيتك، ولكن إذا كنت تريد التحقق من التداخل بين دائرة الخاص بك والعديد من دوائر أخرى (دعنا نقول الآلاف من الدوائر)، يمكنك محاولة لتنظيم الدوائر في رباعية الأشجار ( يمكنك الاطلاع على http://en.wikipedia.org/wiki/Quadtree ) والقيام نظرة شجرة -up (هذه البيانات تعتمد على المستطيل المحيط من دائرة الخاص بك) في رباعية شجرة.

Answer 5

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

وهذا هو النمط الذي يستخدم جافا 2D. انظر Shape.getBounds ()

Answer 6

لا تجعل التعليمات البرمجية بشكل أسرع، ولكن كنت تفضل:

return a > (dx*dx + dy*dy);