Thuật toán để phát hiện chính xác sự chồng chéo giữa hình vuông và hình tròn?

Question

Tôi đang thực hiện (trong C++) một phương pháp để phát hiện khi chồng chéo xảy ra giữa hai hình dạng liên kết trục, tĩnh trên mặt phẳng 2d. Các hình dạng là một trong hai hình vuông hoặc hình tròn, và do đó có ba trường hợp tôi cần phải xem xét để chồng lên nhau: hình vuông, hình vuông, hình tròn và hình tròn.

Hình vuông và hình tròn có hình tròn đơn giản, nhưng tôi đang cố gắng tìm bất kỳ thông tin rắn trực tuyến nào về thuật toán chính xác để tính toán chồng chéo hình vuông.

Tôi biết rằng tôi có thể nhúng hình vuông bên trong một vòng tròn (hoặc ngược lại) như một phương pháp thô, nhưng tôi quan tâm đến những gì sẽ được coi là cách sạch nhất để làm điều này chính xác hơn?

Nghiên cứu trực tuyến cho thấy có câu trả lời 'chính xác' cho câu hỏi này, nhưng không rõ câu trả lời chính xác là gì.

Answer 1

Dưới đây là một thuật toán đơn giản và nhanh chóng:

bool doesSquareCircleOverlap(float squareCenterX, float squareCenterY, float squareHalfSize, float circleCenterX, float circleCenterY, float circleRadius) { 
    float x = fabs(circleCenterX - squareCenterX) - squareHalfSize; 
    float y = fabs(circleCenterY - squareCenterY) - squareHalfSize; 

    if (x>0) { 
     if (y>0) { 
      return x*x + y*y<circleRadius*circleRadius; 
     } else { 
      return x<circleRadius; 
     } 
    } else { 
     return y<circleRadius; 
    } 
} 

Lưu ý rằng hình vuông được đại diện bởi các trung tâm và nửa kích thước.

Về cơ bản, những gì nó làm là:

• nó loại bỏ trường hợp đối xứng với fabs()
• đặt góc vào nguồn gốc
• kiểm tra mà khu vực trung tâm của vòng tròn là, để xác định điểm gần nhất trên hình vuông từ hình tròn. Nếu điểm đóng này gần hơn circleRadius thì có một chồng chéo.