직선과 직선의 교점 구하기.

두 개의 직선(선분) A와 B가 있을 때, 
    선분 A : A(t) = (1-t)*A1 + t*A2
    선분 B : B(s) = (1-s)*B1 + s*B2
와 같이 표현할 수 있다.
여기서 t와 s값이 0~1 사이에 존재하면 선분을 의미하게 되고 그 범위를 벗어나 무한대가 되면 직선을 의미한다.

두 직선의 교점은 A(t) = B(s) 이므로,
    (1-t)*A1 + t*A2 = (1-s)*B1 + s*B2
와 같이 표현이 된다.

위의 식을 x/y성분으로 구분을 짓는다.
    (1-t)A1.x + tA2.x = (1-s)B1.x + sB2.x
    A1.x - tA1.x + tA2.x = B1.x - sB1.x + sB2.x 
    A1.x + t(A2.x-A1.x) = B1.x + s(B2.x-B1.x)

    (1-t)A1.y + tA2.y = (1-s)B1.y + sB2.y
    A1.y - tA1.y + tA2.y = B1.y - sB1.y + sB2.y
    A1.y + t(A2.y-A1.y) = B1.y + s(B2.y-B1.y)

결국, t와 s에 관련된 2차 방정식을 구하게 되었다.
이 방정식을 이용하여 t와 s의 값을 구하면,(풀이 과정은 생략한다.) 아래와 같이 된다.

    t = (B2.x-B1.x)*(A1.y-B1.y) - (B2.y-B1.y)*(A1.x-B1.x) / (B2.y-B1.y)*(A2.x-A1.x)-(B2.x-B1.x)*(A2.y-A1.y)
    s = (A2.x-A1.x)*(A1.y-B1.y) - (A2.y-A1.y)*(A1.x-B1.x) / (B2.y-B1.y)*(A2.x-A1.x)-(B2.x-B1.x)*(A2.y-A1.y)

위의 식을 보면 t와 s를 구하는 식에서 분모의 값이 일치함을 알 수 있다.
즉, 분모가 0이라면 두 직선의 교점은 존재할 수가 없게 되고, 이는 곧 두 직선이 평행함을 의미한다.
또한, 분모와 분자가 모두 0이라면, 두 직선이 같은 선이라는 것을 의미하게 된다.
마지막으로, 직선끼리의 교점이 아니라 선분끼리의 교점을 구할 경우, t와 s모두가 0~1 사이의 값을 가져야만 한다.

위의 내용을 기반으로 두 선분의 교점을 구하는 코드를 C++로 작성해보자.

BOOL GetCrossPoint( const v2f& A1, const v2f& A2, const v2f& B1, const v2f& B2, v2f* out )
{
	f32 t;
	f32 s; 
	f32 under = (B2.y-B1.y)*(A2.x-A1.x)-(B2.x-B1.x)*(A2.y-A1.y);
	if(under==0) return false;

	f32 _t = (B2.x-B1.x)*(A1.y-B1.y) - (B2.y-B1.y)*(A1.x-B1.x);
	f32 _s = (A2.x-A1.x)*(A1.y-B1.y) - (A2.y-A1.y)*(A1.x-B1.x); 

	t = _t/under;
	s = _s/under; 

	if(t<0.0 || t>1.0 || s<0.0 || s>1.0) return false;
	if(_t==0 && _s==0) return false; 

	out->x = A1.x + t * (A2.x-A1.x);
	out->y = A1.y + t * (A2.y-A1.y);
	return true;
}