2024. 11. 9. 19:54ㆍ카테고리 없음
안녕하세요! 뤀카입니다. 오늘은 심화 기하학 알고리즘인 볼록 껍질(Convex Hull) 알고리즘에 대해서 알려드리겠습니다.
볼록 껍질은 주어진 점들을 이어서 가장 큰 도형을 만드는 알고리즘입니다. 쉬워 보인다고요? 안 쉽다니까요 직접 해보세요
쉽진 않습니다. 어느 정도 난이도냐면 최저가 P5이고요, 최고는... R1입니다.
참고:
파이썬 설명이 많이 없더라고요. 그래서 파이썬으로 배우느라 고생해서....
파이썬으로 글 쓰는 거입니다. c++은 나중에 올려드릴게요.
자 이제 본격적인 설명 하겠습니다.
자 대표적으로는 그라함 스캔이 있는데요, 다음은 시뮬레이션 영상입니다.
https://www.youtube.com/watch?v=Ps1idzOx6LA
어떻게 저렇게 하냐고요?
ccw를 사용하면 됩니다.
CCW는 점 그래서 ccw인 거예요. counter clock wise(반시계 방향) 봤을 때 반시계방향으로 놓여 있으면 양수를, 시계방향이면 음수를, 평행하게 놓여있으면 0을 반환합니다.
자 어쨌든 이어서....
일단 점들이 뒤 섞이는 것을 방지하기 위해서 정렬을 해줍니다. 이제 0번점과 1번점을 리스트에 넣고 시작합니다. 만약에 그다음 점이 왼쪽에 있다면, 그 점을 더해줍니다. 이렇게 쭈욱 가다가 만약에 오른쪽에 있다면, 그전에 있던 점은 볼록껍질에 내부에 있는 것이므로 그전에 있던 점을 빼주고 전 점 기준으로 왼쪽에 있을 때까지 반복합니다.
이렇게 하면 볼록 껍질에 있는 점만 리스트에 남 습니다.
아마 이해가 안 가시는 분들이 많을 텐데, 다음 예제 코드를 보고 천천히 익히세요!
지금까지 컨벡스 헐 포스팅이었습니다!
import sys
import math
# 입력을 sys.stdin.readline으로 받기 위해 설정
input = sys.stdin.readline
# ccw 함수: 세 점의 방향을 계산하는 함수
# 양수일 경우 반시계방향, 음수일 경우 시계방향, 0일 경우 일직선
def ccw(p1, p2, p3):
return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])
# 볼록다각형을 구하는 함수
def convex_hull(points):
# 점들을 x, y 좌표 순으로 정렬
points.sort(key=lambda p: (p[0], p[1]))
# 볼록다각형을 구성할 스택
stack = []
# 점들을 하나씩 처리
for p in points:
# 스택에 최소 2개 이상의 점이 있고, 세 점이 시계방향이 아니라면
# 스택에서 마지막 점을 제거 (올바른 볼록다각형을 만들기 위해)
while len(stack) >= 2 and ccw(stack[-2], stack[-1], p) <= 0:
stack.pop()
# 현재 점을 스택에 추가
stack.append(p)
# 볼록다각형을 구성한 점들 반환
return stack
# 점의 개수 입력
n = int(input())
# 각 점의 좌표 입력 (x, y 형태)
points = [tuple(map(int, input().split())) for _ in range(n)]
# 볼록다각형을 구성한 점들 구하기
hull = convex_hull(points)
# 볼록다각형을 구성한 점들의 개수 출력
print(len(hull))
# 볼록다각형을 구성한 점들 출력
for p in hull:
print(p[0], p[1])