그레이엄 스캔 - 위키백과, 우리 모두의 백과사전 그레이엄 스캔 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 2차원 볼록 껍질을 찾는 그레이엄 스캔의 예시 그레이엄의 스캔 ( Graham Scan ) 은 평면상에서 유한한 점들의 볼록 껍질을 찾는 방법으로, 시간 복잡도는 O ( n log n ) 이다. 이것의 이름은 로널드 그레이엄이 1972년 원시 알고리즘을 출판한 뒤에 붙여졌다. 이 알고리즘은 볼록껍질의 모든 정점들을 테두리를 따라 찾는다. 그이 알고리즘은 경계의 오목성을 효율적으로 감지하고 제거하기 위해 스택을 사용한다. 목차 1 알고리즘 2 시간 복잡도 3 의사코드 4 내용주 5 숫자의 견고성 6 참조 7 각주 알고리즘 [ 편집 ] 위에서 볼 수 있듯이 PAB와 ABC는 반시계 방향이지만, BCD는 그렇지 않다. 알고리즘은 이러한 상황을 감지하고 반시계 방향이 될 때 까지 이전에 고른 부분을 무시한다. ( 위 그림에서 ABD ) 첫 번째 단계에서 알고리즘은 y좌표가 가장 낮은 점을 찾는다. 만약 y좌표가 가장 낮은 점이 하나보다 많을 경우, 그 중에서 x좌표가 가장 낮은 점을 고른다. 이 점을 P 라고 하자. 이 단계는 입력
만약 결과가 양수이면 세 점들은 " 좌회전 " 또는 반시계 방향을 이루고 있고, 음수인 경우 " 우회전 " 또는 ( 반시계 방향으로 번호매겨진 점들에 대해 ) 시계 방향을 이루고 있는 것이다. 이 과정은 시작된 정점을 반환하고, 시작된 정점에서의 스택은 반시계 방향 순서로 볼록 껍질을 이루는 점들을 포함한 채로 알고리즘이 종료된다. 시간 복잡도 [ 편집 ] 점들을 정렬하는 시간 복잡도는 O ( n log n ) 이다. 하는 동안 보일 수 있는 시간 복잡도의 루프 O ( n2 ) 때문에 각각에 대해 점을 확인하는 경우 이전의 임의의 점 " 우회전 ", 실제로는 O ( n ) 기 때문에, 각 지점에서 고려 대부분이 두 번에서 어떤 의미가 있습니다. 각 지점은 한 번만 나타날 수 있습으로점 " 좌회전 " ( 기 때문에 알고리즘의 발전 다음점 후에는 것 ), 로점 에서 " 를 우회전 " ( 기 때문점 이 제거됩니다. ) 전반적인 총 시간 복잡도는 O ( n log n ) 인데, 점들을 정렬하는 시간이 볼록 껍질을 계산하는 시간을 지배하게 된다. 의사코드 [ 편집 ] 첫째, 정의 # ccw > 0이면 세 점은 반시계 방향이고, 시계방향이면
ack push points [ 2 ] to stack for i = 3 to N : while ccw ( next - to - top ( stack ) ( stack ), top ( stack ), points [ i ] ) < = 0 : pop stack push points [ i ] to stack end 여기에, next - to - top 함수를 반환하는 항목이 하나의 항목 아래 최고의 스택, 변경하지 않고 쌓고, 마찬가지로, 가 반환하기 위한 최상위 요소입니다. 이 의사코드는 Introduction to Algorithm ( 책 ) 으로부터 가져왔다. 내용주 [ 편집 ] 이 문단은 기계 번역에 의해 작성되었을 수 있습니다. 한국어 어법에 알맞게 다듬어 주세요. ( 이 틀은 2018년 10월 23일에 붙었습니다. ) 동일한 기본적인 아이디어도 작동하는 경우 입력이 정렬 x 좌표 대의 각도와 선체에서 계산한 두 가지 단계를 생산하는 상단 및 하단 부분의 헐 각각합니다. 이 수정되었에 의해 고안 A. M. 앤드류 고 알려져 있으로 앤드류 모노톤 체인 알고리즘이 있습니다. 그것은 동일한 기본적인 속성으로 그레이엄의 검사입니다. 숫자의 견고성 [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 참조 [ 편집 ] 이 문단은
표가 가장 낮은 점이 하나보다 많을 경우, 그 중에서 x좌표가 가장 낮은 점을 고른다. 이 점을 P 라고 하자. 이 단계는 입력된 점의 개수를 n이라고 할 때 O ( n ) 에 수행된다. 다음으로, 점들의 집합은 점 P로부터 x축에 대해 각도가 증가하는 순으로 정렬된다. 모든 일반적인 목적의 정렬 알고리즘은 이 과정에 적절하다. 예를 들어 힙 정렬 ( O ( n log n ) ( n log n ) ) 이 사용될 수 있다. 각도 순으로 정렬할 때 각을 계산할 필요는 없다. 구간 스칼라곱을 이용하여 쉽게 계산될 수 있는 코사인이나, P에서 점까지의 직선의 기울기를 사용할 수도 있다. 만약 숫자의 정밀도가 중요할 때, 정렬 알고리즘에 사용되는 비교 함수는 외적의 부호를 통해 상대각 ( 좌회전, 우회전 ) 을 알 수 있다. 알고리즘은 정렬된 배열의 각 점들에 대해 순차적으로 처리한다. 각 점에 대하여, 점에서, 그것은 첫 번째는지 여부를 결정에서 여행은 두 가지 포인트 바로 앞에 이점을 구성하기 왼쪽이나 오른쪽 턴다. 는 경우 오른쪽으로, 두 번째 마지막 포인트는 일부의 convex hull, 거짓말'내부 '. 동 결정은 다음에
록 껍질을 계산하는 시간을 지배하게 된다. 의사코드 [ 편집 ] 첫째, 정의 # ccw > 0이면 세 점은 반시계 방향이고, 시계방향이면 # ccw < 0이다. 그리고 만약 ccw = 0 이면 일직선 상에 있는 것인데, 왜냐하면 ccw는 # p1, p2 그리고 p3로 이루어진 부호가 붙은 삼각형 넓이의 두배를 돌려주기 때문이다. function ccw ( p1, p2, p3 ) : return ( p2. x - p1. x ) * ( p3. y - p1. y ) - ( p2. y - p1. y ) * ( p3. x - p1. x ) 그 결과를 points배열에 저장하도록 하자. let N be 점의 개수 let points [ N ] be 점들의 배열 points [ 0 ] 을 y좌표가 제일 낮은 점 과 바꾼다. points [ 0 ] 의 점들을 극각도 순으로 정렬한다. let stack = NULL push points [ 0 ] to stack push points [ 1 ] to stack push points [ 2 ] to stack for i = 3 to N : while ccw ( next - to - top ( stack ) ( stack )
허락 3. 0에 따라 사용할 수 있으며, 추가적인 조건이 적용될 수 있습니다. 자세한 내용은 이용 약관을 참고하십시오. [UNK] 미국 및 다른 국가에 등록되어 있는 Wikimedia Foundation, Inc. 소유의 등록 상표입니다. 개인정보 정책 위키백과 소개 면책 조항 개발자 쿠키 정책 모바일 보기
에 이점을 구성하기 왼쪽이나 오른쪽 턴다. 는 경우 오른쪽으로, 두 번째 마지막 포인트는 일부의 convex hull, 거짓말'내부 '. 동 결정은 다음에 대한 설정의 최신 지점과 두 개의 포인트는 바로 앞에 지점을 발견해 내부에 있던 선체, 그리고 반복될 때까지 " 좌회전 " 설정은 발생되는 시점에서 알고리즘으로 이동한 다음 포인트에서 설정 포인트의 정렬된 배열이 없다는 점을 제외하고는 점이 발견되었을 수도 대체할 필요가 없습니다 이러한 점을 고려 하시니다. ( 면 모든 단계에서 세 개의 포인트는 선적은, 하나를 선택할 수 있습니다 중 하나를 버리거나 그것을 보고, 이후에 일부 응용 프로그램은 그것을 찾기 위해 필요한 모든 지점에서의 경계 convex hull. ) 다시 말해서, 세 점이 " 좌회전 " 혹은 " 우회전 " 을 구성하는지여부를 여부를 결정하는 데에는 두 선분의 실제 각을 계산할 필요는 없으며, 사실 간단한 산수를 통해 구할 수 있다. 세 개의 점, 그리고 두 개 벡터 와. 만약 결과가 0이면 점들은 일직선 상에 있느 것이다. 만약 결과가 양수이면 세 점들은 " 좌회전 " 또는 반시계 방향을 이루고 있고, 음수인 경우 " 우회전 " 또는 ( 반시계 방향으로 번호매겨진
한 기본적인 속성으로 그레이엄의 검사입니다. 숫자의 견고성 [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 참조 [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 각주 [ 편집 ] 원본 주소 " " 분류 : 알고리즘 분석숨은 분류 : 기계 번역 의심 문서 / 2018년 10월모든 기계 번역 의심 문서기계 번역 의심 문서 - 문단빈 문단이 포함된 문서 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 [UNK] 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 [UNK] 올리기특수 문서 목록고유 링크문서 정보위키데이터 항목이 문서 인용하기 인쇄 / 내보내기 책 만들기PDF로 다운로드인쇄용 판 다른 언어 [UNK] / [UNK] 中 文 링크 편집 이 문서는 2019년 6월 23일 ( 일 ) 23 : 19에 마지막으로 편집되었습니다. 모든 문서는 크리에이티브 커먼즈 저작자표시 - 동일조건변경허락 3. 0에 따라 사용할 수 있으며, 추가적인 조건이 적용될 수 있습니다. 자세한 내용은 이용 약관을 참고하십시오. [UNK] 미국 및 다른 국가
그레이엄의 스캔(Graham Scan)은 평면상에서 유한한 점들의 볼록 껍질을 찾는 방법으로, 시간 복잡도는 O(n log n)이다. 이것의 이름은 로널드 그레이엄이 1972년 원시 알고리즘을 출판한 뒤에 붙여졌다. 이 알고리즘은 볼록껍질의 모든 정점들을 테두리를 따라 찾는다. 그이 알고리즘은 경계의 오목성을 효율적으로 감지하고 제거하기 위해 스택을 사용한다.