Rotating Calipers

0. 개요 Rotating Calipers 또는 회전하는 캘리퍼스 라고 부른다. 2차원 좌표평면에 점들이 주어졌을 때, 가장 먼 두 점과 그 거리를 찾는 알고리즘이다. 알고리즘의 동작 방식이 마치 캘리퍼스를 사용하는 것 같아서 붙은 이름인 듯 하다. 1. 가장 먼 두 점 찾기 그림과 같이 2차원 좌표평면에 수많은 점들이 있다. 이 중 가장 먼 두 점을 찾고 싶을 때, 어떻게 하면 좋을까? 1) 모든 점 사이의 거리 계산하기 가장 먼저 떠오르는 방법은 무식하게(?) 모든 쌍을 찾아서 길이를 비교하는 것이다. 점이 $N$개라면 시간 복잡도가 $O(N^2)$ 이 나올 것이 뻔하다. 우리는 조금 더 빠른 시간 안에 해결할 알고리즘을 찾기 때문에, 생각을 전환해보자. 가장 먼 두 점이 될 수 있는 후보는 어떤 점..

Convex Hull

0. 개요 2차원 좌표평면에 점들이 주어졌을 때, 모든 점을 포함하는 볼록다각형 중 가장 면적이 작은 것을 만드는 알고리즘이다. 1. Convex Hull Convex Hull 은 볼록 껍질이라고도 부른다. 주어진 점들을 모두 포함하는 가장 작은 볼록다각형인데, 최외곽에 있는 점들의 일부로 구성된다는 특징이 있다. (당연하다) Convex Hull 은 점들의 회전 방향인 CCW 를 이용해서 만들 수 있다. 2. CCW Convex Hull 알고리즘을 알아보기 전에 CCW 를 간단히 코드로 복습해보자. 점 base → A → B 로 이어지는 회전 방향이 시계 반대 방향이면 양수, 시계 방향이면 음수, 일직선이면 0 을 리턴한다. typedef long long ll; struct Point { int x,..

선분 교차 판정

0. 개요 2개의 선분이 주어졌을 때, 서로 교차하는지 여부를 확인하는 방법을 알아본다. 1. CCW 이전 포스트의 CCW 를 코드로 간단히 복습하자. typedef long long ll; struct Point { int x, y; Point operator-(const Point &other) { Point ret; ret.x = this->x - other.x; ret.y = this->y - other.y; return ret; } }; ll CCW(Point a, Point b) { return a.x * b.y - a.y * b.x; } // base → a → b 의 회전방향 ll CCW(Point base, Point a, Point b) { return CCW(a - base, b - ..

CCW

0. 개요 CCW (Counter ClockWise) 는 두 벡터 또는 세 점의 회전 방향을 확인하는 알고리즘이다. 1. CCW 개념 CCW 는 기본적으로 벡터의 외적을 이용한 회전 방향을 계산한다. 기본적으로 원점을 시작점으로 하는 두 벡터의 외적을 사용한다. 두 점 A, B 을 끝으로 하는 벡터의 회전 방향은 아래와 같이 계산된다. A.x × B.y - A.y × B.x 이는 점 A의 좌표를 1행, 점 B의 좌표를 2행으로 하는 determinant (행렬식) 과 같다. 원점 O → A → B 순서의 CCW 의 값에 따라 회전 방향을 확인할 수 있다. 1) CCW(A, B) > 0: 시계 반대 방향 2) CCW(A, B) < 0: 시계 방향 3) CCW(A, B) = 0: 일직선 2. 도식 말로만 하..