기하 알고리즘

기하학

좌표를 사용하여 점, 선, 다각형, 다면체 등의 기본 요소를 어떻게 표현할 것인가 결정

 

기하학의 문제

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

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

 

 

---

1. 선분 교차

- 두 선분이 주어졌을 때, 이 둘이 서로 교차하는지 아닌지 검사하는 알고리즘

- 두 선분이 교차한다는 것은 두 선분이 적어도 한 점을 서로 공유함을 말하는 것이다.

 

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

-  각 선분의 무한 연장선을 긋고 두 연장선의 일차방정식을 구한 후 교점을 계싼한다.

 

2. 단순 폐쇄경로 찾기

임의의 기준점으로부터 다른 각각의 점까지의 각도를 구한 후, 올림차순으로 정렬한 다음 기준점부터 정렬한 순서대로 이으면 그것이 단순 폐쇄 경로가 된다.

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

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

- 시간복잡도 O(nlogn)

- 각도 계산식  T = dy/dx + dy

 

 

Reference

https://devhwan.tech/53