위키득계정 ↗
기술

CCW 판정

CCW 판정기술
영어
Counterclockwise orientation test
입력
순서가 있는 세 점 A와 B와 C
판정 값
(bₓ − aₓ)(cᵧ − aᵧ) − (bᵧ − aᵧ)(cₓ − aₓ)
일반 좌표의 양수
반시계 방향
CCW 판정은 평면의 세 점을 순서대로 보았을 때 반시계 방향으로 꺾이는지, 시계 방향인지, 한 직선에 놓이는지를 결정하는 계산이다. 두 벡터로 만든 2행 2열 행렬식의 부호를 사용하며 볼록 껍질과 선분 교차 알고리즘의 기본 연산이다.

부호가 뜻하는 방향

x가 오른쪽으로, y가 위쪽으로 증가하는 좌표를 사용하자. 판정식 값이 양수이면 A에서 B를 거쳐 C로 가는 방향은 반시계이고 음수이면 시계다. 0이면 세 점은 공선이다. 세 점의 순서를 바꾸면 부호가 달라질 수 있다.

직접 계산하는 예

A = (0, 0), B = (3, 0), C = (1, 2)를 넣으면 값은 3×2 − 0×1 = 6이다. 따라서 반시계 방향이다. B와 C의 순서를 바꾸면 값은 −6이 된다. 판정값의 절댓값을 2로 나누면 세 점이 만드는 삼각형의 넓이를 얻는다.

공선이면 선분 위에 있는가

판정값이 0이라는 사실은 C가 A와 B를 잇는 선분 내부에 있다는 뜻이 아니다. A = (0, 0), B = (1, 0), C = (3, 0)도 값이 0이지만 C는 선분 바깥에 있다. 선분 위인지 판정하려면 좌표 범위 등 추가 조건을 함께 확인해야 한다.

좌표계와 수치 오차

화면처럼 y좌표가 아래쪽으로 증가하는 체계에서는 시각적인 회전 방향과 부호의 관계가 반대가 된다. 정수 좌표도 중간 곱이 자료형 범위를 넘을 수 있으며 부동소수점에서는 거의 공선인 경우 오차가 중요하다. 좌표 범위와 연산 방식에 맞는 판정이 필요하다.

관련 문서

그레이엄 스캔 / 자비스 행진 / 볼록 껍질 / 행렬식 / 삼각형 / 직교 좌표계 / 부동소수점