볼록 껍질. Convex Hull

Convex Hull을 구하는 알고리즘으로는 Gift Wrapping, Graham Scan, Monotone Chain 등의 알고리즘이 있다. Graham Scan이 가장 웰노운이며 시간복잡도 O(NlogN) 으로 범용성이 높은듯하다.

Convex Hull 응용으로는 가장 먼 점 쌍 찾기기가 있다. Rotating Calipers 알고리즘이 시간복잡도 O(N)으로 가장 잘 알려진 듯 하다. 투 포인터를 이용해서 O(N)개의 쌍들만을 보고 가장 먼 점을 찾는다.

구사과님 코드를 보니 뭔가 다른 알고리즘을 쓴듯한데 뭘까??..

khleexv commented 4 years ago

더 나아가서 들로네 삼각분할, 보로노이 다어어그램, 모든점을 덮는 가장 작은 원, 사각형 같은 주제도 있는 것 같은데, 이 스레드는 아래 주제를 올리고 닫아야겠다.

내적, 외적, CCW, 선분교차, 볼록껍질, 가장 먼 점

khleexv commented 4 years ago

기하는 CCW를 볼록껍질에서 쓴다던지 하는 경우가 많으므로 한 파일에 전부 올리는게 좋을듯하다.

khleexv commented 4 years ago

khleexv / algo