블록 껍질(Convex Hull)

Cunvex Hull(블록 껍질)은 2차원 평면상에 여러개의 점이 있을 때,

그 점들 중에서 일부를 이용하여 볼록 다각형을 만들되,

볼록 다각형 내부에 사용하지 않은 모든 점을 포함시키는 것을 의미합니다.

이를 구현하는 알고리즘은 크게 3가지 존재합니다.

(1) Jarvis March 알고리즘 ← O(NH)

(2) Monotone Chain 알고리즘 ← O(NlogN)

(3) Graham Scan 알고리즘 ← O(NlogN)

 

Graham Scan 알고리즘을 이용한 Convex Hull 구현

① 첫번째 기준 좌표를 설정합니다. 

    일반적으로 y 좌표가 가장 작은 것.

    (가장 작은 y 좌표값이 2개 이상이라면 x 좌표 값이 작은 것)

 

② 기준점(first)을 중심으로 각도순 정렬(반시계 방향(CCW)으로 좌표 정렬)

    ※ 벡터를 사용하여 평면 위에 놓여진 세 점의 방향관계를 구할 수 있는 알고리즘

    정렬 결과: [A B C D E F G]

③ Graham Scan 알고리즘 이용하여 블록 껍질을 이루는 좌표찾기

    - 첫번째 기준점을 시작으로, first / second / third 값을 갱신하며 ccw 여부 확인

▶ CCW (O)

 

▶ CCW (O)

 

▶ CCW (X)

 

▶ CCW (O)

 

▶ CCW (X)

 

▶ CCW (O)

 

▶ CCW (O)

    블록 껍질을 형성하는 모든 좌표 [A, B, C, F, G]를 찾았으면

    각 정점을 연결하면 블록 껍질이 형성되는 것을 확인할 수 있습니다.

 

관련 문제

- [BOJ] 1708 블록 껍질 (Graham Scan 알고리즘 이용)

[BOJ] 백준 1708 블록 껍질