이번에는 3개의 점이 이루는 방향이 시계방향인지 반시계방향인지를 알아보자. (2차원 평면임을 가정한다.)
이것은 1개의 직선에 대해 1개의 점이 직선의 오른쪽에 위치하는지 또는 왼쪽에 위치하는지를 알아보는 것과 같은 이치이다.
즉, 3개의 점은 직선의 시작점, 직선의 끝점, 직선과의 관계를 알고자하는 점이 된다.
그래서 이 3개의 점이 시계방향(ClockWise)이면 직선의 오른쪽에 있는 것이고, 반시계방향(CounterClockWise)이면 직선의 왼쪽에 있는 것이 된다.
그럼 직선에 대한 점의 위치 또는 3개의 점이 이루는 방향은 어떻게 구하는가?
우선 직선에 수직인 수선(방향벡터)을 구해야 한다.
수선은 기울기를 이용하는 방법 등 여러가지 방법으로 구할 수 있지만,
여기서는 간단하게 직선과 (2차원이지만 가상으로 3차원이라고 가정하여) Z축(0,0,1)과의 외적으로 구하도록 한다.
직선의 시작점을 start, 끝점을 end라고 하고, 수선을 NL이라고 하면,
NL.x = (end.y-start.y)*1 - (0)*0 = end.y-start.y
NL.y = (0)*0 - (end.x-start.x)*1 = start.x-end.x
위와 같이 구할 수가 있다.
이제 직선의 시작점(start)과 관계를 알고자하는 점(p)을 잇는 벡터(SP)를 구하고,
SP.x = p.x - start.x
SP.y = p.y - start.y
위에서 구한 수선(NL)과의 내적을 이용항 방향을 구하면 된다.
내적이란 2개의 벡터의 사이각이 0~89도이면 양수, 직교하면 0, 91~180도이면 음수를 나타내므로,
수선(NL)과 벡터 SP와의 내적이 0~89도이면 직선의 오른쪽, 직교하면 직선위의 점, 91~180도이면 직선의 왼쪽이 된다.
위의 과정을 코드로 표현해보자.
편의상 세점을 p1, p2, p3로 표현하겠다.
// 시계방향.
bool isPointCW(const POINT& P1, const POINT& P2, const POINT& P3) const
{
// Is the order of (P1->P2->P3) Clock Wise?
// . P1->P2벡터에 CW방향으로 수직인 벡터 NP1P2를 구한다.
// NP1P2는 P1->P2벡터(P2.x-P1.x, P2.y-P1.y,0)와 Z축(0,0,1)을 외적하면 구할 수 있다.
// NP1P2.x = (P2.y-P1.y)*1 - (0)*0 = P2.y-P1.y
// NP1P2.y = (0)*0 - (P2.x-P1.x)*1 = P1.x-P2.x
// . P1->P3 벡터 P1P3를 구한다.
// P1P3.x = P3.x-P1.x
// P1P3.y = P3.y-P1.y
// . NP1P2벡터와 P1P3벡터를 내적하여 그 값이 0이상이면 CW 아니면 CCW이다.
// NP1P2 (dot) P1P3 = (P2.y-P1.y)(P3.x-P1.x) + (P1.x-P2.x)(P3.y-P1.y)
// = P2.y*P3.x - P2.y*P1.x - P1.y*P3.x + P1.y*P1.x + P1.x*P3.y - P1.x*P1.y - P2.x*P3.y + P2.x*P1.y
// = P2.y*P3.x - P2.y*P1.x - P1.y*P3.x (소거) + P1.x*P3.y (소거) - P2.x*P3.y + P2.x*P1.y
// = P2.y*P3.x + P1.x*P3.y + P2.x*P1.y - P2.y*P1.x - P1.y*P3.x - P2.x*P3.y
// = P1.y*(P2.x-P3.x) + P2.y*(P3.x-P1.x) + P3.y*(P1.x-P2.x)
return P1.y*(P2.x-P3.x) + P2.y*(P3.x-P1.x) + P3.y*(P1.x-P2.x) > 0;
}
// 반시계 방향.
bool isPointCCW(const POINT& P1, const POINT& P2, const POINT& P3) const
{
return P1.y*(P2.x-P3.x) + P2.y*(P3.x-P1.x) + P3.y*(P1.x-P2.x) < 0;
}