Graham Scan

1. 정의

Graham Scan은 평면 상에서 유한한 점들의 볼록 껍질(Convex hull)을 찾는 방법이다.

자세한 사항은 아래를 참고 하자.

ko.wikipedia.org/wiki/%EA%B7%B8%EB%A0%88%EC%9D%B4%EC%97%84_%EC%8A%A4%EC%BA%94

그레이엄 스캔 - 위키백과, 우리 모두의 백과사전

 

2. 문제

8개의 좌표를 순서대로 입력받는다. (3,1) (1 3) (2 2) (3 2) (1 2) (2 3) (1 1) (2 1)

출력에서는 convex hull을 이루는 점의 개수 및 그 때의 점을 출력해보자.

위와 같이 8개의 점을 입력했다면 출력으로는 convex hull을 이루는 점의 개수는 5개이다.

 

3. 문제에 앞서 필요한 기능 정리

이 입력 받은 좌표들을 정렬을 해야 하는데 정렬하는 기준은 y좌표값이 가장 작은 순으로 오름 차순 정렬을 한다.

만약 y좌표값이 일치하는 점이 있으면 x좌표값이 가장 작은 순으로 오름 차순 정렬 한다.

아래는 입력받은 좌표를 정렬한 형태이다.

위의 배열의 각 좌표들을 xy평면에 나타내면 다음과 같다.

 

그리고 이제 축점(pivot point)를 잡아야 하는데, 이는 배열의 0번째 요소를 축점으로 한다.

즉, (1,1)이 축점이다.

 

그리고, 축점을 기준으로 각도가 가장 작은 순으로 정렬을 해야 한다.

두 점 사이의 각도를 구하는 방법은 앞에서 한 내용이다.

축점을 startPos로 두고, 나머지 한 점을 위의 배열의 점으로 두고 구하면 된다.

그러면 다음과 같이 정렬이 된다.

a가 축점과의 이루는 각도로 단위는 호도법이 아닌 각도이다.

각도를 쓴 이유는 호도법보다는 각도를 쓰는 것이 우리가 직관적으로 보기 편하기 때문이다.

 

일단 여기 까지의 내용을 만들어 보자.

두 점 사이의 각도를 구하는 구하는 것은 앞에서 한 내용이다. 아래를 참조하자.

designatedroom87.tistory.com/102

점과 점의 각도

 

y축 정렬 함수와 각도 정렬 함수를 제외한 나머지 함수들은 앞에서 만든 함수이다.

아래는 y좌표값을 오름 차순 정렬을 했을 때의 모습이다. 이는 디버깅 모드에서 캡쳐한 사진이다.

아래는 y좌표값을 정렬하고 나서 축점과의 각도를 구한 후에 각도를 오름 차순으로 정렬 했을 때이다.

이 또한 디버깅 모드에서 캡쳐한 사진이다.

헤더 파일 & 소스 파일

main.c

0.01MB

point.h

0.00MB

 

4. 구현 방법 탐색

본격적으로 탐색을 시작해 보도록 하자.

자료구조에서 스택이 필요하며, 초기에 스택에 좌표를 2개 차례로 저장하도록 한다.

스택에는 좌표 배열의 인덱스를 저장한다.

스택에 직접 좌표를 저장해도 괜찮지만 좌표 배열의 인덱스만 저장해도 나중에 충분히 좌표를 얻을 수 있다.

 

스택에서 데이터 2개를 꺼내와서 각 각 first와 second 변수에 저장한다. 

first와 second변수는 pos배열의 인덱스가 저장이 된다.

즉, 아래에 first에 1값이 저장되어 있는데 이는 pos[1]의 좌표인 (2,1)을 의미한다.

second에 0값이 저장되어 있는 것은 pos[0]의 좌표인 (1,1)을 의미한다.

아래의 그림을 보도록 하자.

그 다음으로 해야할 작업이 세 점을 이용해서 반시계 방향인지 시계 방향인지를 확인해야 하는데,

이는 벡터의 외적을 통해서 구할 수 있다.

여기서의 세 점이란 pos[second], pos[first], pos[next] 이다.

벡터의 시점은 pos[second]로 (1,1)이며 종점은 각 각 pos[first]와 pos[next]이다. (2,1)과 (3,1)이다.

우선 벡터들을 정의해 보면,

시점을 pos[second] 로 하고 종점을 pos[first]으로하는 벡터를 v1이라 정의하고

시점을 pos[second] 로 하고 종점을 pos[next]으로하는 벡터를 v2이라 정의하면

