[알고리즘] 선분 교차 판정
선분 교차 판정은 CCW를 활용하여 두 선분이 교차하는지를 판단하는 테크닉이다. https://baehoon.tistory.com/96 CCW를 간단히 설명하면, 세 점 A, B, C가 주어지면 벡터와 외적을 이용해 A -> B -> C로 가는 방향이 일직선인지 반시계 방향인지 시계 방향인지 세 가지 경우의 수로 나누는 알고리즘이다. CCW의 반환값은 다음과 같이 도출될 수 있었다. $$ CCW=(x2-x1)(y3-y1)-(y2-y1)(x3-x1) $$\( CCW 세 점의 진행 방향이 시계 방향이다. \( CCW>0 \) => 세 점의 진행 방향이 시계 방향이다. \( CCW=0 \) => 세 점의 진행 방향이 시계 방향이다. 코드는 다음과 같다. int ccw..
[알고리즘] CCW(Counter-Clock-Wise)
CCW(Counter Clock Wise) 알고리즘은 세 개의 점을 이은 직선의 방향을 알고자 할 때 유용한 알고리즘이다.기하 알고리즘의 기초라고 볼 수 있는데, 2차원 평면 위에 놓인 3개의 점이 어떤 방향성이 있는지 알려주고 이를 통해 이후 선분 교차 판정이나 볼록 껍질 등에 활용할 수 있다. 이 알고리즘은 3가지 경우의 수를 나타낸다.반시계 -> 왼쪽으로 도는지시계 -> 오른쪽으로 도는지일직선 CCW를 이해하기 위한 사전 지식에는 벡터와 외적이 있다. 벡터는 두 점을 잇는 화살표이다.어디에서 시작해 어디로 가는지, "방향"과 "크기"를 가지고 있다.A라는 점에서 B라는 점으로 가는 화살표가 있다면 이는 \(\overrightarrow{AB}\) 로 표현될 수 있다. 외적은 두 점 A,B가 있을 때..
