기하 알고리즘 - CCW편

기하 알고리즘 CCW 설명글입니다.

CCW 위주로 기하 알고리즘에 대해서 설명하겠습니다.
그 전에 기초지식부터 확인합시다.
“기하”란 공간에 있는 점, 선, 면, 도형 등의 모양, 크기, 상대적인 위치, 성질 등을 연구하는 수학의 한 갈래이다.
알고리즘에서 일반적으로 다루는 기하요소는 2차원 평면 위에서 점, 선, 면 형태로 표현된다.
스칼라: 크기만을 가지는 물리량 (ex: 속력, 길이 등)
벡터: 크기와 방향을 가지는 물리량 (ex: 속도, 힘 등)
벡터 a와 벡터 b가 이루는 각을 세타라 하고 벡터 a와 벡터 b의 내적과 외적을 구해보자.
벡터의 내적(스칼라곱): a벡터의 크기 X b벡터의 크기 X cos세타 = ax X bx + ay X by
벡터의 외적: 두 벡터가 이루는 사각형의 넓이와 같다. a벡터의 크기 X b벡터의 크기 X sin세타
※ 벡터의 크기란 두 점 사이의 거리를 말한다. 내적과 외적을 이용하면 세타의 크기를 유추할 수 있겠네요.

드디어 CCW를 시작합니다.
CCW: 벡터의 외적을 이용하여 평면상에 세 점이 있을 때 점들의 위치관계를 판단할 수 있는 알고리즘.
회전방향이 반시계인 경우 양수, 시계방향인 경우 음수, 일직선인 경우 0 이 결과로 나온다.
CCW(ax,ay,bx,by,cx,cy) = (axby+bxcy+cxay) - (aybx+bycx+cyax)

CCW를 이용하면 선분 교차 판단과 다각형 면적 구하기를 할 수 있습니다!!
선분 교차 판단: CCW를 이용하면 됩니다. 벡터 AB와 벡터 CD가 교차하는지 판단하는 것을 생각해보자면
벡터 AB에 대해서 점 C와 점 D가 반대 방향에 있어야 하고 벡터 CD에 대해서 점 A와 점 B가 반대 방향에 있어야 합니다.
한쪽 점이 벡터에 걸쳐있어도 교차한다고 말할 수도 있습니다. 그때는 CCW가 0이 나올 수 있겠네요.
(CCW(A,B,C) * CCW(A,B,D) <= 0 && CCW(C,D,A) * CCW(C,D,B) <= 0)
CCW를 4번하면 간단히 구할 수 있겠네요.
하지만… 이렇게 간단히 풀릴 기하가 아닙니다.
두 선분이 평행할 때 역시 CCW가 0이 나올 수도 있기때문에 이 부분을 예외처리를 해주셔야합니다…
두 벡터가 평행할 때 겹치는 부분이 있는지 판단하면 되겠네요.

다각형 면적 구하기: 벡터의 외적이 두 벡터가 이루는 사각형의 넓이라는 사실을 위에서 배웠다.
하나의 기준점과 다른 두 개의 점의 벡터의 외적(CCW)를 이용하면 삼각형의 넓이(CCW/2)를 알 수 있다.
모든 삼각형의 넓이를 더하면 다각형의 면적을 알 수 있다.
하지만 점의 위치에 따라서 값이 음수일수도 양수일수도 있기때문에 절대값을 씌워주셔야합니다.
만약 다각형이 오목하더라도 당황하지마시고 그대로 연산하시면 됩니다.
오목한 부분의 삼각형 부분은 기존의 다각형과 반대방향으로 점이 위치하기때문에 알아서 값이 빠지게 됩니다.

두 선분의 최단거리 구하는 법: 두 벡터가 교차한다면(선분교차판단) 최단거리는 0일테고 그렇지않다면 거리를 구해줘야한다.
벡터 AB와 벡터 CD가 있다면 당연히 점 A와 점 C, 점 B와 점 C, 점 A와 점 D, 점 B와 점 D는 최단거리의 후보일 것이다.
또 벡터 AB와 점 C, 벡터 AB와 점 D, 벡터 CD와 점 A, 벡터 CD와 점 B가 수선의 발을 내릴 수 있다면 그것 역시 최단거리 후보일 것이다.
점 사이의 거리정도는 쉽게 구할 수 있지만 수선의 발을 내릴 수 있는지는 어떻게 알까?
벡터 AB와 점 C가 있다고 할 때 두 선분과 점이 삼각형을 이룬다고하면 예각삼각형이거나 직각삼각형이라면 수선의 발을 내릴 수 있을 것이다.
예각인지 직각인지 어떻게 아냐고? 드디어 벡터의 내적을 사용해보자.
벡터의 크기는 항상 양수일테니 내적의 값이 0이상이라면 세타는 90도 이하이지 않을까?(코사인세타 그래프를 생각해보자.)
수선의 발의 길이는? CCW(A,B,C)를 선분 AB의 길이로 나누면 구하면 나온다.