Çokgen Kesişim başarısız, "büyüklük" çarpışması çok büyük

Question

Tamam, bu yüzden basit bir asteroid klonu yapmaya çalışıyorum. Her şey, çarpışma tespiti dışında gayet iyi çalışıyor.

Bu bir cazibe gibi çalışır

// polygon is a java.awt.Polygon and p is the other one 
final Area intersect = new Area(); 
intersect.add(new Area(polygon)); 
intersect.intersect(new Area(p.polygon)); 
return !intersect.isEmpty(); 

... sadece 120 için yaklaşık% 40 CPU umursamazsak:

Ben iki farklı sürümü var, ilki java.awt.geom.Area kullanır

public double dotProduct(double x, double y, double dx, double dy) { 
     return x * dx + y * dy; 
    } 

    public double IntervalDistance(double minA, double maxA, double minB, 
      double maxB) { 
     if (minA < minB) { 
      return minB - maxA; 
     } else { 
      return minA - maxB; 
     } 
    } 

    public double[] ProjectPolygon(double ax, double ay, int p, int[] x, int[] y) { 
     double dotProduct = dotProduct(ax, ay, x[0], y[0]); 
     double min = dotProduct; 
     double max = dotProduct; 
     for (int i = 0; i < p; i++) { 
      dotProduct = dotProduct(x[i], y[i], ax, ay); 
      if (dotProduct < min) { 
       min = dotProduct; 
      } else if (dotProduct > max) { 
       max = dotProduct; 
      } 
     } 
     return new double[] { min, max }; 
    } 

    public boolean PolygonCollision(Asteroid ast) { 
     int edgeCountA = points; 
     int edgeCountB = ast.points; 
     double edgeX; 
     double edgeY; 

     for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) { 
      if (edgeIndex < edgeCountA) { 
       edgeX = xp[edgeIndex] * 0.9; 
       edgeY = yp[edgeIndex] * 0.9; 
      } else { 
       edgeX = ast.xp[edgeIndex - edgeCountA] * 0.9; 
       edgeY = ast.yp[edgeIndex - edgeCountA] * 0.9; 
      } 

      final double x = -edgeY; 
      final double y = edgeX; 
      final double len = Math.sqrt(x * x + y * y); 
      final double axisX = x/len; 
      final double axisY = y/len; 

      final double[] minMaxA = ProjectPolygon(axisX, axisY, points, xp, 
        yp); 
      final double[] minMaxB = ProjectPolygon(axisX, axisY, ast.points, 
        ast.xp, ast.yp); 

      if (IntervalDistance(minMaxA[0], minMaxA[1], minMaxB[0], minMaxB[1]) > 0) { 
       return false; 
      } 
     } 
     return true; 
    } 

: Ben thaaaaaat iyi bir ben here gelen uygulanmasını aldı ve benim Java sığacak şekilde dönüştürülür matematik ihtiyacı değilim çünkü asteroitler :(

yüzden, ünlü ayıran eksen teoremi için net aradı

Çalışıyor ... biraz. Aslında asteroidlerin "çarpışma gövdesi" nin bu kodu kullanırken çok büyük olduğu anlaşılıyor, asteroidin 1.2 katı büyüklüğünde. Ve neden hiç bir fikrim yok. umarım görebileceğiniz gibi
http://www.spielecast.de/stuff/asteroids1.png
http://www.spielecast.de/stuff/asteroids2.png

, resimde bir de asteroitler SAT kodu kullanmak olduğunu resimde 2'de olanlardan çok daha yoğun şunlardır:

İşte karşılaştırma için iki resim.

Peki herhangi bir fikir? Ya da herkesin kullanabileceğim kesişim testlerini içeren Java için çokgen uygulamasını biliyor mu?

Answer 1

İkinci sonucun, çokgenlerin merkezden çok uzaktaki en uzak noktasına ayarlanan yarıçapları olan daireler halinde sanki çarpışma algılaması yapıyor gibi görünüyor. Gördüğüm en çok çarpışma algılaması, poligonun sığabileceği basit bir sınırlayıcı kutu (bir daire veya dikdörtgen) oluşturur. Yalnızca iki sınırlayıcı kutu kesişiyorsa (çok daha basit bir hesaplama) daha ayrıntılı saptamaya devam edersiniz. Belki de uygun algoritma sadece sınırlayıcı bir kutu hesap makinesi olarak tasarlanmıştır.

DÜZENLEME: Ayrıca , organların bir dışbükey değilse teoremi geçerli değildir wikipedia

dan.

Görüntünüzdeki asteroitlerin çoğu içbükey yüzeylere sahiptir.