[백준] 30_1. CCW(Counter Clock Wise) 알고리즘 설명 | 수알못

선분 교차 2

17387번: 선분 교차 2

설명

해당 문제는 CCW(Counter Clock Wise)라는 다소 생소한 알고리즘을 활용하여 풀 수 있는 문제입니다.

수학 벡터와 관련된 알고리즘이다 보니 포기가 마려웠지만 그래도 한 번 이해해보고자 하였습니다.

 

이번 글에서는 CCW 알고리즘에 대해 제가 이해한 과정을 최대한 풀어서 설명해 보겠습니다.

 

CCW는 어떤 알고리즘인가?

평면 위에 3개의 점이 주어졌을 때 세 점의 방향을 알 수 있는 알고리즘입니다.

나올 수 있는 방향은 총 3가지입니다.

• 반 시계 방향
• 직선
• 시계 방향

ccw의 알고리즘에서는 반 시계 방향일 경우 양수, 직선일 경우 0, 시계 방향일 경우 음수를 반환하도록 합니다.

(알고리즘 이름이 Counter Clock Wise(시계 반대 방향)인 이유가 반 시계 방향일 경우 양수를 반환해서이지 않을까 추측해 봅니다.)

 

뭔 소리인가 싶겠지만 그림을 보시면 쉽게 이해가 되실 겁니다.

3가지 방향

 

그럼 이제 CCW는 어떻게 구현해야 되는가?

구현 방법은 벡터의 외적을 구하면 됩니다. 그게 뭔데

 

벡터의 외적이란?

벡터의 외적은 쉽게 말해 두 개의 벡터에 대해 모두 수직을 만족하는 벡터를 말합니다.

(벡터는 방향을 가진 선분으로 이해하시면 마음이 편합니다.)

3차원 공간의 벡터의 외적 예시

위 그림에서 a벡터와 b벡터가 있을 때 두 벡터 모두 수직을 만족하는 벡터는 a X b 벡터와 b X a 벡터 총 두 가지가 나올 수 있습니다. (벡터 a, b의 외적은 a X b로 표기합니다.)

벡터의 순서에 따라 외적의 결과는 다르게 나옵니다. a X b != b X a 

 

또한 두 외적은 서로 반대에 위치하기 때문에 부호도 항상 반대로 나오게 됩니다. (음수 and 양수)

위 그림에서는 a X b의 결과가 양수가 나오고 b X a의 결과는 음수가 나옵니다.

그 이유는 오른손 법칙에 의해서 알 수 있습니다.

오른손 법칙 예시

쉽게 생각하여 위 그림의 오른손처럼 검지가 먼저 그다음 중지 순서(반 시계 방향)로 외적을 구할 경우 외적의 방향은 위를 향하며 이는 양수값이 나옴을 의미합니다. (항상 양수임을 보장하는지, 왜 양수가 나오는지는 잘 모르겠습니다)

 

결과적으로 두 벡터의 외적을 구하면 해당 값의 부호를 통해 방향을 알 수 있게 됩니다.

따라서 우리는 CCW 알고리즘을 구현하기 위해 벡터의 외적을 구해주는 것입니다.

 

지금까지의 내용을 정리하면 다음과 같습니다.

• ccw 알고리즘은 결국 벡터의 외적을 구하면 되는 알고리즘이다.
• 벡터의 외적은 두 벡터 모두 수직을 만족하는 벡터이다.
• 벡터의 외적은 두 벡터의 순서에 따라 2개의 결과가 나오며 두 결과의 부등호는 반대이다.
• 오른손 법칙 순서의 벡터의 외적은 방향이 위로 향하며 양수값이 나온다.
• 오른손 법칙은 반 시계 방향이다.

 

벡터의 외적 공식

이제 벡터의 외적을 구하는 식을 알아보겠습니다.

벡터의 외적에 대한 공식은 다양하지만 그중에서 제가 쉽게 이해한 행렬 표기법으로 알아보겠습니다. 

(이해하시면 딱히 암기하지 않아도 공식을 구할 수 있게 됩니다.)

 

벡터 a, b의 외적에 대한 행렬식은 다음과 같습니다. (a1=x, a2=y, a3=z)

