Phát hiện va chạm vòng tròn nhanh

Question

Tôi đang cố gắng viết một phương pháp sẽ tính toán nếu hai vòng kết nối chồng lên nhau. Tôi đã đưa ra sau đây và tôi chỉ tò mò muốn biết nếu có anyway nó có thể được tối ưu hóa hơn nữa.

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

Hmm. Điều đó có vẻ khá tốt như xa như toán học đi. Một số điểm nhỏ về cách làm cho mặt Java của nó nhanh hơn và kéo dài hơn:

• Nếu bạn sử dụng tăng gấp đôi thay cho phao cho bán kính, bạn sẽ không phải xuống đôi để phao nổi.
• Nếu bạn đặc biệt yêu cầu Point2D.Double parameters, bạn có thể sử dụng các trường công cộng x và y thay vì sử dụng getters.
• Ngoài ra, tại sao if (foo) { return true; } else { return false; }? Chỉ cần làm return foo;!

Một phiên bản được cải thiện, sau đó:

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

(. Lưu ý rằng nếu mã của bạn là hoàn toàn thả nổi dựa trên, bạn có thể làm điều tương tự với Point2D.Float và float s)

Answer 2

Chồng chéo hoặc cắt nhau?

Nếu giao nhau, đừng quên trường hợp vòng tròn không giao nhau vì chúng nằm trong nhau.

Nếu chồng chéo, tôi không thực sự thấy cách bạn có thể tối ưu hóa thêm; bạn so sánh khoảng cách điểm với tổng của bán kính, sử dụng khoảng cách bình phương để tránh lấy căn bậc hai. Không có vẻ như có bất kỳ chất béo còn lại để cắt.

Answer 3

Nó doesn không làm cho mã của bạn nhanh hơn, nhưng tôi muốn:

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

Answer 4

Bạn có thực sự cần phải phục vụ cho bất kỳ Point2D implementati nào có thể trên? Nếu bạn không phải, nó sẽ tiết kiệm được một cuộc gọi ảo:

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 

Nếu bạn có thể, chọn một hay cách khác, chứ không phải phục vụ cho cả hai.

---

Vấn đề với câu hỏi đặt ra là bạn thực sự phải đo lường hiệu ứng, khi đó ai đó đã đăng câu trả lời giống như ý kiến ​​không được hỗ trợ.

Answer 5

Thuật toán của bạn có thể được tối ưu hóa thêm bằng cách tính giới hạn hình chữ nhật của mỗi vòng tròn và xem chúng có trùng lặp hay không. Nếu chúng không trùng nhau thì chỉ cần trả về false. Điều này tránh nhân cho những vòng tròn của những giới hạn hình chữ nhật không trùng lặp (nghĩa là chúng không gần nhau). Cộng/trừ cho phép tính ràng buộc hình chữ nhật là rẻ hơn phép nhân.

Đây là mẫu mà Java 2D sử dụng. Hãy xem Shape.getBounds()

Answer 6

Tôi không biết liệu nó có liên quan trong trường hợp của bạn hay không, nhưng nếu bạn muốn kiểm tra trùng lặp giữa vòng kết nối của bạn và nhiều vòng kết nối khác (giả sử hàng nghìn vòng kết nối) -trees (xem http://en.wikipedia.org/wiki/Quadtree) và thực hiện tìm kiếm cây (dựa trên hình chữ nhật bao quanh của vòng tròn của bạn) trong cây quad-tree.