목록2025/07/16 (1)
Elevation
기하 - CCW, 선분 교차, 볼록 껍질
CCW(Counter Clockwise)란 세 점의 진행 방향이 시계 반대 방향인지, 시계 방향인지 판단할 수 있게 해 주는 알고리즘이다.$CCW(A, B, C)$는 세 점을 입력으로 받아 직선 $AB$와 점 $C$의 위치 관계를 판단한다. $C$가 직선 $AB$에 비해 반시계 방향으로 진행한다면 양수를, 시계 방향으로 진행한다면 음수를, 직선 위에 있다면 0을 반환한다. CCW 알고리즘은 벡터의 외적을 활용한다. 두 벡터 $\overrightarrow{AB}$와 $\overrightarrow{AC}$를 외적하면 그 부호는 오른손 법칙에 의해 결정되는 외적의 방향을 의미한다. $\overrightarrow{AB}$에 비해 $\overrightarrow{AC}$가 시계 반대 방향이라면 외적은 2차원 평면을..
ps/기타
2025. 7. 16. 00:40