Finding Convex Hull (Graham's Scan) - 외곽선 찾기, 임의의 사각형 내부에 임의의 점 존재 확인

Convex Hull 을 한국어로 정확하게 해석하자면 '볼록 껍데기' 정도라 하겠다. 2차원 공간에서 임의의 점들이 x와 y 축에 퍼져 있을때 이 점들의 외곽선을 연결하는 꼭지점들 (Vertex) 만 찾아내는 알고리즘이 바로 Graham's Scan이다. 

일단 몇가지 정의 해야 할 것들이 있다. Q는 2차원 공간상의 임의의 점들의 집합이고 각각의 점들을 P0, P1, P2 ... 와 같이 표현한다.

스택 S는 점들을 저장하는 스택인데 이 스택에 모든 점들을 최소한 한번씩은 집어 넣은 다음, 만약 어떤 점이 외곽선을 구성하는 점이 아닐 경우 스택에서 뽑아낸다. 결국 모든 과정을 끝낸후에 스택에 남은 점들은 외곽선을 구성하는 점들이 될것이다. 

그리고 CH(Q)는 Convex Hull(Q)의 약자로 점의 집합 Q에서 외곽선을 구성하는 점들만의 집합을 말한다. 이 CH(Q)가 우리가 최종적으로 원하는 점들이 될것이다.

자, 이제 단계별로 Graham's Scan을 살펴보자.

1. P0 정하기 - 제일 먼저 해야 하는 것은 시작점을 정하는 일이다. P0는 가장 작은 y 값을 가지는 점이다. 만약 가장 작은 y 값을 가지는 점이 한개 이상 있다면 그들중 가장 작은 x 값을 가지는 점을 찾아서 그 놈을 P0로 정한다. 이렇게 정하는 이유는 Graham's Scan 이 기본적으로 cross product를 사용하기 때문이다.

간단하게 말해서 P0, P1, P2 라는 3개의 점이 있을때, (이 세점은 직선상에 놓인 점이 아니어야 한다는 가정아래) 이 세개의 점의 외적 (cross product)의 부호를 구하면 P2 점이 P0와 P1이 만드는 직선을 기준으로 왼쪽에 놓이는지 혹은 오른쪽에 놓이는지 알수 있다. 이것을 Pseudocode로 표현하면, 다음과 같다.

# Three points are a counter-clockwise turn if ccw > 0, clockwise if
# ccw < 0, and collinear if ccw = 0 because ccw is a determinant that
# gives the signed area of the triangle formed by p1, p2, and p3.
function ccw(p1, p2, p3):
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)

만약 마지막 세번째 점이 앞의 두점이 이루는 직선의 왼쪽에 있으면 Counter-clockwise가 되어 ccw 함수는 양의 값을 리턴하고 반대로 세번째 점이 앞의 두점이 이루는 직선보다 오른쪽에 있다면 Clockwise가 되어 ccw 함수는 음의 값을 리턴한다. 만약 세점이 직선상에 위치하게 되면 0을 리턴한다.

2. 점 P0를 기준으로 각 점마다 각도 구하여 작은 순서에서 큰 순서로 정렬하기 - 이 과정이 내가 조금 헷갈렸던 부분인데, 나는 원점을 기준으로 각도를 구했다가 낭패를 봤다. 

구해야 하는 각도는 위 그림처럼 원점을 기준으로 한 각도가 아닌 P0 점을 기준으로 한 각 점들의 각도를 구해야 한다. 이것을 구하기 위해서는 atan2 함수를 사용하면 된다. 원래 tans는 x의 증가량 분의 y의 증가량인데 이 구해진 기울기 값을 tan의 역함수인 atan2 함수에 대입하면 각도가 나온다. 다만, +, - 기호에 주의해야 하는데 이건 웹 서핑하다보면 각 언어별로 적절한 코드가 존재하니 찾아보면 된다. Google 에서는 Angle between two points 라고 하면 여러개가 뜬다.

옆의 그림은 Graham scan을 간단하게 설명한 그림이다. (위키에서 퍼왔음) 일단 P, A, B, C, D의 점들이 있는데 가장 y값이 적으면서도 가장 x 값이 적은 P 점을 시작점으로 잡는다. 그리고 P 점을 기준으로 각도를 구하는데 각도가 적은 순으로 나열하면 A, B, C, D가 된다. 이제 알고리즘을 돌리기 위한 준비가 끝났다.

3. 스택 S에 첫 세점 (시작점 포함) 을 집어 넣는다. 왼쪽 그림에서는 P, A, B가 첫 세점이다. 그러면 스택 S는 |P|A|B| <- 요런 모습을 하고 있을 것이다. (B가 가장 상위 스택)

4. 이제는 For문을 이용하여 i = 3 부터 남아 있는 점들 모두에 대해 스캔을 시작한다. 각각의 i에 대해서 3개의 점이 이루는 cross vector의 방향성을 체크하여 그 값이 음이면, 즉 앞 두점이 이루는 선보다 오른쪽에 위치하면 그 점은 외곽선 내부에 위치하므로 과감하게 스택 S에서 빼버리고 그 다음 점을 스캔한다. 이것을 수도 코드로 표현 하자면,

