Wielokątne przecięcie się nie udaje, kolizja "rozmiar" zbyt duża

Question

OK, więc próbuję zrobić prosty klon asteroid. Wszystko działa dobrze, z wyjątkiem wykrywania kolizji.

mam dwie różne wersje, pierwsza wykorzystuje java.awt.geom.Area:

// 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(); 

To działa jak czar ... jeśli nie dbają o 40% CPU na tylko 120 asteroidy :(

Więc szukałem do siatki oddzielającej słynnego twierdzenia osi, ponieważ nie jestem thaaaaaat fajnie matematyka wziąłem realizację od here i przekształcono go dopasować mój Java potrzebuje:

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

Działa ... trochę. W rzeczywistości wydaje się, że "kadłub zderzeniowy" asteroidów jest za duży, gdy używa się tego kodu, jest on 1,2 razy większy od asteroidy. I nie mam pojęcia, dlaczego.

Oto dwa zdjęcia Dla porównania:
http://www.spielecast.de/stuff/asteroids1.png
http://www.spielecast.de/stuff/asteroids2.png

Jak można zobaczyć z nadzieją, asteroidy w jednym obrazie są znacznie gęstsza niż te na rysunku 2, gdzie jest użyć kodu SAT.

Jakieś pomysły? Lub czy ktoś zna implementację Polygon dla Java z testami przecięcia, które mogłem użyć?

Answer 1

Wygląda na to, że drugim rezultatem jest wykrywanie kolizji, tak jakby wielokąty były okręgami o promieniu ustawionym w najdalszym punkcie wieloboku od środka. Większość detekcji kolizji, którą widziałem tworzy prostą ramkę ograniczającą (okrąg lub prostokąt), w którą może zmieścić się wielokąt. Tylko wtedy, gdy dwie ramki graniczne przecinają się (znacznie prostsze obliczenia), możesz przejść do bardziej szczegółowego wykrywania. Być może odpowiedni algorytm jest przeznaczony tylko jako kalkulator obwiedni?

EDIT: Również z wikipedii

Twierdzenie nie stosuje się, gdy jeden z organów nie jest wypukła.

Wiele z asteroid na twoim zdjęciu ma wklęsłe powierzchnie.