[geometry] 원-사각 충돌 탐지 (교차)

내가하는 방법은 다음과 같습니다.

bool intersects(CircleType circle, RectType rect)
{
    circleDistance.x = abs(circle.x - rect.x);
    circleDistance.y = abs(circle.y - rect.y);

    if (circleDistance.x > (rect.width/2 + circle.r)) { return false; }
    if (circleDistance.y > (rect.height/2 + circle.r)) { return false; }

    if (circleDistance.x <= (rect.width/2)) { return true; }
    if (circleDistance.y <= (rect.height/2)) { return true; }

    cornerDistance_sq = (circleDistance.x - rect.width/2)^2 +
                         (circleDistance.y - rect.height/2)^2;

    return (cornerDistance_sq <= (circle.r^2));
}

작동 방식은 다음과 같습니다.

1. 첫 번째 선 쌍은 원의 중심과 사각형의 중심 사이의 x 및 y 차이의 절대 값을 계산합니다. 이렇게하면 4 사분면이 하나로 축소되어 계산을 4 번 수행 할 필요가 없습니다. 이미지는 이제 원의 중심이 놓여 야하는 영역을 보여줍니다. 단일 사분면 만 표시됩니다. 사각형은 회색 영역이고 빨간색 테두리는 사각형의 가장자리에서 정확히 1 반경 떨어진 임계 영역을 나타냅니다. 교차점이 발생하려면 원의 중심이이 빨간색 경계 안에 있어야합니다.

2. 두 번째 선 쌍은 원이 사각형에서 어느 방향으로도 멀리 떨어져있어 교차가 불가능한 쉬운 경우를 제거합니다. 이것은 이미지의 녹색 영역에 해당합니다.

3. 세 번째 선 쌍은 원이 교차가 보장되는 직사각형 (양 방향)에 충분히 가까운 쉬운 경우를 처리합니다. 이것은 이미지의 주황색과 회색 부분에 해당합니다. 이 단계는 논리가 이해되도록 2 단계 이후에 수행되어야합니다.

4. 나머지 선은 원이 사각형의 모서리와 교차 할 수있는 어려운 경우를 계산합니다. 해결하려면 원의 중심과 모서리에서 거리를 계산 한 다음 거리가 원의 반경보다 크지 않은지 확인하십시오. 이 계산은 중심이 빨간색 음영 영역 내에있는 모든 원에 대해 false를 반환하고 중심이 흰색 음영 영역 내에있는 모든 원에 대해 true를 반환합니다.

답변

// clamp(value, min, max) - limits value to the range min..max

// Find the closest point to the circle within the rectangle
float closestX = clamp(circle.X, rectangle.Left, rectangle.Right);
float closestY = clamp(circle.Y, rectangle.Top, rectangle.Bottom);

// Calculate the distance between the circle's center and this closest point
float distanceX = circle.X - closestX;
float distanceY = circle.Y - closestY;

// If the distance is less than the circle's radius, an intersection occurs
float distanceSquared = (distanceX * distanceX) + (distanceY * distanceY);
return distanceSquared < (circle.Radius * circle.Radius);

P1 = [x1, y1]
P2 = [x2, y2]
거리 = sqrt (abs (x1-x2) + abs (y1-y2))

L1 = [x1, y1], L2 = [x2, y2] (라인의 두 점, 즉 정점)
P1 = [px, py] 포인트

거리 d = abs ((x2-x1) (y1-py)-(x1-px) (y2-y1)) / 거리 (L1, L2)

// 사각 모서리 : TL (왼쪽 위), TR (오른쪽 위), BL (왼쪽 아래), BR (오른쪽 아래)
// 테스트 할 지점 : POI

분리 = 거짓
예를 들어 {{TL, TR}, {BL, BR}, {TL, BL}, {TR-BR}}에서 // 가장자리
    D = 모서리 [0]-모서리 [1]
    innerProd = D * POI
    Interval_min = min (D * edge [0], D * edge [1])
    Interval_max = max (D * edge [0], D * edge [1])
    그렇지 않은 경우 (Interval_min ≤ innerProd ≤ Interval_max)
           분리 = true
           break // 루프 종료
    경우 종료
끝나다
경우 (분리 된 경우)
      "교차 없음"을 반환
그밖에
      "교차로"를 반환
경우 종료

public static boolean intersect(Rectangle r, Circle c)
{
    float cx = Math.abs(c.x - r.x - r.halfWidth);
    float xDist = r.halfWidth + c.radius;
    if (cx > xDist)
        return false;
    float cy = Math.abs(c.y - r.y - r.halfHeight);
    float yDist = r.halfHeight + c.radius;
    if (cy > yDist)
        return false;
    if (cx <= r.halfWidth || cy <= r.halfHeight)
        return true;
    float xCornerDist = cx - r.halfWidth;
    float yCornerDist = cy - r.halfHeight;
    float xCornerDistSq = xCornerDist * xCornerDist;
    float yCornerDistSq = yCornerDist * yCornerDist;
    float maxCornerDistSq = c.radius * c.radius;
    return xCornerDistSq + yCornerDistSq <= maxCornerDistSq;
}

public boolean intersects(float cx, float cy, float radius, float left, float top, float right, float bottom)
{
   float closestX = (cx < left ? left : (cx > right ? right : cx));
   float closestY = (cy < top ? top : (cy > bottom ? bottom : cy));
   float dx = closestX - cx;
   float dy = closestY - cy;

   return ( dx * dx + dy * dy ) <= radius * radius;
}