[알고리즘] CCW(Counter-Clock-Wise)
CCW(Counter Clock Wise) 알고리즘은 세 개의 점을 이은 직선의 방향을 알고자 할 때 유용한 알고리즘이다.기하 알고리즘의 기초라고 볼 수 있는데, 2차원 평면 위에 놓인 3개의 점이 어떤 방향성이 있는지 알려주고 이를 통해 이후 선분 교차 판정이나 볼록 껍질 등에 활용할 수 있다. 이 알고리즘은 3가지 경우의 수를 나타낸다.반시계 -> 왼쪽으로 도는지시계 -> 오른쪽으로 도는지일직선 CCW를 이해하기 위한 사전 지식에는 벡터와 외적이 있다. 벡터는 두 점을 잇는 화살표이다.어디에서 시작해 어디로 가는지, "방향"과 "크기"를 가지고 있다.A라는 점에서 B라는 점으로 가는 화살표가 있다면 이는 \(\overrightarrow{AB}\) 로 표현될 수 있다. 외적은 두 점 A,B가 있을 때..
Algorithm
2024. 10. 11. 10:12