for i = 3 to m (여기서 m은 전체 포인트의 갯수)

   

   do while (스택 S의 최상위 바로 밑의 점과 최상위 점, 그리고 포인트 Pi 가 시                     계방향인지 반 시계 방향인지 검사하여 만약 시계 방향이라면, 즉                       앞 두점이 만드는 직선보다 세번째 점이 오른쪽에 있다면)

           do Pop(S) // 스택 S에서 최상위 점 제거

   Push(Pi, S)    

이걸 걍 보면 잘 이해가 안되니 하나하나 그림을 보면서 해보자.

우선 앞서 말한것 처럼 스텝 1,2를 끝내고 나면 스택 S에는 |P|A|B| 가 들어가 있는 상태다. 여기서 for 문을 들어가게 되면 최상위 스택의 바로 아래 점 (A)와 최상위 스택의 점 (B) 그리고 Pi 점인데 i가 3에서 시작하므로 P3인 점은 바로 C이다. (P0 = P, P1 = A, P2 = B, P3 = C, P4 = D)

이 세점을 이어보면 AB가 만드는 직선의 왼쪽편에 점 C가 존재하므로 조건이 만족하지 않는다. 따라서 while 문을 탈출하여 Push(Pi, S)를 하게 되는데, 그러면 스택에는 |P|A|B|C| 처럼 C가 들어가게 되고 제일 위에 위치한다.

이때 while 문 내부의 조건을 함수로 표현하면 간단하게 ccw(스택 최상위 바로 아래 점, 스택 최상위 점, Pi) <= 0 로 표현 가능하다. 0보다 적거나 같다는 의미는 '일직선 상에 놓이거나 아니면 오른쪽 편 (시계 방향으로 돌거나)에 위치하거나' 라는 의미다.

자 그런데, 스택에 C를 넣었다는 의미는 즉, C가 외곽선을 구성하는 점들중 하나라는 의미인데 그림을 보면 그렇지 않다. 이는 바로 다음 for 루프에서 찾아진다.

i 값이 하나 증가하여 4가 되었고 마찬가지로 while 문에 들어가게 되면 최상위 아래점 (B)와 최상위점 (C) 그리고 P4 (i=4) 점에 대해 방향성 검사를 한다. 이때 점 B와 C가 이루는 직선의 '오른쪽' 편에 점 D가 존재하게 된다. 고로 음의 값을 리턴하며 마침내 Pop(S) 문을 수행한다.

고로 최상위 스택값이던 C점이 스택에서 제거가 된다. 고로 스택 S는 |P|A|B| 가 되어 원상 복구된다. 즉, C점을 제거한 셈이다. 이 과정은 아주 간단한 논리다. 가장 외곽에 존재하는 점들은 절대로 앞 두점을 기준으로 한 직선의 오른쪽 편에 존재하지 않는다는 원리를 사용한 것이다. 만약 오른편에 존재한다면 그 점은 외곽선에 포함되지 않는다는 간단한 논리인 셈이다.

그리고 이것이 while 문인 이유는 두 개 이상의 점이 실제로는 외곽선 상의 점이 아님에도 불구하고 외곽선으로 판정되는 경우가 종종 있기 때문에 이런 경우 이런 모든 점들을 제대로 스택에서 제거하기 위해서 while문을 이용하여 스택에서 차례 차례 제거한다. while 문에서 i 값은 늘 고정되어 있는데 비해 스택의 최상위 점만 계속 제거해 나가는 구조를 보면 쉽게 이해할 수 있다.

마지막으로 while문을 벗어난 후 현재 i = 4의 점인 D를 스택 S에 집어 넣는다. |P|A|B|D| 요렇게. 결국 남은 4개의 점은 위의 그림에서 정확한 외곽선을 이루는 점들이다. 

이런 알고리즘이 그닥 무슨 효용이 있을까 생각하시는 분들 많을 텐데 생각외로 매우 유용할 수 있다. 내가 이 알고리즘을 사용하려고 했던 목적은 사실 임의의 모양을 가지는 사각형이 있고 임의의 점 x가 있을때 이 x 점이 사각형 내부에 존재하는지 아니면 외부에 존재하는지 체크하는데 이 알고리즘을 적용했다.

만약 사각형의 네개의 점을 위의 그림에서의 P, A, B, D라고 한다면 임의의 점 x가 사각형 내부에 존재한다면 사각형의 각 직선 (PA, AB, BD, DP) 에 대해 점 x는 반드시 왼쪽에 위치해야 한다. 만약 점 x가 사각형 외부에 존재하거나 직선위에 놓이게 되면 방향성 검사에서 음의 값이나 0을 리턴하게 되어 있다. 

네이버에서 임의의 사각형 내부에 존재하는 점 찾기를 검색해 보면 각 직선의 방정식을 이용하기 등 좀 까다로운 방법들이 많은데 내가 볼때는 이 방법이 가장 '컴퓨터 프로그램'적이지 않나 싶다. 물론 주의해야 할 점은 numerical error가 존재하므로 좌표계를 적절히 조절할 필요가 있다는 점이지 싶다.