알고리즘 - 기하 알고리즘

CCW(Counter Clockwise)

세 점이 어떤 위치 관계로 놓여있는가를 판단하기 위한 알고리즘.

기하 알고리즘의 기본.

 

세 점이 일직선, 가운데점을 기준으로 반시계, 시계 방향으로 놓여있는 경우를 판단하는 알고리즘.

 

각 점 사이의 벡터(A,B 와 B,C) 에 대해 외적을 계산하여 0이 나오면 평행으로 일직선, 양수라면 반시계, 음수라면 시계방향으로 나타난다고 본다.

 

 

컨백스 헐(Convex Hull)

2차원 평면상의 여러 점중에 다른 모든 점을 포함할수 있는 볼록 다각형을 찾는 알고리즘.

 

만약 10개의 점이 존재하면 점 10개를 모두 포함하는 면적을 가진 볼록 다각형을 찾는것.

 

1. 기준점을 잡는다. 보통 기준점은 최하단 좌측에 위치한 점을 잡음.

2. 기준점의 반시계방향으로 다른 점들을 각도순으로 정렬. 각도상 최 우측부터 1번 2번 식으로 정렬.

3. 스택에 정렬한 점들을 하나씩 넣는다.

4. 두개 이상의 점이 스택에 들어있다면, 스택 맨위의  두 점과 다음 점을 이용해 CCW알고리즘 결과를 구함. 양수, 반시계방향이라면 스택에 넣고, 아니라면 마지막에 넣은점을 빼고 다시 진행.

5. 모든 점에 대해 연산하고 스택에 남은 점이 볼록다각형을 구성하는 점.