Good bye, halcyon days...

Convex Hull

Convex Hull

Convex Hull 또는 Convex Closure는 차원과 좌표를 가지는 공간 상의 특정 지점(Vertex)들을 원소로하는 집합 A 전체를 포함하는 가장 작은 Convex Set를 말한다. Convex Set은 공간 S 내에 포함된 Vertices 간의 연결된 선분이 공간 S에 완벽히 포함되는 공간을 말한다. 아래 그림의 오른쪽의 회색 공간이 Convex Set을 만족한다.

Convex Set: 오른쪽이 Convex Set을 만족함

Convex Hull은 X, Y만 가지는 2차원에서는 집합 A의 원소들 전체 또는 일부를 점으로하는 다각형이 된다. Convex Hull을 계산하는 알려진 Algorithm이 여럿 존재하여, 간단히 Link를 첨부하는 것으로 대신한다.

  1. https://en.wikipedia.org/wiki/Convex_hull_algorithms#Algorithms
  2. https://www.cs.umd.edu/class/spring2012/cmsc754/Lects/cmsc754-lects.pdf

.

Convex Hull은 주어진 Vertices에 대해 외각선을 계산하는 것이므로 필요면적 계산, 충돌 검사 등에 활용될 수 있다.



e.riny

e.riny

I know what I know nothing.