多邊形相交失敗，碰撞「大小」太大

好吧，所以我試圖做一個簡單的小行星克隆。一切工作正常，除了碰撞檢測。多邊形相交失敗，碰撞「大小」太大

我有兩個不同的版本，第一個使用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();

這就像一個魅力......如果你不關心40％的CPU僅120小行星:(

所以我搜索網爲著名的分離軸定理，因爲我不是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

正如你可以看到希望，在一個畫面的小行星比照片2的那些地方是用SAT代碼密集得多。

那麼有什麼想法？或者是否有人知道我可以使用的具有相交測試功能的Java的Polygon實現？

來源

2009-10-26 Ivo Wetzel

它看起來像你的第二個結果是做碰撞檢測，就好像多邊形是半徑設置爲離中心多邊形最遠點的圓形一樣。我見過的大多數碰撞檢測工具創建了一個簡單的邊界框（圓圈或矩形），多邊形可以放入其中。只有兩個邊界框相交（更簡單的計算），您纔會繼續進行更詳細的檢測。也許這個挪用的算法只能用作邊界框計算器？

編輯：此外，從維基百科

如果其中一個機構是不是凸的定理並不適用。

圖像中的許多小行星都有凹面。

來源

2009-10-26 22:56:25 Jherico

多邊形相交失敗，碰撞「大小」太大

回答

相關問題