jundyu 님의 블로그

들어가며볼록 껍질을 구하는 그레이엄 스캔 알고리즘을 알기 위해선 CCW 알고리즘을 먼저 배워야합니다. CCW 알고리즘에 대해 자세히 설명해둔 글이 있으니 아래 링크 참고해주세요. [Algorithm] CCW 알고리즘 with JAVA들어가며최근에 기하와 관련된 문제를 풀며 점들이 이루는 방향성을 판별하는 알고리즘을 배우게 되었습니다. CCW 알고리즘은 세 점이 이루는 방향을 간단한 연산으로 확인할 수 있는 핵심 알고jundyu.tistory.com 볼록 껍질: Convex Hull1. 볼록한 다각형(Convex Polygon) 왼쪽 도형을 바깥에서 바라봤을 때 기준으로 모든 꼭짓점들이 볼록합니다. 하지만 오른쪽 도형은 빨간색으로 표시된 하나의 꼭짓점이 오목한 것을 볼 수 있습니다. 이렇게 모든 꼭짓점..

들어가며최근에 기하와 관련된 문제를 풀며 점들이 이루는 방향성을 판별하는 알고리즘을 배우게 되었습니다. CCW 알고리즘은 세 점이 이루는 방향을 간단한 연산으로 확인할 수 있는 핵심 알고리즘입니다. 이번 글에서는 CCW의 원리와 구현 방법, 그리고 더 나아가 활용방법까지 JAVA 언어와 함께 알아보겠습니다. CCW : Counter Clock Wise좌표평면에 세 개의 점이 주어진 경우 점을 순차적으로 이었을 때 세 점을 이은 선이 시계방향인지 반시계방향인지, 일직선인지 판별하는 알고리즘입니다.1번 이미지부터 순서대로 반시계 방향, 시계 방향, 일직선인 경우입니다. 사람의 눈으로 세 점의 방향 관계를 파악하는 것은 아주 쉽지만 프로그래밍 언어를 통해 세 점의 좌표를 받고 판별하는 로직을 구현하는 것은 ..