회전하는 캘리퍼스 알고리즘(Rotating Calipers Algorithm)은 캘리퍼스로 무언가를 재는 과정을 알고리즘화 한 것 입니다.캘리퍼스는 작은 물건의 지름, 너비등을 측정할 때 쓰는 도구로 두 개의 평행한 변 사이에 물체를 끼우고 변 사이를 측정합니다.기하 문제에서는 이를 볼록 다각형에 완전히 포함하는 가장 긴 선분의 길이를 구하는 용도로 쓸 수 있습니다.이 때 이 길이를 볼록 다각형의 지름이라고도 합니다.회전하는 캘리퍼스 알고리즘은 실제 캘리퍼스와 비슷하게 다각형을 평행한 두 직선 사이에 끼우고다각형을 따라 두 직선을 한 바퀴 돌리면서 두 직선에 닿는 꼭지점들 간의 거리를 구합니다.이를 좀 더 편하게 구현하기 위하여 가장 왼쪽에 있는 점과 오른쪽에 있는 점에 수직선을 붙이고 시작한 뒤,어느 ..
볼록껍질(Convex Hull)은 컨벡스 헐이라고도 불리며 주어진 점들을 모두 포함하는 최소 크기의 다각형을 말합니다.볼록껍질을 구하기 위하여 그라함 스캔 알고리즘(Graham's Scan Algorithm)을 사용합니다.이 알고리즘은 먼저 y좌표가 가장 작고 y좌표가 같다면 x좌표가 가장 작은 점을 선택한 뒤,그 선택한 점을 제외한 점을 반시계 방향으로 정렬하여 순서대로 점을 보며 스택에 push 합니다.이 때 push하기 전 스택에 점이 2개 이상 들어있을 때 그 두 점을 이은 직선 기준으로 왼쪽에 이 점이 있지 않다면스택에서 조건에 만족할 때까지 pop한 뒤 push를 해주며모든 점을 보았을 때 스택에 남아있는 점이 최소 크기의 다각형을 이루는 점입니다.직선 기준으로 왼쪽에 있는 지는 앞서 계산 기..
다각형 클리핑 알고리즘(Polygon Clipping Algorithm)은 다각형으로 다른 다각형을 잘라내는 알고리즘입니다.많이 사용하는 다각형 클리핑 알고리즘으로는 서덜랜드-호지맨 알고리즘(Sutherland-Hodgman Algorithm)으로볼록 다각형으로 다른 단순 다각형을 잘라내는 알고리즘입니다.볼록 다각형의 여러 반평면의 교집합을 구하는 것이 주원리로앞서 계산 기하에서 배운 CCW를 이용하여 각 점이 평면의 어느 쪽에 속하는 지 확인하며직선의 왼쪽에 있는 점들과 변이 직선을 가로지를 경우 변과 직선의 교차점 또한 포함 시키는 과정을 반복합니다.
계산 기하 알고리즘(Computational Geometry Algorithm)은 각종 기하학적 도형을 다루는 알고리즘입니다.계산 기하의 기본 도구로는 방향과 크기의 의미를 모두 포함하는 벡터(Vector)를 자주 사용합니다.이유는 벡터를 사용하였을 때 더 많은 계산을 빠르고 간편하게 할 수 있으며벡터끼리의 연산인 내적과 외적을 활용하여 더 효율적으로 문제에 접근할 수 있기 때문입니다.내적을 이용하여 두 벡터의 사이각, 두 벡터의 직각 여부, 벡터의 사영을 쉽게 구현할 수 있으며외적을 이용하여 삼각형 또는 사각형의 면적, 두 벡터의 방향을 판별할 수 있습니다.이 때 벡터의 방향을 판별하는 기법을 CCW(Counter-Clockwise) 알고리즘이라 하며두 벡터의 방향이 반시계 방향이면 양수, 시계 방향이..