그라함 스캔(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

Trackback :: http://harrys.co.kr/blog/lab/trackback/22

댓글을 달아 주세요

  1. Haroo 2007/04/23 00:34  댓글주소  수정/삭제  댓글쓰기

    이왕 링크를 걸테면 새창으로 띄우도록 부탁.
    뭐, 이쪽에서 shift를 누르면 되지만.. 키보드를 분리했을 땐 안되걸랑.

  2. Haroo 2007/04/23 23:23  댓글주소  수정/삭제  댓글쓰기

    감사해효 ;ㅁ;(?)
    지금 7은하.. 완전 안습.. OTL