L'intersezione del poligono fallisce, la collisione "taglia" è troppo grande

Question

OK, quindi sto cercando di creare un semplice clone di asteroidi. Tutto funziona bene, ad eccezione del rilevamento delle collisioni.

Ho due versioni differenti, il primo usa 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(); 

Questo funziona come un fascino ... se non vi interessa circa il 40% della CPU per soli 120 asteroidi :(

Così ho cercato in rete per il famoso teorema dell'asse separazione, dato che non sono un buon thaaaaaat la matematica ho preso l'attuazione da here e convertito per adattarla mia Java esigenze:

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

Funziona ... un po '. In realtà sembra che lo "scafo di collisione" degli asteroidi sia troppo grande quando si usa questo codice, è pari a 1,2 volte la dimensione dell'asteroide. E non ho idea del perché.

Qui ci sono due immagini per il confronto:
http://www.spielecast.de/stuff/asteroids1.png
http://www.spielecast.de/stuff/asteroids2.png

Come si può vedere si spera, gli asteroidi in un'immagine sono molto più denso rispetto a quelli in foto 2 dove è utilizzare il codice SAT.

Quindi qualche idea? O qualcuno conosce un'implementazione Polygon per Java con test di intersezione che potrei usare?

Answer 1

Sembra che il secondo risultato stia eseguendo il rilevamento delle collisioni come se i poligoni fossero cerchi con il raggio impostato al punto più distante del poligono dal centro. La maggior parte dei materiali di rilevamento delle collisioni che ho visto crea un semplice riquadro di delimitazione (un cerchio o un rettangolo) in cui il poligono può adattarsi. Solo se due caselle di delimitazione si intersecano (un calcolo molto più semplice) si procede al rilevamento più dettagliato. Forse l'algoritmo appropriato è inteso solo come un calcolatore di bounding box?

EDIT: Inoltre, da wikipedia

Il teorema non si applica se uno dei corpi non è convessa.

Molti degli asteroidi nell'immagine hanno superfici concave.