알고리즘 - CCW (세 점의 방향 판별하기)

CCW 란 Counter Clock Wise 의 준말이다.

Counter Clock Wise 란 반시계 방향을 의미한다.

 

CCW 알고리즘은 세 점의 좌표가 주어졌을 때, 반시계 방향으로 위치하는가를 판별하는 알고리즘이다.

위의 두 그림에서 A->B->C의 방향을 보자.

첫 번째 그림은 반시계 방향으로 세 점이 위치하고 있고, 두 번째 그림은 시계 방향으로 세 점이 위치하고 있다.

 

이렇게, 세 점이 순서대로 주어졌을 때, 반시계 방향으로 위치하는지 시계 방향으로 위치하는지를 판별하는 알고리즘이 CCW이다.

 

 

CCW 알고리즘

---

CCW알고리즘은 기본적으로 벡터의 외적을 이용한 알고리즘이다.

이 알고리즘을 알기 위해선 외적에 대한 이해가 있어야 하며, 왼손 좌표계와 오른손 좌표계에 대한 이해가 있어야 한다.

모른다면, 찾아보고 나서 다시 알고리즘을 보는 것을 추천한다.

 

이 알고리즘은 상술했듯이 벡터의 외적을 기반으로 작동한다.

허나, 벡터의 외적은 해당 좌표계가 오른손 좌표계인지 왼손 좌표계인지에 따라 다른 결과를 나타낸다.

(수치는 같지만, 적용되는 방향이 다르다.)

 

만약 DirectX나 unreal Engine같은 환경에서 이 알고리즘을 사용하겠다면 왼손 좌표계를 기준으로 해야할 것이다.

수학에서 일반적인 좌표계는 오른손 좌표계이기 때문에 해당 게시글에선 오른손 좌표계를 기준으로 설명할 것이다.

 

일반적인 오른손 좌표계는 위와 같이 축이 설정되어 있다.

이 공간 안에, 그림에 보이는 것과 같이 벡터 1과 벡터 2가 존재한다고 해보자.

두 선분의 z값은 0이라고 가정하겠다.

 

이 떄, 두 선분을 외적하면 XY평면과 수직이며, z축과 평행한 벡터가 결과로 나오게 될 것이다.

 

이 때, 벡터 1과 벡터 2의 위치관계를 보자.

그림과 같이 위치한다면, 오른손 법칙에 의해, (벡터 1) X (벡터 2) 의 결과는 z축의 양의 방향으로 뻗어나가는 벡터일 것이다.

 

반면, 이 그림처럼 벡터 1과 벡터 2가 위치한다면, (벡터 1) X (벡터 2)의 결과는 Z축의 음의 방향으로 뻗어나가는 벡터가 될 것이다.

 

즉, 두 벡터의 위치관계에 따라 외적한 벡터의 Z값이 양수인지 음수인지 달라지는 것이다.

 

그럼 다시 이 그림을 보자.

 

세 점이 반시계 방향으로 위치할 때, 점을 제거하고 벡터만을 보게 되면 위와 같이 정리할 수 있다.

 

2차원 평면에 해당 그림과 같이 위치했을 때, 파란색 벡터와 빨간색 벡터를 외적하면?

오른손 법칙에 의해, Z축의 양의 방향으로 뻗어나가는 벡터가 나온다.

 

즉, (파란색 벡터 X 빨간색 벡터) 를 통해 나온 벡터의 Z값이 양수라면 세 점이 반시계 방향으로 위치한다고 생각할 수 있다.

 

이번엔 시계 방향으로 있는 상황을 보자.

그림과 같이 벡터의 관계를 정리할 수 있다.

이 때, 파란색 벡터와 빨간색 벡터를 외적하게 되면, Z축의 음의 방향으로 뻗어나가는 벡터가 결과로 나오게 된다.

 

즉, (파란색 벡터 X 빨간색 벡터) 를 통해 나온 벡터의 Z값이 음수라면 세 점이 시계 방향으로 위치한다고 생각할 수 있다.

 

이와 같이, 세 점의 좌표를 기준으로 벡터를 구한 뒤 벡터를 외적하게 되면 세 점이 시계방향으로 있는지 반시계 방향으로 있는지를 판별할 수 있다.

 

 

백준 17386- 선분 교차 1 (C++) (tistory.com)

백준 17386- 선분 교차 1 (C++)

위의 링크는 이 알고리즘을 적용하여 풀어볼 수 있는 문제이다.

문제를 먼저 풀어보고 나서 게시글을 참고하면 도움이 될 것 같다.