두 선의 교차점 구하기

http://www.gisdeveloper.co.kr/?p=89

두 선의 교차점 구하기 – GIS Developer

퍼온 글입니다.

이 글은 두 선분의 교차점을 구하는 알고리즘이 작업에 필요해서 작성해둔 글이다. 참고로, 예전에 두선분의 교차점을 구하는 것 자체가 쉬울 것으로 생각하고 흔히 생각하는 기울기, 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인 경우 두 선은 동일한 선이다.

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

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;
}

댓글의 내용 정리.
위의 함수는 교차점을 구하는 함수인지라.. 교차점이 무한 개인 경우는 교차점 없는 것으로 판단하기 때문에 false를 리턴합니다.

선분의 정의 시에 2개의 좌표를 통해 정의되는데 이 2개의 좌표계 선분의 시작점과 끝점입니다.
시작점은 t가 0일때, 끝점은 t=1일때입니다.결론을 통해 t의 범위를 유추할수있는 방법이고..
선분을 구성하는 t의 범위 제한은 사실 없습니다.

under가 0일 때 동일한 선인지 확인하는 코드 입니다.
p1 p2를 지나는 선과 p3가 얼마나 떨어져 있는지 확인하려면 크로스 프로덕을 하면 알 수 있습니다.
참고로 코드를 추가 합니다.

if (under == 0)
{
PtVector3 v1, v2, c;
v1 = AP2 – AP1;
v2 = BP1 – AP1;
c = v1.Cross(v2);
if (c.DoubleLength() == 0)
{
if (v1.Dot(v2) > 0)
*IP = BP1;
else
*IP = AP1;
return true;
}

return false;
}

한 직선에 t 라는 점이 있다고 가정해서 나온 내분점 공식 이네요.

다만, 수학적 증명에 일부 아래첨자가 잘못된것 같은데 확인 부탁드리겠습니다.

*** 수정사항 1 => P(t) = P(s) 관계로부터 교차점을 기술하는 부분
(본문 내용) : (1-t)P1+tP2 = (1-s)P1 + sP2
(수정) : (1-t)P1+tP2 = (1-s)P3 + sP4

*** 수정사항 2 => 최종적으로 두선의 교점을 구하는 부분
(본문 내용) : x = x1 + s(x2 – x1)
y = y1 + s(y2 – y1)
(수정) : x = x1 + t(x2 – x1)
y = y1 + t(y2 – y1)

: Code에서는 x,y 좌표를 구할때, (x1,y1),(x2,y2),t를 이용해서 구하고 있어,
오류는 없는것 같습니다.
단순히, 수학증명을 써주실때 아래첨자를 잘못 쓰신거 같아요.