Hızlı daire çarpışma algılaması

Question

İki dairenin çakışıp çakışmadığını hesaplayacak bir yöntem yazmaya çalışıyorum. Aşağıdakileri buldum ve sadece daha fazla optimize edilip edilemeyeceğini merak ediyorum.

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

Hmm. Bu matematik devam ettikçe oldukça iyi görünüyor. Java hızlı onun tarafını ve terser yapmak için nasıl Bazı küçük noktalar: Bunun yerine yarıçapı için yüzen çiftler kullandıysanız

• , sen yüzen çiftler aşağı döküm olmazdı.
• Özellikle Point2D.Double parametrelerini soruyorsanız, alıcıları kullanmak yerine x ve y ortak alanlarını kullanabilirsiniz.
• Ayrıca, neden if (foo) { return true; } else { return false; }? Sadece return foo; yapın! Sonra

Geliştirilmiş versiyonu:

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); 
} 

(. kodunuzu tamamen yüzer esaslı yapıldığı takdirde Point2D.Float ve float s ile aynı şeyi unutmayın)

Answer 2

Örtüşme veya kesişme?

Kesişiyorsa, birbirlerinin içinde oldukları için dairelerin kesişmediği durumu unutmayın.

Eğer üst üste biniyorsa, daha fazla nasıl optimize edebileceğinizi görmüyorum; Bir karekök almaktan kaçınmak için nokta mesafelerini radyüs toplamıyla karşılaştırıyorsunuz. Düzeltmek için herhangi bir yağ kalmış gibi görünmüyor.

Answer 3

Bu etmiyor 't hızlı kodunuzu yapmak ama tercih ediyorum:

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

Answer 4

gerçekten olası Point2D implementati karşılamak gerekir mi üzerinde? Eğer hiç yoksa, bu sanal bir arama kazandıracak:

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 

sen yerine her ikisi için ikram yerine, birini seçmek durumunda. perf sorularla

---

sorun gerçekten zaman birisi desteklenmeyen görüş olarak aynı cevabı gönderdi hangi etkileri ölçmek zorunda olmasıdır.

Answer 5

Algoritmanız, her dairenin dikdörtgen sınırlarının hesaplanması ve çakışıp çakılmadıklarının belirlenmesiyle daha da iyileştirilebilir. Üstüste binmezlerse, sadece yanlış döndürün. Bu, dikdörtgen sınırların üst üste gelmediği (yani birbirine yakın olmayan) daireler için çarpmayı önler. Dikdörtgen bağlı hesaplama için toplama/çıkarma, çarpmadan daha ucuzdur.

Bu, Java 2D'nin kullandığı modeldir. Bkz. Shape.getBounds()

Answer 6

Durumunuzla ilgili olup olmadığını bilmiyorum, ancak çemberinizle diğer birçok daire arasındaki çakışmaları kontrol etmek isterseniz (binlerce daire olsun), çevrelerinizi dörtlü olarak düzenlemeyi deneyebilirsiniz. -trees (bkz. http://en.wikipedia.org/wiki/Quadtree) ve dörtgen ağacında bir ağaç görünümü (dairenizin sınırlayıcı dikdörtgene dayalı) yapın.