2차원 평면상에서 선분 AB와 CD의 정보가 주어질 때, 두 선분의 교차 여부를 빠르게 판단할 수 있는 방법이 있다. 벡터의 외적(벡터곱)을 이용하는 방법이다.


그림 1과 같이 두 선분이 교차하는 경우를 생각해 보자. 벡터 BA를 기준으로 점 C와 점 D가 서로 다른 회전방향에 있으므로, 아래 두 경우는 벡터곱 연산의 결과로 나온 z값의 부호가 다르다.

- 벡터 BA와 벡터 BC를 외적한 결과

- 벡터 BA와 벡터 BD를 외적한 결과


벡터 DC에 대해서도 역시 부호가 다르게 된다.

- 벡터 DC와 벡터 DA를 외적한 결과

- 벡터 DC와 벡터 DB를 외적한 결과 


     

그림 1. 교차하는 두 선분                                  


즉, 벡터곱 연산을 이용하여 한 선분의 벡터를 기준으로, 다른 선분의 두 점들이 같은 회전뱡향에 있는지, 다른 회전방향에 있는지 검사하면 교차 여부를 판단할 수 있는 것이다.
두 선분에 대해 이러한 판단을 수행하여 모두 만족하면 교차하는 것으로 판정한다.


그림 2에서는 벡터 CD에 대해 다른 선분의 두 점(A, B)는 서로 다른 회전방향이지만, 벡터 AB에 대해서는 두 점(C ,D)가 같은 회전방향에 있기 때문에 교차하지 않는 것으로 판정한다.


 

그림 2. 교차하지 않는 두 선분



Javascript로 표현하면 아래와 같이 쓸 수 있다.

    let p1 = line1.p1;

    let p2 = line1.p2;

    let p3 = line2.p1;

    let p4 = line2.p2;


    let sign1 = (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);

    let sign2 = (p2.x-p1.x)*(p4.y-p1.y) - (p4.x-p1.x)*(p2.y-p1.y);


    let sign3 = (p4.x-p3.x)*(p1.y-p3.y) - (p1.x-p3.x)*(p4.y-p3.y);

    let sign4 = (p4.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p4.y-p3.y);


    return sign1*sign2<0 && sign3*sign4<0;




그러나 위 코드에는 문제점이 있는데, 그림 3과 같이 두 선분의 기울기가 같을 때는 교차하지 않는 것으로 판단한다는 것이다. (이런 결과를 의도했다면 문제가 되지 않겠지만..)


그림 3. 두 선분의 기울기가 같고, 교차점이 무수히 많은 경우



그림 3과 같은 경우에도 두 선분이 교차하는 것으로 판정하기 위해, 비교문을 아래와 같이 고치면 또다른 문제가 발생한다. 그림 4와 같이 기울기가 같고 서로 떨어져 있을 때 잘못 판정한다는 것이다.

return sign1*sign2<=0 && sign3*sign4<=0;



그림 4. 교차 여부를 잘못 판정한 경우




두 선분이 완전히 떨어져 있을 경우(더 정확히 말하면, 각각의 선분이 이루는 직사각형 영역이 서로 겹치지 않는 경우)에 false를 리턴하면 이 문제를 해결할 수 있다. 외적 연산에 앞서 사전 영역 검사를 하는 것이다.

아래 코드에서 모든 부호가 0일 때 true를 반환하는 부분을 추가한 이유는, 그림 3과 같이 교차점이 무수히 많은 경우도 교차하는 것으로 판단하기 위해서이다.


    let p1 = line1.p1;

    let p2 = line1.p2;

    let p3 = line2.p1;

    let p4 = line2.p2;


    if(Math.max(p1.x, p2.x) < Math.min(p3.x, p4.x)) return false;

    if(Math.min(p1.x, p2.x) > Math.max(p3.x, p4.x)) return false;

    if(Math.max(p1.y, p2.y) < Math.min(p3.y, p4.y)) return false;

    if(Math.min(p1.y, p2.y) > Math.max(p3.y, p4.y)) return false;


    let sign1 = (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);

    let sign2 = (p2.x-p1.x)*(p4.y-p1.y) - (p4.x-p1.x)*(p2.y-p1.y);


    let sign3 = (p4.x-p3.x)*(p1.y-p3.y) - (p1.x-p3.x)*(p4.y-p3.y);

    let sign4 = (p4.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p4.y-p3.y);


    if(sign1==0 && sign2==0 && sign3==0 && sign4==0) return true;


    return sign1*sign2<=0 && sign3*sign4<=0;



그림 5. 교차 여부를 정상적으로 판정한 경우




경우에 따라서 그림 6과 같이 선분의 끝점이 교차할 때는 교차하지 않는 것으로 판단하는 것이 필요할 때가 있다.

 

그림 6, 7. 두 선분이 교차하는 것으로 판단하는 경우



아래 코드에서와 같이 사전 영역 검사에 동등 조건을 넣어  좀더 엄격하게 바꾸고(그림 6과 관련), 마지막의 리턴 코드에서 동등 조건을 제거한다.(그림 7과 관련)


    let p1 = line1.p1;

    let p2 = line1.p2;

    let p3 = line2.p1;

    let p4 = line2.p2;


    if(Math.max(p1.x, p2.x) <= Math.min(p3.x, p4.x)) return false;

    if(Math.min(p1.x, p2.x) >= Math.max(p3.x, p4.x)) return false;

    if(Math.max(p1.y, p2.y) <= Math.min(p3.y, p4.y)) return false;

    if(Math.min(p1.y, p2.y) >= Math.max(p3.y, p4.y)) return false;


    let sign1 = (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);

    let sign2 = (p2.x-p1.x)*(p4.y-p1.y) - (p4.x-p1.x)*(p2.y-p1.y);


    let sign3 = (p4.x-p3.x)*(p1.y-p3.y) - (p1.x-p3.x)*(p4.y-p3.y);

    let sign4 = (p4.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p4.y-p3.y);


    if(sign1==0 && sign2==0 && sign3==0 && sign4==0) return true;


    return sign1*sign2<0 && sign3*sign4<0; 





결론


만들고자 하는 프로그램에 따라 선분 끝점을 어떻게 판단해야할지가 달라진다. 위 코드를 활용하여 비교문들을 조정하면 선분의 교차 판단을 목적에 맞게 할 수 있을 것이다.



 

소스코드


동작하는 전체 코드는(Javascript)는 아래 github에서 다운로드할 수 있습니다.

https://github.com/tibyte/algorithms/tree/master/line-intersection






+ Recent posts

티스토리툴바