[Algorithm] CCW 알고리즘 with JAVA

CCW Algorithm

 

들어가며

최근에 기하와 관련된 문제를 풀며 점들이 이루는 방향성을 판별하는 알고리즘을 배우게 되었습니다. CCW 알고리즘은 세 점이 이루는 방향을 간단한 연산으로 확인할 수 있는 핵심 알고리즘입니다. 이번 글에서는 CCW의 원리와 구현 방법, 그리고 더 나아가 활용방법까지 JAVA 언어와 함께 알아보겠습니다.
 

---

 

CCW : Counter Clock Wise

좌표평면에 세 개의 점이 주어진 경우 점을 순차적으로 이었을 때 세 점을 이은 선이 시계방향인지 반시계방향인지, 일직선인지 판별하는 알고리즘입니다.

순서대로 1, 2, 3번 이미지

1번 이미지부터 순서대로 반시계 방향, 시계 방향, 일직선인 경우입니다. 사람의 눈으로 세 점의 방향 관계를 파악하는 것은 아주 쉽지만 프로그래밍 언어를 통해 세 점의 좌표를 받고 판별하는 로직을 구현하는 것은 쉽지 않습니다.
 
처음 문제를 접했을 때 두 선분의 기울기를 각각 구해서 많은 조건 분기로 판별해야된다고 생각했는데 기울기만으로 세 점의 방향을 구하는 것은 한계가 극명하게 드러났습니다. 수직 선분이나, 실수 연산 등으로 구현이 복잡해져서 바로 다른 방법을 찾아봤습니다.
 
그리고 이러한 문제를 쉽게 해결할 수 있는 핵심 개념이 벡터의 외적이었습니다. 외적을 활용하면 세 점의 방향 관계를 수학적으로 간단히 판별할 수 있으며, 이를 통해 다양한 기하 알고리즘 문제에도 응용할 수 있게 됩니다.
 
 

벡터의 외적 : Cross Product

기하학에서 벡터의 외적이란 두 벡터의 곱을 뜻합니다. 두 벡터의 곱에 대한 반환값은 두 벡터가 포함된 평면과 수직을 이루는 또다른 벡터입니다.
 
외적은 수학적으로 아래와 같은 식으로 나타낼 수 있습니다.

즉, 벡터 AB와 AC의 스칼라 곱에 sin θ를 곱한 값입니다.
여기서 θ는 벡터 AB에서 벡터 AC로 회전하면서 생기는 각의 변화값인데 θ의 범위에 따라 sin θ의 부호는 아래 표처럼 나눠질 수 있습니다.

구분	0 < θ < 180	θ = 0, 180, -180	0 > θ > -180
부호	+	0	-

 
즉, 벡터 AB에서 벡터 AC로 회전하면서 생기는 각의 변화값을 통해 sin θ의 부호가 결정되고, sin θ의 부호를 통해 외적의 부호가 결정됩니다. 그럼 이 결론을 역으로 추적해서 외적의 부호를 알면 두 벡터가 어느 방향으로 회전하고 있는지도 알 수 있지 않을까요?
 
우선 벡터의 회전 방향을 통해 외적의 값을 구하는 과정을 케이스별로 자세히 살펴보겠습니다.
 

손바닥이나 손가락을 이용해서 회전 방향과 부호의 관계를 기억하는 사람들이 많던데 둘이 왜 그런 관계가 되는지를 아는 것이 우선이라고 생각합니다.

 

여러분들도 sin 값에 의해 부호가 결정된다는 것을 우선 이해하고 외우셨으면 합니다.

 

1. 반시계 방향(0 < θ < 180)

이미지1과 이미지2

이미지 1에서 A, B, C라는 세 점이 주어졌을 때 점 A, B, C는 현재 반시계 방향으로 회전하고 있는 것을 볼 수 있습니다. 벡터 AB에서 벡터 AC로 회전하면서 생긴 각 θ는 증가했기 때문에 양수입니다.
 
따라서 이미지 2에서 외적값은 양수임을 알 수 있습니다.
 

2. 시계 방향(-180 < θ < 0)

이미지1과 이미지2

이미지 1에서 A, B, C라는 세 점이 주어졌을 때 점 A, B, C는 현재 시계 방향으로 회전하고 있는 것을 볼 수 있습니다. 벡터 AB에서 벡터 AC로 회전하면서 생긴 각 θ는 감소했기 때문에 음수입니다.
 
따라서 이미지 2에서 외적값은 음수임을 알 수 있습니다.
 

3. 일직선( θ = 0, 180, -180)

이미지1과 이미지2

