ポリゴンの交差が失敗し、衝突が「大きすぎます」が大きすぎます

Question

OK、単純な小惑星のクローンを作成しようとしています。衝突の検出を除いて、すべてうまく動作します。

これは魔法のように動作

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

...あなただけの120のために約40％のCPUを気にしない場合：

は、私は2つの異なるバージョンを持って、最初のものはjava.awt.geom.Areaの使用しています小惑星:(

だから、私は数学A thaaaaaat良いじゃないので、私はhereから実装を取り、私のJavaが必要に合わせてそれを変換し、有名な分離軸定理のためのネットを検索：

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

それは働く...ちょっと。実際には、小惑星の「衝突船体」は、このコードを使用すると大きすぎると思われます。小惑星の1.2倍の大きさです。そして私には何の手がかりもない。あなたがうまくいけば見ることができるように
http://www.spielecast.de/stuff/asteroids1.png
http://www.spielecast.de/stuff/asteroids2.png

、画像1における小惑星は、SATのコードを使用している画像2のものよりもはるかに密度が高い：

はここで比較のための2枚の写真です。

だからアイデアはありますか？あるいは、私が使用できる交差点テストを特徴とするJava用のPolygon実装を知っている人はいますか？

Answer 1

2番目の結果は、ポリゴンが中心からのポリゴンの最も遠い点に設定された半径を持つ円であるかのように衝突検出を行っているようです。私が見たほとんどの衝突検出機能は、ポリゴンが収まるような単純な境界ボックス（円または四角形）を作成します。 2つの境界ボックスが交差する場合（より簡単な計算の場合）に限り、より詳細な検出を続行します。おそらく、適切なアルゴリズムは、バウンディングボックスの計算機としてのみ意図されていますか？

EDIT：また 、体の一つが凸でない場合、ウィキペディア

から定理は適用されません。

あなたの画像の小惑星の多くは凹面を持っています。