Elementary Sorts(4) : Convex Hull

Convex hull

• 평면 내의 모든 점을 포함하는 최소한의 다각형을 구하는 문제입니다
• 여기에도 정렬 알고리즘이 사용됩니다.
• 시계 반대방향으로 도는 과정을 반복합니다.

 

Convext hull: mechanical algorithm

• 비유이긴한데.. 잘 와닿지는 않네요..

 

Convex hull applicatoin: motion planning

• 로봇의 이동 알고리즘을 설계할 때 장애물을 피해갈 수 있는 최적의 경로를 선정하는데 활용될 수 있습니다.

 

Convex hull application: farthest pair

 

Convex hull: geometric properties

 

Grahan scan: implementation challenges

• 시작은 y 좌표값이 가장 작은 것을 p로 정하는 것입니다.
  이로부터 시계 반대방향으로 순서대로 값을 지정해줍니다.
• 그리고 각 요소를 포함하는 것이 옳은지 그렇지 않은지를 판단합니다.

 

Implementing ccw

• 시계 반대방향으로 convex hull을 제대로 형성하고 있는지에 대한 설명입니다.
  물론 이 수업이 어떤 시각화와 관련된 내용이 주된 것은 아니라 설명이 디테일하지는 않고, 간단한 알고리즘이 존재한다는 사실 정도만 캐치해도 괜찮을 것 같습니다.

 

Immutable point data type

 

 

출처: Coursera, Algorithms, Part 1, Princeton University