[📚정보] 볼록 껍질 알고리즘

[vertex(4321vertex)]

볼록 껍질 알고리즘은 컨벡스 헐 (Convex hull) 알고리즘이라고도 불러요,

볼록 껍질 알고리즘은 특정한 점이 주어졌을때 해당 점들을 가장자리에서 모두 감싸서 포함하는 볼록 껍질을 찾는 알고리즘이에요

그리고 여기서 설명할건 볼록 껍질 알고리즘 중에서 선물포장 알고리즘(Gift wrapping algorithm)이에요

1.선물 포장 알고리즘의 작동방식

위의 그림처럼 특정한 점들이 주어져 있을때, 제일 먼저 그중 y좌표가 제일 작은 점을 찾아야해요, 위의 그림에서 빨강색 점이에요

그리고 이 점은 구하려는 볼록껍질에 확실하게 포함되어 있는 점이에요

그 다음 그렇게 찾은 빨강색 점을 기준으로 제일 +방향의 각도에 있는 점을 찾아야 해요, 즉 빨강색 점들과 다른 나머지 점들 사이의 각도를 구했을때, 그렇게 구한 각도들중 제일 +방향의 각도에 있는 점을 찾아야 해요, 위의 그림에서 파랑색 점이에요

그리고 다시 파랑색 점을 기준으로 동일한 방식으로 제일 + 방향의 각도에 있는 점을 찾아야 해요, 위의 그림에서 초록색 점이에요

그리고 그런식으로 계속해서 제일 +방향의 각도에 있는 점을 찾다보면, 최종적으로 다시 처음의 시작점으로 돌아오게 되요

그리고 그렇게 하면 최종적으로 주어진 점들의 볼록껍질이 완성되는거에요

[링크]

그리고 알고리즘의 코드는 위의 링크에 있어요

[익명(nowhere1201)]

제일 + 방향에 있다는 게 정확히 무슨 뜻임?

[익명(hotkey02)]

코드 보니까 각도로 구하는듯?

[Indie 1(125.132)]

각도? 말하는거 같은데

[익명(hotkey02)]

@ㅇㅇ 현재 기준 방향에서 가장 많이 꺾이는 방향의 점을 들고오는건데 이건 틀린 알고리즘이긴함 어떤 방향에서 현재 점으로 들어왔는지를 기준으로 가장 바깥쪽으로 회전하는 점을 골라야 하는데 저건 외곽을 돈다는 보장이 없어

[주사위열쇠(personal2282)]

그래픽스 수업에서 배웠던 기억이 난다