heehcs   6년 전

아래와 같이 구현하였는데요, 무언가 예외케이스가 존재하는듯하여 문의드립니다.

1. x축 점 기준 정렬
2. i번째 점의 y값에 기반하여 껍질 업데이트
3. 왼쪽으로 돌면서 ccw가 양수가 나올때까지 업데이트
4. 오른쪽으로 돌면서 ccw 가 음수가 나올때까지 업데이트
5. Graham Scan이 완료된후,  볼록껍질 점들을 순회하며 일직선상에 세점이 위치하는 경우에는 
    카운트 하지 않음으로 예외처리

감사합니다.

ehddml3   6년 전

코드는 안봤지만, 설명으로는 sort 기준부터 제가 아는 graham scan이랑은 다른 것 같네요.. y좌표가 가장 작으면서 x가 가장 작은 점을 기준으로 모든 점들을 x축으로 부터의 각도 순으로 정렬합니다 https://en.wikipedia.org/wiki/... 를 한번 봐보시는게 어떨까요

heehcs   6년 전

방식 자체를 다르게 푸니 풀리네요. 감사합니다. 

댓글을 작성하려면 로그인해야 합니다.