알고리즘 : ConvexHull (Graham's Scan)

2014. 5. 1. 09:24프로그래밍/알고리즘

외곽선 찾기(ConvexHull) 알고리즘


1. 개요

2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 나머지 모든 점을 내부에 포함하는 다각형을 만든다. 이를 볼록 껍질(CONVEX HULL) 이라 한다.

아래 그림은 N=10인 경우의 한 예.


2. 알고리즘 : Graham's Scan 사용

(1) P0을 선택합니다.

  - P0y축 가장 아래에 위치한 점을 선택합니다.

  - 가장 아래 위치한 점이 여러 개 존재 시 x축 가장 좌측을 선택합니다.


(2) P0을 기준으로 모든 점들에 대한 각도를 구한다.


(3) 구한 점들의 각도 중 가장 낮은 각을 가진 점을 순서대로 P1, P2 선택


(4) 다음 점 Pn을 선택하여, 점을 추가 할 것인지 교체 할 것인지 정한다.

  - 이전 두 점에 대해 조건 검색을 하여, 조건에 만족하지 않으면 해당 점을 Pn과 교체하며, 만족하면 Pn을 추가한다.

   - 조건 : 선택된 점[Pn]이 선[Pn-2Pn-1(->)]에서 왼쪽(반시계 방향)에 위치하면 Pn을 추가,

             오른쪽(시계방향)에 위치하면 점[Pn]을 점[Pn-1]과 교체한다.

  * 이 때 선의 방향을 유의하자. 선은 Pn-2 -> Pn-1.




(5) 모든 점에 대한 (4)의 탐색이 끝나면 선택된 점을 연결한다.



3. 소스설명


4. 실행결과


5. 기타

  - MFC GDI를 사용해 표현

  - 점을 원으로 표현하였기 때문에 외곽으로 원의 일부가 삐져나올 수 있으나, 좌표 상으로는 선 내부에 포함됨.

  - 5000개 이상 생성 시 정신건강에 해로움


6. 소스파일 및 실행파일 첨부

HnS17_ConvexHull.zip


  • 프로필사진
    2015.06.04 19:28

    비밀댓글입니다

    • 프로필사진
      hns172015.06.08 20:06 신고

      한 동안 블로그 접속을 하지않아 답이 늦은 점 이해해주세요.
      이해를 돕기위해 그림에서 화살표를 사용해 방향성을 추가해보았습니다.
      p1p2가 정해진 후 p3부터는 ccw 조건에 따라 포인트가 확정되며 선의 방향을 유심히 보시면 이해하기 쉬울거라 생각합니다.
      댓글 감사드리며, 이해하기 어려우시다면 댓글달아주세요.
      열공하세요~

  • 프로필사진
    박작가12015.09.24 08:25 신고

    잘 하시네요. 더불어 각도를 직접 측정하기 보다는 CCW로 판단을하면 더 좋겠네요~

  • 프로필사진
    OnDraw2016.05.26 10:23 신고

    감사합니다.