빠른 원주 충돌 감지

Question

두 개의 원이 겹치는 경우 계산할 메소드를 작성하려고합니다. 나는 다음을 생각해 냈다. 어쨌든 그것이 더 이상 최적화 될 수 있는지 궁금하다.

private static boolean isCollision(Point2D p1, float r1, Point2D p2, float r2) 
{ 
    float a,dx, dy; 
    a = (r1+r2) * (r1+r2); 
    dx = (float) (p1.getX() - p2.getX()); 
    dy = (float) (p1.getY() - p2.getY()); 

    if (a > (dx*dx) + (dy*dy)) 
    { 
     return true; 
    } 
    return false; 
} 

Answer 1

흠. 수학이가는 한 꽤 괜찮아 보입니다. 자바 빨리 측과 terser하는 방법에 약간의 포인트 : 대신 반경위한 수레의 두 배를 사용한 경우

• , 당신은 수레에 두 배를 아래로 캐스팅 할 필요가 없습니다 것입니다.
• 특별히 Point2D.Double 매개 변수를 요청하면 getter를 사용하는 대신 x 및 y public 필드를 사용할 수 있습니다.
• 또한 이유는 if (foo) { return true; } else { return false; }?입니다. return foo;! 다음

개선 된 버전 :

이

private static boolean isCollision(Point2D.Double p1, double r1, Point2D.Double p2, double r2) 
{ 
    final double a = r1 + r2; 
    final double dx = p1.x - p2.x; 
    final double dy = p1.y - p2.y; 
    return a * a > (dx * dx + dy * dy); 
} 

(. 코드가 완전히 플로트를 기반으로하는 경우, 당신은 Point2D.Float 및 float들과 같은 일을 할 수 있습니다)

Answer 2

겹치거나 교차합니까?

intersect 인 경우 서로가 내부에 있기 때문에 원이 교차하지 않는 경우를 잊지 마세요.

겹치는 부분이 있다면 어떻게 더 최적화 할 수 있는지 실제로 알 수 없습니다. 점 거리를 제곱근을 피하기 위해 제곱 한 거리를 사용하여 반경의 합계와 비교합니다. 다듬을 지방이 남아있는 것처럼 보이지 않습니다.

Answer 3

그것은 아무튼 'T는 빠르게 코드를 만들지 만, 내가 선호하는 것 :

return a > (dx*dx + dy*dy); 

Answer 4

것은 당신이 정말로 가능한 나타내는 Point2D의 implementati 음식을 장만해야합니까 에? 당신이하지 않은 경우, 그것은 가상 통화를 저장합니다 :

private static boolean isCollisionFloat (Point2D.Float p1, float r1, Point2D.Float p2, float r2) 
{ 
    final float r = r1+r2; 
    final float dx = p1.x - p2.x; 
    final float dy = p1.y - p2.y; 

    return (r*r) > (dx*dx) + (dy*dy); 
} 

 
testing 1000x1000 points: 
Doing nothing took 6 ms 
Doing isCollision passing Point2D.Float took 128 ms 
Doing isCollision passing Point2D.Double took 127 ms 
Doing isCollisionFloat took 71 ms 
Doing isCollisionDouble took 72 ms 

당신이 아니라 모두를 위해 음식보다, 둘 중 하나를 선택 할 수 있습니다. 반환 한 질문

---

문제 당신이 정말로 시간 누군가가 지원되지 않는 의견과 같은 대답을 게시하는 효과를 측정 할 필요가 없다는 것입니다.

Answer 5

각 원의 직사각형 경계를 계산하고 겹치는 지 확인하여 알고리즘을 더욱 최적화 할 수 있습니다. 중복되지 않으면 false를 반환합니다. 이렇게하면 직사각형 경계가 겹치지 않는 서클 (즉, 서로 가깝지 않음)에 대한 곱셈을 피할 수 있습니다. 직사각형 바인딩 계산의 더하기/빼기는 곱하기보다 쌉니다.

이것은 Java 2D에서 사용하는 패턴입니다. Shape.getBounds()

Answer 6

귀하의 사례와 관련이 있는지는 잘 모르겠지만 서클과 다른 서클의 겹치는 부분을 확인하려는 경우 (수천 개의 서클을 가정 해 봅시다) 쿼드로 서클을 구성 할 수 있습니다. (http://en.wikipedia.org/wiki/Quadtree 참조) 쿼드 트리에서 트리 룩업 (원의 경계 사각형을 기반으로)을 수행합니다.