벡터 a, b의 외적에 대한 행렬식

행렬식 : 해당 행렬을 대표하는 값 정도로 이해하고 넘어가시면 됩니다.

 

해당 행렬식을 구하는 공식은 다음과 같습니다.

나에겐 너무 복잡하다.

 

 

하지만 너무 복잡하기에 좀 더 간단한 사루스의 법칙을 이용하여 공식을 구해보겠습니다.

먼저 기존 행렬식 옆에 행렬식의 1열과 2열을 붙여줍니다.

기존 행렬식에 1,2열 붙인 모습

 

그다음 아래 그림처럼 같은 대각선에 있는 애들끼리 곱해준 뒤 ex) i x a2 x b3

빨간색 대각선의 합 - 파란색 대각선의 합

을 구해주면 됩니다.

빨간색 대각선의 합 - 파란색 대각선의 합

 

식으로 보면 다음과 같습니다.

사루스의 법칙 식

 

여기서 식을 더 간단히 만들 수 있습니다.

일단 i, j, k는 단위 벡터 즉 1이기 때문에 굳이 계산해주지 않아도 됩니다.

거기에 a와 b 벡터는 2차원 벡터값이기 때문에 z값이 0이 됩니다. 따라서 a3와 b3는 0이 됩니다.

이에 따라 다시 식을 만들어주면 다음과 같습니다.

간단해진 식

 

이제 예시와 함께 CCW를 구현해 보겠습니다.

평면 위에 3개의 점 A(ax, ay), B(bx, by), C(cx, cy)가 있다고 가정하겠습니다. (순서 중요)

예시

먼저 벡터 AB와 벡터 AC를 구해줍니다.

// AB = (bx - ax, by - ay)
// AC = (cx - ax, cy - ay)

// 구현 코드
data class Point(val x: Long, val y: Long)
fun getVector(a: Point, b: Point) : Point {
    return Point(b.x - a.x, b.y - a.y)
}

 

 

이제 벡터 AB, BC의 외적을 구해줍니다.

// AB x AC = AB.x * AC.y - AB.y * AC.x

// 구현 코드
fun ccw(ab: Point, ac: Point) : Int{
    val cross =  ab.x * ac.y - ab.y * ac.x // 두 벡터의 외적
}

 

추가적으로 외적의 부호에 따른 반환값을 설정해 주면 끝입니다.

// 구현 
fun ccw(ab: Point, ac: Point) : Int{
    val cross =  ab.x * ac.y - ab.y * ac.x // 두 벡터의 외적
    if (cross > 0)  return 1       // 반 시계
    else if (cross == 0L) return 0 // 직선
    else return -1                 // 시계
}

 

전체 코드입니다.

// 구현 
fun main() {

    data class Point(val x: Long, val y: Long)
    
    fun getVector(a: Point, b: Point) : Point {
        return Point(b.x - a.x, b.y - a.y)
    }

    fun ccw(ab: Point, ac: Point) : Int{
        val cross =  ab.x * ac.y - ab.y * ac.x // 두 벡터의 외적
        if (cross > 0)  return 1       // 반 시계
        else if (cross == 0L) return 0 // 직선
        else return -1                 // 시계
    }

    val AB = getVector(A, B)
    val AC = getVector(A, C)
    val ABxAC = ccw(AB, AC)
}

 

 

아래는 3개의 좌표를 통해 바로 외적을 구하는 코드입니다. 사실상 외적을 구하는 동시에 벡터 계산을 해주고 있습니다. 대부분 블로그에서는 아래의 식을 알려주고 있습니다.

// AB = (bx - ax, by - ay) 
// AC = (cx - ax, cy - ay)

// 벡터와 외적을 동시에 구할 경우
fun ccw(a: Point, b: Point, c: Point) : Int{
    //     ab.x    *   ac.y    -   ab.y    *   ac.x
    // = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) 
    val cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
    if (cross > 0)  return 1       // 반 시계
    else if (cross == 0L) return 0 // 직선
    else return -1                 // 시계
}

---

CCW 알고리즘을 이해한 대로 글을 작성해 보았습니다.

혹시 잘못된 정보가 있을 경우 지적해 주시면 감사하겠습니다.