v1과 v2를 외적한 결과가 양수가 나오면 반시계 방향이다. 즉, 연산은 v1 X v2 를 구한다.

우선 그림을 통해서 알아보자.

위의 그림에서 두 벡터는 서로 방향이 같으므로 반시계 방향도 시계 방향도 아니다.

(즉, 반시계 방향이 아니다.)

반 시계 방향이 아니면 점 first를 스택에 저장하지 않는다.

그리고 나서 스택에 데이터가 2개 이상인지를 확인하는데 현재 스택에 데이터가 하나이므로

스택에서 데이터를 2개를 가지고 올 수 없다. 그렇기 때문에 next를 스택에 저장하고(2번 인덱스)

next에 다음 점을 준비한다. 다음 점은 3번 인덱스가 된다.

그러면 아래와 같은 구조가 된다.

 

그리고 나서 다시 스택에서 데이터를 2개 꺼낸다.

세 점을 이용해서 반시계 방향인지 시계 방향인지를 확인을 해보자.

시점을 pos[second] 로 하고 종점을 pos[first]으로하는 벡터를 v1이라 정의하고

시점을 pos[second] 로 하고 종점을 pos[next]으로하는 벡터를 v2이라 정의하면

v1과 v2를 외적한 결과가 양수가 나오면 반시계 방향이다.

시점은 (1,1)이고, pos[first]는 (3,1)이고 pos[next]는(3,2)이다.

아래의 그림을 보자.

두 벡터의 외적을 하면 이는 반 시계 방향이므로 이 경우에는 first를 스택에 저장하고

next도 스택에 저장을 하고 next를 다음 점으로 설정한다. next는 4가 된다.

그러면 아래의 그림과 같이 된다.

 

그리고 나서 다시 스택에서 데이터를 2개 꺼낸다.

 

세 점을 이용해서 반시계 방향인지 시계 방향인지를 확인을 해보자.

시점을 pos[second] 로 하고 종점을 pos[first]으로하는 벡터를 v1이라 정의하고

시점을 pos[second] 로 하고 종점을 pos[next]으로하는 벡터를 v2이라 정의하면

v1과 v2를 외적한 결과가 양수가 나오면 반시계 방향이다.

시점은 (3,1)이고 pos[first]는 (3,2)이고 pos[next]는(2,2) 이다.

아래의 그림을 보자.

반 시계 방향이므로 first를 스택에 저장하고 next를 스택에 저장하고 next에 다음 점으로 설정한다.

아래의 그림과 같다.

 

그리고 나서 다시 스택에서 데이터를 2개 꺼낸다. 아래의 그림과 같다.

세 점을 이용해서 반시계 방향인지 시계 방향인지를 확인을 해보자.

시점을 pos[second] 로 하고 종점을 pos[first]으로하는 벡터를 v1이라 정의하고

시점을 pos[second] 로 하고 종점을 pos[next]으로하는 벡터를 v2이라 정의하면

v1과 v2를 외적한 결과가 양수가 나오면 반시계 방향이다.

시점은 (3,2)이고 pos[first]는 (2,2)이고 pos[next]는(2,3) 이다.

위 그림과 같이 시계 방향이 된다. 시계 방향이면 first를 스택에 저장하지 않는다.

스택에 데이터가 2개 이상 저장되어 있기 때문에 다시 스택에서 데이터를 2개 꺼낸다.

아래의 그림과 같다.

 

세 점을 이용해서 반시계 방향인지 시계 방향인지를 확인을 해보자.

시점을 pos[second] 로 하고 종점을 pos[first]으로하는 벡터를 v1이라 정의하고

시점을 pos[second] 로 하고 종점을 pos[next]으로하는 벡터를 v2이라 정의하면

v1과 v2를 외적한 결과가 양수가 나오면 반시계 방향이다.

시점은 (3,1)이고 pos[first]는 (3,2)이고 pos[next]는(2,3) 이다.

반 시게 방향이므로 first를 스택에 저장하고, next를 스택에 저장하고

next에 다음 점을 세팅한다. next는 6이 된다.

 

다시 스택에서 데이터를 2개 꺼낸다. 아래의 그림과 같다.

 

세 점을 이용해서 반시계 방향인지 시계 방향인지를 확인을 해보자.

시점을 pos[second] 로 하고 종점을 pos[first]으로하는 벡터를 v1이라 정의하고

시점을 pos[second] 로 하고 종점을 pos[next]으로하는 벡터를 v2이라 정의하면