이미지 1에서 벡터 AB와 벡터 AC는 회전하지 않고 0도를 이루고 있습니다. 또한 이미지 2에서 벡터 AB와 벡터 AC는 180도 혹은 -180도 회전하여 일직선을 이루는 것을 볼 수 있습니다.
 
따라서 위의 두 가지 경우는 항상 외적값이 0입니다.
 
 

CCW 판별

직전에 세 점의 방향에 따라서 외적값의 부호를 도출했습니다. 그럼 반대로 외적값의 부호를 알면 세 점의 방향 관계를 판단할 수 있습니다.
 
따라서 세 점이 주어진 경우 회전 방향을 판단하는 로직은 다음과 같습니다.

1. 세 점의 좌표를 입력 받음
2. 세 점의 좌표를 통해 외적을 구한 뒤 부호를 저장
3. 부호에 따라 회전 방향 판별

이제 마지막 단계입니다. 세 점의 좌표를 통해 외적을 구해야합니다. 앞서 점 A, B, C에 대해서 벡터 AB와 벡터 AC로 벡터를 만든 뒤 외적을 구했던 것처럼 세 점이 주어지면 점 하나를 공통으로 두고 나머지 점과 연결해 벡터를 만들면 됩니다.
 

AB&AC말고 AB&BC는 안 될까?
결론부터 말하면 가능은 합니다.
하지만 AB는 A에서 시작하지만 BC는 B에서 시작하므로, 이 둘을 비교하려면 추가적인 좌표 변환이나 기준 재정립이 필요합니다. 결국 해석 과정이 복잡해지므로 실용적이지 않습니다.

 

1. 좌표로 외적 구하기

외적 공식

 
위의 식이 두 벡터의 외적을 구하는 공식입니다. 어떻게 우변을 도출했는지 궁금하실 수 있는데 단지 좌변을 대수적으로 정리하면 우변처럼 나옵니다.
 
따라서 저흰 우변의 식에 각각의 좌표를 대입하면 부호를 알아낼 수 있고, 회전 방향도 알아낼 수 있습니다.
 

2. 실제 코드로 구현하기

이제 자바 코드로 구현해보겠습니다.

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long[] A = readPoint(br);
        long[] B = readPoint(br);
        long[] C = readPoint(br);

        long orientation = ccw(A, B, C);

        // orientation > 0 : 반시계, < 0 : 시계, = 0 : 일직선
        if (orientation > 0) {
            System.out.println(1);
        } else if (orientation < 0) {
            System.out.println(-1);
        } else {
            System.out.println(0);
        }
    }

    private static long[] readPoint(BufferedReader br) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        long x = Long.parseLong(st.nextToken());
        long y = Long.parseLong(st.nextToken());
        return new long[]{x, y};
    }

    // CCW 판별을 위한 외적 계산 메소드
    // (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)
    // 반환값 > 0 : 반시계(CCW), < 0 : 시계(CW), = 0 : 일직선
    private static long ccw(long[] A, long[] B, long[] C) {
        return (B[0] - A[0]) * (C[1] - A[1]) 
             - (B[1] - A[1]) * (C[0] - A[0]);
    }
}

단순하게 ccw에서 외적을 계산하고 if~else문으로 방향을 판단하는 로직입니다.
 
 

CCW 활용 : 선분 교차 판정

이제 세 점의 회전 방향을 판단하는 방법은 충분히 이해했을거라고 생각합니다. 그러면 더 나아가서 CCW를 활용해 두 선분이 교차하는지 판단하는 것을 설명하겠습니다.
 

Case #1

선분 교차 참고 이미지 1

우선 선분이 교차하는 경우입니다. 이때 a 선분을 기준으로 점 b1과 b2가 존재하는데 a1, a2, b1이 반시계 방향으로 회전하고 있고, a1, a2, b2는 시계 방향으로 회전하는 것을 알 수 있습니다.
 
그렇다면 선분 하나를 기준으로 다른 선분의 각 점에 외적을 해줄 때 서로 부호가 반대가 된다면 반드시 교차하는 걸까요?
아래의 예시를 하나 더 보겠습니다.
 

Case #2

선분 교차 참고 이미지 2

선분 a에 대해서 점 b1과 점 b2에 각각 외적을 해준 결과 부호가 각각 반대로 나옵니다. 하지만 선분 a와 b는 교차하고 있지 않기 때문에 Case #1에서 내렸던 가정은 틀렸습니다.
 
