두 선의 교차점 구하기

참고 자료 : http://mathworld.wolfram.com/Line-LineIntersection.html

 

이 글은 두 선분의 교차점을 구하는 알고리즘이 작업에 필요해서 작성해둔 글이다. 참고로, 예전에 두선분의 교차점을 구하는 것 자체가 쉬울 것으로 생각하고 흔히 생각하는 기울기, y 절편을 이용하여 접근하려고 하였다. 이는 상당히 비효율적 방법이였고 조금 더 효율적인 방법으로 접근하였다.

먼저 직선의 방정식으로써, 기울기와 절편으로 나타내지 말고, t 매개변수를 이용해 나타내면 다음과 같다.

P1과 P2는 직선의 시작점과 끝점을 나타내며, t의 범위는 0에서 1까지이다. (P1, P2에서 1, 2는 아래첨자로 생각하기 바란다)

선의 식을 알았으니, 이제 두선의 교점을 구해보는 것으로 응용해보자. 먼저 아래 그림을 보자.

Line1은 P1과 P2로 이루어져 있으며, Line2는 P3와 P4로 이루어져 있다. 두개의 라인을 식으로 표현해보면 다음과 같다.

이미 알겠지만, t와 s는 0에서 1부터의 값이며, 두선의 교점은 두선의 공통된 값이므로 P(t)와 P(s)는 같으므로 위의 2개의 식은 아래의 1개의 식으로 나타낼 수 있다.

다시 위의 식을 x, y로 분리해보면 아래와 같은 두개의 식들로 분리된다.

위의 식을 t와 s에 대해서 정리를 해보면 다음과 같다.

즉, 위의 t와 s는 두선이 서로 만날때의 값이므로, 최종적으로 두선의 교점은 다음과 같이 나타낼 수 있다.

위의 x, y가 우리가 구하고자하는 두 직선의 교점이다.

마지막으로 t와 s에 대해 정리해 보도록 하자.

s와 t의 값이 0과 1 사이를 벗어나는 경우, 두 선은 교차하지 않는다고 판정해야 한다. 그리고 s와 t를 구하는 공식에서 분모가 0인 경우 두 선은 평행하다는 의미이므로 교점은 존재하지 않다. 분모와 분자 모두 0인 경우 두 선은 동일한 선이다.

아래의 코드는 위의 설명을 토대로 작성하였다.

 

[code cpp]
bool GetIntersectPoint(const POINT& AP1, const POINT& AP2,
                       const POINT& BP1, const POINT& BP2, POINT* IP)
{
    double t;
    double s;
    double under = (BP2.y-BP1.y)*(AP2.x-AP1.x)-(BP2.x-BP1.x)*(AP2.y-AP1.y);
    if(under==0) return false;

    double _t = (BP2.x-BP1.x)*(AP1.y-BP1.y) - (BP2.y-BP1.y)*(AP1.x-BP1.x);
    double _s = (AP2.x-AP1.x)*(AP1.y-BP1.y) - (AP2.y-AP1.y)*(AP1.x-BP1.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;

    IP->x = AP1.x + t * (double)(AP2.x-AP1.x);
    IP->y = AP1.y + t * (double)(AP2.y-AP1.y);
    return true;
}[/code]

출처 : http://www.gisdeveloper.co.kr/15