v1과 v2를 외적한 결과가 양수가 나오면 반시계 방향이다.

시점은 (3,2)이고 pos[first]는 (2,3)이고 pos[next]는(1,2) 이다.

아래의 그림을 보자.

위 그림에서 반 시계 방향이므로 first를 스택에 저장하고 next를 스택에 저장한다.

그리고 next에 다음 점을 준비한다. next는 7이 된다. (배열의 마지막 인덱스 값이다.)

아래의 그림과 같이 된다.

 

다시 스택에서 데이터를 2개 꺼낸다. 아래의 그림과 같다.

세 점을 이용해서 반시계 방향인지 시계 방향인지를 확인을 해보자.

시점을 pos[second] 로 하고 종점을 pos[first]으로하는 벡터를 v1이라 정의하고

시점을 pos[second] 로 하고 종점을 pos[next]으로하는 벡터를 v2이라 정의하면

v1과 v2를 외적한 결과가 양수가 나오면 반시계 방향이다.

시점은 (2,3)이고 pos[first]는 (1,2)이고 pos[next]는(1,3) 이다.

아래의 그림을 보자.

시계 방향이므로, first를 스택에 저장하지 않는다. 스택에는 데이터가 2개 이상 있기 때문에

다시 스택에서 데이터를 2개 꺼낸다. 

 

세 점을 이용해서 반시계 방향인지 시계 방향인지를 확인을 해보자.

시점을 pos[second] 로 하고 종점을 pos[first]으로하는 벡터를 v1이라 정의하고

시점을 pos[second] 로 하고 종점을 pos[next]으로하는 벡터를 v2이라 정의하면

v1과 v2를 외적한 결과가 양수가 나오면 반시계 방향이다.

시점은 (3,2)이고 pos[first]는 (2,3)이고 pos[next]는(1,3) 이다.

아래의 그림을 보자.

반 시계 방향이 된다. first를 스택에 저장하고 next를 스택에 저장한다.

그리고 next에 다음 점을 준비한다. next는 8이 된다. 

아래의 그림을 보자.

위의 그림에서 보다시피, next는 배열의 범위를 벗어났으므로 모든 탐색을 종료한다.

이 스택에 들어있는 점 인덱스들이 convex hull을 이루는 점들이다.

 

5. 위의 내용 구현

먼저 위의 내용에서 두 개의 함수를 추가하는데 앞에서 한 내용이다.

벡터의 외적을 구하는 함수와 세 점의 방향을 구하는 함수이다.

그리고 아래는 메인 함수이다.

프로그램 실행결과

 

헤더 파일 & 소스 파일1

common.h

0.00MB

main.c

0.01MB

MyStack.c

0.00MB

MyStack.h

0.00MB

point.h

0.00MB

 

헤더 파일 & 소스 파일2

위에서는 스택을 직접 구현해서 만든 것인데, 아래는 라이브러리에서 제공하는 스택을 사용한 것으로

C++을 이용한 것이다.

모든 내용은 위와 같다.

main.cpp

0.01MB

point.h

0.00MB

 

우리가 최종적으로 스택에 저장한 점들을 그래픽적으로 보고 싶을 것이다.

그러기 위해서 스택에 저장한 점들을 엑셀 파일에 저장해서 

이 점들을 그래픽적으로 보도록 하자.

우선 아래의 함수를 하나 정의 하도록 하자.

위의 함수 호출은 아래와 같이 메인함수에서 호출 하는데 약간의 부분이 변경되었다.

아래는 메인함수의 일부분이다.

아래는 실행결과이다.

그리고 실행을 한 후에 솔루션에 다음과 같은 경로에 엑셀 파일이 존재함을 볼 수 있다.

엑셀 파일을 열어보자. 파일을 열어보면 다음과 같이 점들이 찍혀 있을 것이다.

이 점들이 들어있는 영역을 드래그해 보자.

이렇게 드래그한 후에 [삽입] 탭에 들어가면 [분산형]이란 목록이 보일 것이다.

분산형에서 직선 및 표식이 있는 분산형을 선택하면 다음과 같은 그래프가 뜬다.

WriteExcelFile 함수에서 축점인 0번 점을 스택에 저장하지 않고 엑셀 파일에 저장하고

실행하면 마지막점인 (1,3)에서 (1,1)로의 직선이 그려지지 않는다.

 

최종 헤더 파일 & 소스 파일

common.h

0.00MB

main.c

0.01MB

MyStack.c

0.00MB

MyStack.h

0.00MB

point.h

0.00MB