[문제해결기법] 10. 계산 기하

 

계산 기하

• 2, 3차원 공간상에서 점, 선, 도형 간의 관계를 다루는 문제
• 기본 가정 : 2차원 공간, 정수좌표만 고려함. 실수 연산은 지양
• polygon : 선분들로 이뤄진 닫힌 도형. 두 선분이 만나는 점은 하나뿐이다.

모든 점을 지나는 경로

• n개의 점이 주어지면, 이 점들을 모두 지나고 시작점으로 돌아오는 경로를 구하시오. 단, 교차하지 않게
• 풀이 방법
  1. y좌표가 가장 낮은 점을 기준점으로 잡음. O(n)
  2. 이 점을 지나는 직선과 다른 점들을 잇는 직선을 모두 구하고, 각의 크기에 따라 정렬한다. O(n log n). 그리고 이 순서대로 방문하면 됨
• 각의 계산 : arctan 함수와 비슷한 성질을 가지고, 분모가 0인 경우가 없도록 하는 함수를 직접 만들어서 계산한다.

점과 폴리건의 포함 관계

• 점의 좌표가 (x,y)라고 하자.
• (x,y)-(∞,y) 직선과 도형의 모든 선분간의 교차 여부를 판정하여 교점의 수를 센다.
• 교점의 수가 짝수라면, 이 점은 도형 외부에 있다
• 교점 수가 홀수라면, 이 점은 도형 내부에 있다.

점과 볼록 다각형의 포함관계 (컨벡스 폴리곤)

• Convex polygon = 모든 내각이 180도 이하인 다각형
• 또는, 다각형 안의 두 점을 잇는 직선이 항상 다각형 내에 있는 다각형
• 다각형의 둘레를 같은 방향으로 돌 때, 항상 좌회전 또는 항상 우회전이며 회전 방향이 바뀌지 않는다.

컨벡스 헐 (Convex Hull) : n개의 점이 주어질 때, 이 점들을 모두 포함하는 가장 작은 볼록 다각형이다.

 

컨벡스 헐을 구하는 방법

 

1. 브루트 포스 : O(n^3)
   1. 가장 y좌표가 작은 점을 기준점 u로 잡는다. u는 반드시 컨벡스 헐에 포함된다.
   2. 다른 모든 점이 선분 (u,v)의 왼쪽으로 가는 점 v를 찾는다. 그 점 v는 컨벡스 헐에 포함된다.
   3. v에서 다시 2번 조건을 만족하는 점을 찾는다. 반복
2. Graham scan : O(n log n) : stack에 점을 저장
   1. 가장 y좌표가 작은 점을 기준점 u로 잡는다. u는 반드시 컨벡스 헐에 포함된다. O(n log n)
   2. 다른 점들을 각에 따라 정렬한다. O(n log n)
   3. 처음으로 검사할 점 2개(기준점 포함)를 stack에 넣고, 이 두점을 이은 벡터와, 그 다음 점과 기준점을 이은 벡터의 외적을 비교한다.
   4. 결과가 ccw이면(stack 내부의 점을 이은 벡터가 오른쪽이면) 컨벡스헐에 포함시킨다.
   5. 결과가 cw이면, 마지막에 stack에 들어간 점을 pop하고, 이전 과정부터 다시 진행한다.
   6. n-1개의 점마다 이전에 그은 선분과 새로 그은 선분의 외적을 비교하는데에 O(n)
3. Quick Hull : T(n) = O(n) + T(a) + T(b)
   1. 가장 상하좌우에 있는 점 4개는 반드시 둘레에 포함된다. 이 중 2개의 점을 잇는 선분 A와 가장 먼 점 x를 찾는다.
   2. x도 반드시 컨벡스 헐에 포함된다.
   3. A와 x가 이루는 삼각형의 내부에 있는 점들은 컨벡스 헐에 포함되지 않으므로, 삭제한다.
   4. 남은 점들에 대해 같은 과정을 반복하면, 컨벡스 헐에 포함되지 않는 점들은 모두 지워진다.
   5. 선분을 찾는데에 O(n), 가장 먼 점을 찾는데에 O(n)이 걸림
   6. 선분을 기준으로 공간을 나누어 각 공간을 a, b라고 하면,
      • Best : a=b=n/2 → T(n) = O(n log n)
      • Worst : a=1, b=n-1 → T(n) = O(n^2)
      • 총 시간복잡도는 T(n) = O(n) + T(a) + T(b)

 

아래는 graham scan 코드의 함수 작성 예시이다.

 

// Graham's scan 으로 컨벡스 헐 찾는 코드

nextToTop(stack<Point> &S): 스택에서 가장 위에 있는 두 번째 점을 반환하는 함수입니다. 
스택의 맨 위의 점을 가져온 뒤 스택에서 제거한 다음, 다시 스택에 넣지 않고 바로 그 아래에 있는 점을 반환합니다.

swap(Point &p1, Point &p2): 두 점을 교환하는 함수로, 두 개의 Point 객체를 인자로 받아서 값을 교환합니다.

distSq(Point p1, Point p2): 두 점 사이의 거리의 제곱을 반환하는 함수로, 두 개의 Point 객체를 인자로 받아서 거리의 제곱을 계산하여 반환합니다.

compare(const void *vp1, const void *vp2): qsort() 함수에 전달되어 사용되는 비교 함수입니다. 
이 함수는 두 개의 Point 포인터를 인자로 받아서 비교를 수행하고, 정렬 순서를 결정합니다. 
또한 orientation() 함수를 사용하여 점들의 방향성을 비교하고, 일정한 규칙에 따라 정렬 순서를 반환합니다.

convexHull(Point points[], int n): 볼록 껍질을 계산하는 주요 함수입니다. 주어진 점들의 배열과 배열의 크기를 인자로 받습니다. 

이 함수는 다음과 같은 단계로 수행됩니다:

가장 아래에 있는 점을 찾습니다.
아래에 있는 점이 여러 개인 경우 왼쪽에 있는 점을 선택합니다.
가장 아래에 있는 점을 배열의 첫 번째 요소와 교환합니다.
첫 번째 점을 기준으로 나머지 점들을 정렬합니다. qsort() 함수를 사용하며, compare() 함수를 비교 함수로 활용합니다.
정렬된 점들 중에서 기준점과의 각도에 따라 겹치는 점들을 제거합니다.
만약 점의 개수가 2개 이하라면 계산을 중단하고 반환합니다.
볼록 껍질을 계산하기 위해 스택을 사용합니다. 처음 세 개의 점을 스택에 넣고, 나머지 점들을 순회하면서 스택에 추가합니다.
스택에서 점들을 제거하면서 비-왼쪽 회전(non-left turn)이 되는 경우까지 제거합니다. 스택에는 최종적으로 볼록 껍질에 속하는 점들만 남게 됩니다.
이렇게 코드는 주어진 점들 중에서 볼록 껍질을 계산하여 반환하는 기능을 수행합니다.

 

컨벡스 헐 응용 : n개의 점이 있을 때, 가장 멀리 있는 두 점을 구하시오

1. 브루트 포스 O(n^2) : (n,2)의 조합을 모두 해본다
2. 컨벡스 헐을 구한다. 가장 먼 두 점은 컨벅스 헐 위에 있을 것이므로, 컨벡스 헐 위의 점들끼리의 거리 차이를 구한다.