기하 - 기하 알아보기

기하 알고리즘은 점, 선, 다각형, 원과 같이 각종 기하학적 도형을 다루는 알고리즘입니다.

코딩 테스트에서 기하 알고리즘은 모두 CCW라는 기하학적 성질을 이용해 풀 수 있습니다.

 

기하의 핵심 이론

CCW는 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘입니다.

세 점을 A(X1, Y1), B(X2, Y2), C(X3, Y3)라고 가정했을 때 CCW 공식은 다음과 같습니다.

 

CCW 공식

CCW = (X1Y2 + X2Y3 + X3Y1) - (X2Y1 + X3Y2 + X1Y3)

 

• CCW 결과 < 0: 시계 방향
• CCW 결과 == 0: 일직선
• CCW 결과 > 0: 반시계 방향
• |CCW 결과|: 세 점으로 이루어진 두 백터의 외적값
• |CCW 결과| / 2: 세 점으로 이루어진 삼각형의 넓이