"Convex Hull"의 두 판 사이의 차이
DnlzkWiki
(새 문서: Convex Hull(볼록 껍질)은 주어진 모든 점을 포함하는 가장 작은 볼록다각형이다. == Graham Scan == 섬네일|오른쪽|https://www.crocus.co.kr/1288 # 기준점을 잡는다. (보통 y좌표가 가장 작은 점을 기준으로 한다) # 기준점으로 하여 다른 점들을 반시계 방향으로 정렬한다. # 첫 번째와 두 번째 정점을 스택에 넣고 시작한다. # 스택에서 second와 first를 순서대로...) |
Dipolemoment (토론 | 기여) |
||
| 12번째 줄: | 12번째 줄: | ||
# 4번 과정을 next값이 없을 때까지 반복한다. | # 4번 과정을 next값이 없을 때까지 반복한다. | ||
스택에 남아 있는 점들이 Convex Hull이다. | 스택에 남아 있는 점들이 Convex Hull이다. | ||
== MonotoneChain == | |||
#Convex Hull을 상부와 하부로 나눈다. | |||
#점들은 먼저 정렬한 이후 Graham Scan과정과 같이 ccw를 사용하여 스택에 넣어준다. | |||
#하부는 상부 배열을 뒤집어 위 과정을 수행해준다. | |||
#상,하부에 겹치는 점들이 있으므로 그들을 제외 시키고 스택을 합친다. | |||
합쳐진 스택이 ConvexHull이다. | |||
2022년 4월 7일 (목) 16:14 판
Convex Hull(볼록 껍질)은 주어진 모든 점을 포함하는 가장 작은 볼록다각형이다.
Graham Scan
- 기준점을 잡는다. (보통 y좌표가 가장 작은 점을 기준으로 한다)
- 기준점으로 하여 다른 점들을 반시계 방향으로 정렬한다.
- 첫 번째와 두 번째 정점을 스택에 넣고 시작한다.
- 스택에서 second와 first를 순서대로 꺼내고 next값과 ccw를 하여 > 0인지 확인한다. (좌회전 하는지 확인)
- 좌회전한다면 볼록 껍질이 될 수 있다는 의미이고 pop했던 second를 다시 스택에 넣어 주고 next도 스택에 넣어 준다.
- 우회전한다면 second 점은 버리고 first를 스택에 넣는다.
- 4번 과정을 next값이 없을 때까지 반복한다.
스택에 남아 있는 점들이 Convex Hull이다.
MonotoneChain
- Convex Hull을 상부와 하부로 나눈다.
- 점들은 먼저 정렬한 이후 Graham Scan과정과 같이 ccw를 사용하여 스택에 넣어준다.
- 하부는 상부 배열을 뒤집어 위 과정을 수행해준다.
- 상,하부에 겹치는 점들이 있으므로 그들을 제외 시키고 스택을 합친다.
합쳐진 스택이 ConvexHull이다.
