중독에 취약 중독에 취약

1. 개요Convex Hull 알고리즘 중에서 가장 신경쓸 부분(double precision)이 적은 알고리즘으로, 어찌보면 가장 강력한 방식의 알고리즘이다. Graham's Scan 방식과 유사한 방식으로 진행되는 알고리즘이다.전체적인 방식은 유사하지만 graham scan 방식을 변형한 (위, 아래를 따로 계산하는) 방식으로 진행된다.2. 알고리즘Monotone Chain 방식은, 제일 왼쪽에 있고 가장 아래에 있는 점과 제일 오른쪽에 있고 가장 윗쪽에 있는 점이 convex hull에 포함된다는 특징을 통해 알고리즘을 진행해 나간다.주어진 점들을 x좌표와 y 좌표를 기준으로 정렬한다.아래 껍질을 넣을 스택을 초기화한다.각 점들을 정렬된 순서대로 순회한다스택의 크기가 2 이상일 때..

1. 개요 자비스의 행진 알고리즘은, convex hull 문제를 해결하기 위한 알고리즘이다. 말만 들으면 아이언맨에 나온 자비스가 생각난다. Jarvis라는 사람이 만들었고 마치 행진하듯 알고리즘이 진행되어 Jarvis's March라는 이름이 붙었다. 또 다른 이름으로는 선물 포장 알고리즘이라는 이름이 있다. 이 알고리즘은 다른 알고리즘들에 비해 상당히 속도가 느리다는 단점이 있지만, 3차원 이상의 공간으로 확장될 수 있다는 장점이 있다. 2. 알고리즘 간단하게 진행하기 위해, 3개의 정점들이 같은 직선 위에 있는 경우는 없다고 가정한다. 처음 시작할 때, 시작점 $P_0$에서 시작하고 $i = 0$으로 설정한다. 이때, $P_0$는 Convex hull에 포함되어 있는 점 중 하나로 일반적으로 가장..

1. 개요 convex hul에 속한 모든 정점들을 찾는 알고리즘으로, $O(n\log{n})$시간의 시간 복잡도를 가진다. 효과적으로 이전 값을 탐색하고 삭제하기 위해 stack 구조를 활용하여 알고리즘이 진행된다. 3차원 공간에서는 결과를 얻을 수 없다..는 단점이 있다. 컴퓨터에서는 floating point로 각도를 계산해야 하니... 오차가 꽤나 많이 생긴다는 단점도 있다. 2. 알고리즘 가장 작은 y좌표값을 갖는 정점을 시작점 $P$로 잡는다. 만약 같은 y좌표를 갖는 정점이 여러개라면 x 값이 가장 작은 것을 선택한다. 정점 목록을 $P$와 x축이 이루는 각도에 따라 정렬한다. 직접 각도를 계산할 필요는 없다. x축과 이루는 각이므로, 직선의 기울기, 내적으로도 쉽게 판별이 가능하다. 만약 ..