'그라함 스캔'에 해당되는 글 1건

  1. 2007/04/16 그라함 스캔(Graham Scan) (3)

그라함 스캔(Graham Scan)

Computer/Algorithms 2007/04/16 01:43
그라함 스캔은 볼록다각형을 구하는 가장 일반적인 방법이다.

  1. 외곽의 점을 하나 잡는다. 이는 반드시 최외곽에 존재해야 하며, 주로 y가 가장 작은 점 등을 선택한다.
  2. 다른 점들을 선택된 점(pivot이라 합니다)을 기준으로 각도가 증가하는 순서로 정렬한다. 이를 다 선으로 이으면 별 모양이 만들어진다.
  3. 다각형을 만들어나간다. 각 점들에 대해 다른 점이 해당 선분의 좌측인지 우측인지를 판단하면서 진행한다.


그라함 스캔 시뮬레이션
http://www.cs.princeton.edu/~ah/alg_anim/version1/GrahamScan.html




2008년 1월 19일 이후 작성된 모든 글에 대해서 퍼가는 것을 금지합니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
Posted by Harry
TAG , ,
Trackback 0 , Comments 3