Convex Hull Problem 컨벡스 헐

Convex Hull은 점들의 집합이 있을때 

이 모든 점들을 포함하는 크기가 최소인 Convex Polygon을 찾는 문제이다

728x90

Convexity

---

 

쉽게 말해 위처럼 집합 내에 있는 두 점을 연결한 선분이 집합 내에 있어야

Convex하다고 할 수 있다

하지만 우리가 찾는 것은 Convex Polygon 다각형임으로

 

모든 내각이 180도 이하라는 조건이 또 붙는다

(180도는 각이 아님 ㅋ)

 

가장간단한 풀이 방법은 뭘까??

 

좀 간지나게 mechanical way 라고 말하는데 

2차원 평면에 수직되게 못을 점들과 대응되게 박아넣은뒤 고무줄을 늘려 풀어주면

알아서 착! 감기며 Convex Hull 문제의 해를 구하게 된다

 

이렇게 시각적으로는 너무나 쉬운 내용이지많은 컴퓨터로 구현 혹은 알고리즘으로 정의 내리기가 매우 어렵다

-> 기하 알고리즘들의 특징

반응형

Package Wrapping

---

1. Anchor 지점을 정한다 (기준점), 편의상 y값이 가장 적은 값을 정하는 편이다

2. 양에 방향으로 ray, 선을 쏘아 회전시켜준다, 다른 점과 부딪칠 때 까지 -> 이점은 무조건 Convex Hull에 포함됨

3. 이제 그 점이 새로운 Anchor이 되어 다각형이 완성될 떄 까지 반복한다!!

Graham Scan

---

Cross Product를 통해 두 벡터가 좌회전을 하는지 우회전을 하는지

counter-clock wise 알고리즘을 활용한다

 

CCW

 

여기서 vector(a->b)랑 vector (b->c)의 cross product (외적)을 계산하면
clockwise (시계방향) 면 음수가 나오고

counter-clockwise (반시계방향) 면 양수가 나와서 판별할 수 있다

 

이전 점 p

현재 점 c

다음점 n

 

를 가지고 p->c->n 이 좌회전인지 우회전인지 판별해서

우회전이면 내각이 180도를 넘게됨으로 Convex하지 않아서 그 점을 solution에 포함시키지 않고

p,c,n을 업데이트해 반복해서 구하는 알고리즘이