Case #1을 다시 보겠습니다. 두 선분이 교차할 때 b를 기준으로 a1과 a2를 보면 서로 반대 방향으로 회전하고 있습니다. 하지만 Case #2를 다시 보면 선분 b에 대해 a1과 a2는 똑같이 시계 방향으로 회전하고 있습니다.
 
따라서 우린 각 선분에 다른 선분의 점에 외적을 했을 때 부호가 서로 반대가 되어야 하는 것을 결론 내릴 수 있습니다. 즉, 선분 a에 대해서 b1과 b2에 외적한 값을 서로 곱했을 때 음수가 나와야하고, 선분 b에 대해서 a1과 a2에 외적한 값을 서로 곱했을 때 음수가 나와야합니다.
 

Case #3

선분 교차 참고 이미지 L : 3, R : 4

그런데 예외가 있습니다. 두 선분이 존재한다면 점이 4개가 존재할텐데 그 중 3개의 점이 일직선이 되는 경우는 어떻게 될까요?
 

Case #3-1

우선 교차하는 경우입니다. 선분 a와 선분 b1을 외적하면 0입니다. 따라서 선분 a를 기준으로 외적한 결과를 곱하면 0이 나올 것이고, 선분 b를 기준으로 외적한 결과를 곱하면 음수가 나올 것입니다.
 

Case #3-2

다음으로 교차하지 않는 경우입니다. 똑같이 생각해보면 선분 a를 기준으로 외적한 결과를 곱하면 0이 나올 것이고, 선분 b를 기준으로 외적한 결과를 곱하면 양수가 나올 것입니다.
 
따라서 외적의 값이 0이거나 음수인 경우 항상 교차한다는 결론을 낼 수 있습니다.
 
하지만 마지막으로 한 번 더 생각해보겠습니다. 만약 외적의 값이 모두 0인 경우. 즉, 4개의 점이 일직선 상에 있는 경우는 어떨까요?
 

Case #4

선분 교차 참고 이미지 L : 5, R : 6

점 4개가 일직선상에 있는 경우 이미지 5처럼 겹칠수도 있고, 이미지 6처럼 겹치지 않는 경우도 존재합니다.
 
각각의 선분에서 외적을 한 결과가 똑같이 0으로 나오기 때문에 외적 값이 모두 0인 경우는 직접 겹치는지 범위 확인을 해야합니다.
 

선분 교차 판정 결론

if (ccw1 == 0 && ccw2 == 0) {
    if (isOverlap(x1, x2, x3, x4) && isOverlap(y1, y2, y3, y4)) {
        System.out.println(1);
    } else {
        System.out.println(0);
    }
} else if (ccw1 <= 0 && ccw2 <= 0) {
    System.out.println(1);
} else {
    System.out.println(0);
}

public static boolean isOverlap(long a1, long a2, long b1, long b2) {
    return Math.max(Math.min(a1, a2), Math.min(b1, b2)) <= Math.min(Math.max(a1, a2), Math.max(b1, b2));
}

우선 ccw1과 ccw2는 각각의 선분에 대해 외적을 해주고 외적한 값의 부호(1, 0, -1)가 저장되어있습니다. 두 선분의 ccw 값이 모두 0인 경우 Case #4에서 말했듯이 겹치는지 직접 확인해야합니다. 따라서 isOverlap으로 확인해주고 만약 겹친다면 1을 출력하고 겹치지 않는다면 0을 출력합니다.
 
isOverlap 함수가 복잡해보이지만 그림으로 보면 간단합니다.

isOverlap 함수 참고 이미지

선분 1의 x1과 x2 중에 더 오른쪽에 있는 값(x2)이 선분 2의 x3과 x4 중에 더 왼쪽에 있는 값(x3)보다 크다면 겹친다고 볼 수 있습니다. (y 좌표도 마찬가지)
 
다음으로 두 ccw가 전부 0 이하라면 반드시 겹친다고 볼 수 있고, 지금까지 경우를 제외하면 항상 겹치지 않습니다.

 

 

.
.
.

 

마치며

solved.ac

기하 공부 열심히 하겠습니다.. 본격적으로 공부한 건 이번이 처음인데 생소해서 그런지 어렵게 느껴지네요. 개인적으로 기하 알고리즘은 개인적으로 느껴지는 난이도와 티어 간의 갭이 큰 것 같습니다..
 
+ 백준의 CCW와 선분 교차 문제를 직접 풀어보면 이해가 더 쉬울 것 같습니다!
CCW : https://www.acmicpc.net/problem/11758
선분 교차1 : https://www.acmicpc.net/problem/17386
선분 교차2 : https://www.acmicpc.net/problem/17387
 
질문과 피드백은 환영합니다!!