구와 구의 충돌 검사는 두 구가 서로 겹치는지를 확인하는 기본적인 물리 엔진 알고리즘 중 하나이다. 이 알고리즘은 두 구의 중심 사이의 거리가 두 구의 반지름 합보다 작거나 같은지를 확인하여 충돌 여부를 판별한다. 이를 단계별로 설명하면 다음과 같다.

1. 구의 정의

• 각 구는 중심 좌표와 반지름으로 정의된다.
• 구 A의 중심: $\mathbf{C}_A$
• 구 B의 중심: $\mathbf{C}_B$
• 구 A의 반지름: $r_A$
• 구 B의 반지름: $r_B$

2. 구간 거리 계산

• 두 구의 중심 간의 거리를 계산한다.
• $d = \left| \mathbf{C}_A - \mathbf{C}_B \right|$

3. 충돌 조건

• 두 구의 반지름 합을 구한다.
• $r_{sum} = r_A + r_B$
• 충돌 여부를 판별하는 조건은 다음과 같다.
• 충돌 발생: $d \leq r_{sum}$

4. 의사코드

다음은 충돌 여부를 확인하는 의사코드이다.

bool isCollision(Vector3 centerA, float radiusA, Vector3 centerB, float radiusB) {
    // 두 구의 중심 간의 거리 계산
    float distance = (centerA - centerB).length();

    // 두 구의 반지름 합보다 중심 간의 거리가 작거나 같으면 충돌
    return distance <= (radiusA + radiusB);
}

5. 알고리즘의 시간 복잡도

• 두 벡터의 거리 계산은 $O(1)$의 상수 시간이므로, 이 충돌 검사의 시간 복잡도는 $O(1)$이다.

이 방식은 매우 간단하면서도 효율적인 방법으로, 충돌 판정에 자주 사용된다.