[알고리즘] 기하 알고리즘

기하 알고리즘에 앞서

기하학은 기본 요소로 점 , 선 , 다각형, 다면체가 있습니다. 기하문제를 풀기 위해선 기본 요소인 점 , 선, 다각형, 다면체 등을 어떻게

표현할 것인가를 결정해야 하는데 간단판 표현법 으로 좌표를 사용합니다.

기하학의 기본요소

- 점 : 1차원 물체

- 선, 다각형 : 2차원 물체

- 다면체 : 3차원 물체

기하학의 문제

- 간단한 문제 : 선분교차, 직각 삼각형, 내접 다각형

- 복잡한 문제 : 순환 외판원, CAD, 최소 신장 나무

두 선분의 교차 검사

두 선분이 주어졌을 떄, 이 둘이 서로 교차하는지 아닌지를 검사하는 것은 가장 기본적인 기하 알고리즘 중에 하나입니다. 여기서 

두 선분이 교차한다는 것은 그 두 선분이 적어도 한 점을 서로 공유함을 말하는 것이다. 기본적인 용어에는

- 선분 AB : 양 끝 점이 A와 B인 선분

- 무한직선 AB : 점 A와 B를 지나는 양방향으로 무한한 직선

- 반직선 AB : 점 A에서 시작하여 점 B를 지나는 무한한 직선

- 직선 Ax : 점 A에서 시작하여 양의 x축과 평행한 반직선

- 꺾은선 ABC : 점 A에서 시작하여 점 B를 지나 점 C에 도착하는 꺾은선

두 선분의 교차 여부를 검사하는 방법

각 선분에 대하여 양방향으로 무한한 연장선을 긋고 두 연장선의 일차방정식을 구한 후에 교점을 계산.

단순 폐쇄 경로 찾기

임의의 기준점으로부터 다른 각각의 점까지의 각도를 구한 후 올림차순으로 정렬한 다음 기준점부터 정렬한 순서대로 이으면 

그것이 단순 폐쇄 경로가 된다. 기준점이 다르면 생성된 단순 폐쇄 경로도 다르다.

여러 개의 점이 주어졌을 때 이를 꼭짓점으로 하면서 변이 서로 교차하지 않도록 하는 것을 간순 폐쇄 경로라 한다.

- 주어진 모든 점을 잇는 단순 폐쇄 경로를 구하는 방법은 기준점을 잡고 각 점과 기준점과의 각도를 계산하여 각도를

   기준으로 하여 오름차순으로 정렬하고 다음 정렬된 점들을 순서대로 연결한다.

- 단순 폐쇄 경로를 구하는 알고리즘은 각도에 따라 점들을 정렬하는 과정이 필요해서 O(nlogn) 시간이 걸린다.

- 각도 계산에 이용하는 식은 상대각도 계산식 T=dy/dx+dy를 쓰며, 이 식은 기준점이 아닌 다른 모든 점에 대하여 분모가 0이 안됨.

점과 다각형의 상대 위치 검사

 - 어떤 점의 위치가 다각형의 내부인지 외부인지 결정하는 것

- 점을 지나는 임의의 반직선이 다각형의 변을 통과하는 경우에 교점의 개수가 홀수면 점은 다각형 내부 , 짝수면 외부 

- 점이 다각형 내부에 포함되는걸 알려면 그점에서 양의 x축 방향으로 수평 선을 그어 다각형의 변과 교차되는 횟수.

블록 껍질 찾기

임의의 집합 X에 대한 볼록 껍질이란 X를 포함하는 가장 작은 볼록 집합을 말하며 여러 개 의 점이 주어졌을 때 그 점들을 모두

포함하는 가장 작은 볼록 다각형을 그 점집합의 볼록 껍질(convex hull)이라고 함.

- 볼록 껍질에는 짐꾸러기, 그레이엄 알고리즘 있고 평균적으로 O(n^2)의 실행시간을 갖는다.

볼록 다각형

- 다각형 내부의 임의의 2점을 연결하는 선분이 반드시 다각형 내부에 존재 하는 다각형을 말함.

- 모든 내각이 180도 보다 작고 어느 두 점을 연결하더라도 그 선분이 다각형 내부에 존재하는 다각형을 말함.

오목 다각형

- 오목 다각형은 내각에 180보다 크고 안쪽으로 오목하게 들어감. 오목 다각형의 이웃하지 않는 두 꼭짓점을 연결하는 대각선

중에는 도형의 바깥쪽을 지나는 것이 반드시 있고, 오목 다각형의 변을 연장하면 그 연장된 선이 다각형의 안쪽을 지남.

짐꾸러기 알고리즘

- 무한대에서부터 임의의 각도로 직선을 점집합 쪽으로 접근시켜서 직선과 처음 만나는 점들로 볼록 껍집을 형성하는 방법을

의미함.

- 양의 x축 방향과 이루는 각도를 계산하여 최소의 각을 갖는 다음의 꼿짓점 및 기준점으로 취함.

단계 1 : y좌표가 최소의 점을 최초의 꼭짓점으로 선택한다.

단계 2 : 기준점에서 아직 선택이 안 된 모든 점들에 대한 각도를 계산.

단계 3 : 최소의 각을 갖는 점을 다음의 볼록 껍질의 꼭짓점으로 선택한다.

단계 4 : 지금 선택한 꼭짓점이 최초의 기준점이면 계산 끝, 아니면 그점을 기준점으로 하여 단계2 부터 반복.

그레이엄의 볼록 껍질 알고리즘

- 주어진 점집합에서 우선 단순 폐쇄 경로를 구한 다음에 볼록 껍질이 될 수 없는 점들을 제거해 나가는 방법으로 볼록 껍질을

찾는 방법.

- 어떤 기준점으로부터 단순 폐쇄 경로를 따라 나가면 항상 시계 반대 방향으로 꺾이게 되는데, 도중에 시계 방향으로 꺾이는

방향으로 꺾이는 선분이 있다면 제거해야한다.

- 최악의 경우 실행시간 O(nlogn) 스캔 알고리즘.