728x90 반응형 Graham Scan1 [Algorithm] 컨벡스 헐 만들기(Convex Hull), Graham Scan 아래 그림과 같은 점들이 있다고 하자. 모든 점들을 이어서 다각형을 만들고 싶다면 어떻게 할 수 있을까? 1. 가장 먼저 y 좌표가 가장 작은 점을 기준으로 잡고 다른 점들과 모두 연결한다. 2. 기준으로 잡은 점을 관통하는 x축에 수평인 직선을 긋고 각도를 계산한 후 작은 순서대로 번호를 매긴다. 3. 번호 순서대로 연결한다. 위와 같은 방식으로 모든 점을 지나는 다각형이 완성되었다. 물론 당연하게도 이 다각형 외에도 여러 모양의 다각형을 만들 수 있다. 각도 알아내기 점들을 각도 순서대로 정렬하려면 각도를 알아낼 수 있어야 한다. 각도를 알아내는 방법은 탄젠트 값을 구한 다음에 탄젠트의 역 함수인 아크 탄젠트 함수에 넣으면 구할 수 있다. 그런데 여기서는 정확한 각도를 알아내는 것이 중요한 것이 아니.. 2023. 6. 2. 이전 1 다음 728x90 반응형
