다각형 교차가 실패합니다. 크기가 너무 큽니다.

Question

좋아, 간단한 소행성 복제를 만들려고합니다. 충돌 탐지를 제외한 모든 것이 잘 작동합니다.

이 마법처럼 작동

// 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를 상관하지 않는 경우 :

내가 두 개의 서로 다른 버전이, 첫 번째는 java.awt.geom.Area 사용

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

: 나는 thaaaaaat 좋은 내가 here에서 구현을 가져다가 내 자바 맞도록 변환 수학이 요구 아니에요 이후 소행성 :(

그래서 나는 유명한 분리 축 정리를위한 그물을 검색

그것은 작동합니다 ... 좀. 사실이 소행성의 "충돌 선체"는이 코드를 사용할 때 너무 크고, 소행성의 1.2 배와 같습니다. 그리고 나는 이유를 전혀 모른다. 당신이 잘하면 볼 수 있듯이
http://www.spielecast.de/stuff/asteroids1.png
http://www.spielecast.de/stuff/asteroids2.png

, 사진을 하나의 소행성이 SAT 코드를 사용하는 것입니다 그림 2에있는 것보다 훨씬 밀도가 있습니다

여기에 비교를 위해 두 사진입니다.

어떤 아이디어가 있습니까? 아니면 사용할 수있는 교차로 테스트를 특징으로하는 Java 용 Polygon 구현을 아는 사람이 있습니까?

Answer 1

두 번째 결과는 다각형이 반경이 중심에서 다각형의 가장 먼 지점으로 설정된 원형 인 것처럼 충돌 감지를 수행하는 것처럼 보입니다. 내가 본 대부분의 충돌 탐지 항목은 다각형이 들어갈 수있는 간단한 경계 상자 (원형 또는 사각형)를 만듭니다. 두 개의 경계 상자가 교차하는 경우에만 (훨씬 간단한 계산) 더 자세한 탐지로 계속 진행합니다. 아마도 적절한 알고리즘은 경계 상자 계산기로만 의도 된 것입니까?

EDIT : 또한, 사체 중 하나가 아닌 경우, 볼록 법칙을 적용하지 않을 위키

에서.

이미지의 소행성 중 많은 부분이 오목한 표면을 가지고 있습니다.