Algorithm

CCW 알고리즘 (세 점의 방향성, 선분 교차 판별)

CCW 알고리즘은 두 선분의 교차점을 판별할 때 사용할 수 있습니다. 세 점의 방향성을 판별하여 위 그림과 같이 세 점이 있을 때 점 3개를 이은 선분이 가능한 방향성은 반시계 방향, 시계 방향, 일직선 세가지가 있습니다. P1(x1, y1)을 검정색, P2(x2, y2)를 초록색, P3(x3, y3)로 나타내었을 때 S = (x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1) 공식에 따라 방향성을 판별할 수 있습니다. S > 0 : 시계방향 S = 0 : 일직선 S < 0 : 반시계방향 A 시작점을 기준으로 공식을 다시 보시면 이해가 더 빠릅니다 또한 CCW 알고리즘을 활용해 선분교차판별이 가능합니다. 옆의 그림에서 A, B 나 C, D를 기준으로 부호가 반대가 반대가 될 때 CCW(..