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






이전글 : 유클리드 호제법(http://www.tibyte.kr/224)



이진 최대공약수 알고리즘(binary GCD algorithm은 스테인 알고리즘(Stein's algorithm)이라고도 하며 비트연산을 이용하여 컴퓨터에서 최대공약수를 (나머지연산을 사용하는 유클리드 알고리즘보다) 빠르게 구할 수 있는 알고리즘이다.


이 알고리즘으로 36과 24의 최대공약수를 구하는 예시를 보면 다음과 같다.

36 → 18 →9 →9 →6 →3 →3 

24 → 12 →6 →3 →3 →3 →0


여기서 이런 규칙을 볼 수 있다.

- 두 수가 짝수일 때는 2로 나눈다.

- 한 수만 짝수일 때는 그 수를 2로 나눈다.

- 두 수가 홀수일 때는 큰 수에서 작은 수를 뺀다.

- 0이 되는 수가 있으면 종료한다.


여기서 최대공약수를 얻는 방법은

두 수가 짝수여서 2로 나누는 계산을 할 때마다, 변수 a를 1씩 증가시킨다.

그리고 마지막에 남은 0이 아닌 수를 b라고 하면

를 계산하는 것이다.


두 수가 모두 2로 a번 나눠진다는 것은

두 수의 공약수에 2가 a번 포함되어있기 때문이라고 생각하면 이해하기가 쉽다.


36과 24의 경우에서, 마지막에 3이 남았다는 것은

바로 전 단계에 두 수에 모두 3이 포함되어있는 것이기 때문에 이 역시 곱해준다(위 식에서는 b)


규칙에서 두 수가 홀수일 때 값을 빼는 것은 유클리드 알고리즘과 관련있는 부분이다.




C언어 코드

int calcGcd(int n1, int n2)
{
    int exp = 0;
    int n;

    while (((n1|n2)&1) == 0) {
        ++exp;
        n1 >>= 1;
        n2 >>= 1;
    }

    while (n1!=0 && n2!=0) {
        while ((n1&1) == 0)
            n1 >>= 1;
        while ((n2&1) == 0)
            n2 >>= 1;

        if (n1 > n2)
            n1 = n1-n2;
        else
            n2 = n2-n1;
    }
    if (n1!=0)
        n = n1;
    else
        n = n2;

    return n<<exp;

}





관련글 : 유클리드 호제법(http://www.tibyte.kr/224)


유클리드 호제법(Euclidean algorithm)으로 최대공약수를 구할 수 있다.


두 정수 m과 n (m>n)의 최대공약수를 구하는 문제를

m-n과 n의 최대공약수를 구하는 문제로 줄일 수 있다.


왜냐하면 m과 n의 최대공약수를 G라 하면 다음과 같이 나타낼 수 있는데

m = Ga

n = Gb

m-n = G(a-b)와 같이 묶을 수 있기 때문이다. (a와 b는 서로소(relatively prime))



예를 들어 94와 30이 있을 경우 아래와 같은 단계를 거쳐 문제를 줄여가면서

최대공약수인 2를 구할 수 있는 것이다.


94    30   (A)

64    30   (A)

34    30   (A)

 4     30   (A) (B)

 4     26   (B)

 4     22   (B)   

 4     18   (B)

 4     14   (B)

 4     10   (B)

 4      6    (B)

 4      2    (B)

 2      2

 2      0


위 단계에서 (A)부분과 (B)부분을  잘 보면 뺄셈 연산을 여러 번 수행한 결과가 결국 나머지 값이라는 사실을 알 수 있다. 따라서 코드로 작성할 때 나머지연산(%)을 사용하면 다음과 같이 단계를 줄일 수 있다.


94   30

 4    30

 4     2

 2     2

 2     0



아래는 C언어로 작성한 코드이다.


int gcd(int n1, int n2)
{
    int temp;
    if (n1 < n2) {
        temp = n1;
        n1 = n2;
        n2 = temp;
    }
    while (n2 != 0) {
        temp = n1%n2;
        n1 = n2;
        n2 = temp;
    }
    return n1;
}






관련글 : 이진 최대공약수 알고리즘 (http://www.tibyte.kr/225)














세 점(기준점, 점1, 점2)이 있을 때 atan()함수를 1번만 써서 사잇각을 구하는 방법이다.

원리는 간단하다.


아래와 같이 한 각과 기준각이 이루는 각도를 α, 나머지 각을 β라 한다.



그러면 θ = α - β 라 할 수 있다.


tanθ는 다음과 같이 나타낼 수 있으므로 sinθ와 cosθ를 구하여 atan2의 각 매개변수로 넣으면 각을 알 수 있을 것이다.


먼저 sinθ는 삼각함수의 덧셈정리에 의해 이렇게 전개할 수 있다.


위 식을 처음에 주어진 x분과 y성분으로 나타낼 수 있으므로,

최종적으로는 이렇게 쓸 수 있다.




코사인세타도 같은 방법으로 전개한다.


공통항인 1/l1l2를 소거하면 아래와 같은 표현식을 얻을 수 있다.



angle = atan2(y1x2-x1y2, x1x2+y1y2);




atan2 함수가 아닌 atan함수를 사용한다면 atan(sin값/cos값) 형태로 사용하면 될 것이다.

→ angle = atan(y1x2-x1y2 / x1x2+y1y2);



▼ 컴퓨터 프로그램으로 작성하여 구동한 화면.






( tibyte.kr과 cafe.naver.com/sdbx에 게시)


 2D 게임을 짜다가 날아가는 미사일이 적을 향해 회전해야 하는 것을 구현할 때

미사일이 시계방향(CW : ClockWise)으로 회전할 것인지, 아니면

반시계방향(CCW : CounterClockWise)으로 회전해야 하는지 알아내야 한다.


 arctangent 함수로 미사일 진행방향과 적(목표물)의 각도를 구하여

미사일의 현재 진행각도와 조건문으로 비교하면 쉽게 될 것 같지만

각도체계가 -pi ~ pi 로 pi각 부분에서 불연속적인 수치가 나타나기 때문에

조건문이 생각보다 복잡해진다.



 미사일 진행방향의 방향벡터를 u, 미사일로부터 목표물에 이르는 방향벡터를 v로 놓고

두 방향벡터의 판별식을 보면 시계방향으로 돌아야 하는지 반시계방향으로 돌아야 하는지 알 수 있다.

판별식 값의 크기는 기하학적으로 두 방향벡터가 이루는 평행사변형의 넓이가 되는데

여기서 그 값의 부호를 보면 두 벡터의 위치관계가 나온다.



[그림1]



[그림1] 과 같이 방향벡터 u를 기준으로, det[u v]<0이면 v는 u보다 시계방향으로 회전한 곳에 위치하고,

det[u v]>0이면 v는 u에서 반시계방향으로 회전한 곳에 위치한다.

판별식 값이 0이면 두 방향벡터는 평행하다.






[그림2]



 다시 처음의 미사일 문제로 돌아와서 [그림2]에는

미사일의 벡터(벡터 AB)와 목표물(점 P)가 그려져 있다.

여기서 벡터AB와 벡터AP를 구하여 판별식을 구해본다면

미사일이 어디로 돌아야 하는지 계산할 수 있을 것이다.


벡터 AB : (Bx-Ax, By-Ay)

벡터 AP : (Px-Ax, Py-Ay) 




det[AB AP] = (Bx-Ax)*(Py-Ay) - (By-Ay)*(Px-Ax)



즉  (Bx-Ax)*(Py-Ay) - (By-Ay)*(Px-Ax)의 부호를 보면

시계방향, 반시계방향을 결정할 수 있다는 것이다. 


컴퓨터 그래픽에서는 y좌표의 값이 아래로 갈수록 커지기 때문에

위의 내용을 반전하여,

판별식값이 0보다 작으면 반시계방향이고,

판별식값이 0보다 크면 시계방향으로 처리하면 된다.








 

 ※ 아래 코드는 실행해보지 않은것입니다. 동작하지 않을 수도 있습니다.




점 2개의 좌표 정보로 표현된 선분이 2개 있을 때

충돌체크를 하는방법입니다.

퍼즐게임이나 슈팅게임, 아니면 총기를 발사하는 것을 구현할 때 유용하게 쓰일 수 있습니다.
첫번째 방법은 직선의 방정식을 이용하는 것입니다.



요약



아래와 같이 선분이 주어졌을때,



선분의 양 끝 두 점의 좌표를 알기때문에
직선의 방정식도 쉽게 나옵니다.


ax + by = c
a`x + b`y = c`
이 방정식에서 a, b, c, a`, b`, c` 만 변수에 저장해두는 형식으로
가상의(화면에 나타나지 않는) 직선이 있다고 생각하는 것입니다.



액션스크립트 geom 패키지의 Matrix 클래스를 사용하여
이원 일차방정식을 간단히 풀어낼 수 있겠죠.
즉, 위 방정식의 해가 교점의 좌표가 되는 것입니다.  



여기서 중요한 것이
구하려는 게 직선교점이 아닌 선분교점이라는 것입니다.



위와 같이 직선의 교점이 선분 밖에 있으면 안되겠죠.
교점의 좌표가 두 선분의 중간값이 되는지 체크하면 됩니다.

위의 행렬연산에서
역행렬이 존재하지 않는 경우는
해가 없거나(두 직선이 평행)
해가 무수히 많거나(두 직선이 일치)
이 두가지인데요,

두 직선의 x y 계수의 비로 이를 분기할 수 있는데,
두 직선의 해가 없는경우는 물론 두 선분도 겹치치 않으니 생각할 필요 없는데,
해가 무수히 많은경우는 다릅니다.


이러한(위 그림과 같은) 경우에는 직선의 해는 (무수히)있으나
구하려는 선분의 교차여부를 본다면 교차하지 않는 경우이지요.

선분의 한 점이 다른 선분의 중간값이 되느냐 안되느냐 하는 체크를 4개의 점에 걸쳐 모두 시행하면
해결할 수 있습니다.

이 경우와 같이
두 선분이 서로 겹쳐지는 경우는 제작하는 프로그램의 상황에 따라
만나는 것으로 처리할지 아니면 만나지 않을 것으로 처리할지 달라지겠네요.
예를 들어 총쏘는 게임을 만든다면 저렇게 스쳐가는것을 무시하게 할 수도 있지만,
꼬여있는 선분을 푸는 퍼즐게임 같은경우는 교차ok로 인식을 해야겠죠.




구현

선분이 두 개 있다면 
읽어들여야 할 변수는 
 
line1_p1.x , line1_p1.y    // 선분1 의 한쪽 끝 점의 x,y 좌표
line1_p2.x , line1_p2.y    // 선분1 의 다른 한 쪽 끝 점의 x,y 좌표
line2_p1.x , line1_p1.y    // 선분2 의 한쪽 끝 점의 x,y 좌표
line2_p2.x , line1_p2.y    // 선분2 의 다른 한 쪽 끝 점의 x,y 좌표

이렇게 8개가 됩니다. line1_p1 , line1_p2  등은 선분의 양 끝 점(DisplayObject 形) 입니다.


직선의 방정식의 기본형을 살짝 변형하여
ax - by = -c
a`x - b`y = -c`
를 기본으로 삼기로 하고,
a, b, c, a` ,b` ,c` 에 해당하는 변수를 각각
line1_a, line1_b, line1_c, line2_a, line2_b, line2_c
이라고 정했습니다.

직선1의 방정식에서 x의 계수인 line1_a 의 값은
1/(line1_p2.x - line1_p1.x)
가 되는데요, 왜 그러냐면
그래프에서 x의 계수를 2배로 하면 x축 방향으로 2배 축소 되고,
1/2 배로 하면 x축 방향으로 1/2배 축소(2배 늘어남) 가 되므로
직선의 기울기를, 주어진 선분의 기울기와 맞추기 위해
선분이 x축 방향으로 늘어난 정도(line1_p2.x - line1_p1.x)의 역수를 x의 계수로 취해 준 것입니다.

line1_b 의 값은 같은이치로
1/(line1_p2.y - line1_p1.y) 가 되고,

line1_c 의 값은
지금까지 구한 계수(방정식에서 a, b에 해당)와 선분의 아무 한 점을 최초의 방정식
ax - by = -c
에 대입하면 나옵니다.
따라서 아래와 같이 프로그램할 수 있겠습니다.
line1_c = (line1_a*line1_p1.x  +  -1*line1_b*line1_p1.y)*-1


직선2의 계수들도 같은방법으로 구해주면 드디어
두 직선의 방정식이 나왔네요.

이제 행렬을 이용해서 해를 구해야합니다.






Matrix 클래스는 플래시8 부터 있기때문에 그 이전 버전에서는 직접 비슷하게 구현해야 합니다.(역행렬, 행렬곱 메서드 정도만)
액션스크립트 3.0 에서는 flash.geom 패키지에 Matrix 클래스가 들어있습니다.

위쪽의 수식에서
(a  b )
(a` b`)
이 행렬을  matrix1 이라고 하고
(c )
(c`)
이 행렬은 matrix2라고 하면,  


(ActionScript3.0)
import flash.geom.Matrix;
var matrix1:Matrix = new Matrix(line1_a , -1*line1_b , line2_a , -1*line2_b );
var matrix2:Matrix = new Matrix(-1*line1_c , -1*line2_c );
var matrix3:Matrix = new Matrix();

이렇게 나타낼 수 있습니다

위쪽의 수식에서와 같이
매트릭스1을 역행렬로 변환하고, 매트릭스2를 곱해주면 되는데요,
matrix1.invert();
matrix3 = matrix1.concat(matrix2);
위와 같이 내장된 메서드를 이용하면 간단히 연산할 수 있습니다.

아! 역행렬이 존재하지 않는경우(ad-bc=0 의 꼴일 때)도 있으니까 위에 추가를 해줘야 합니다.
그래서 코드를 보면,

import flash.geom.Matrix;

var line1_a:Number = 1/(line1_p2.x - line1_p1.x);
var line1_b:Number = 1/(line1_p2.y - line1_p1.y);
var line1_c:Number = (line1_a*line1_p1.x  +  -1*line1_b*line1_p1.y)*-1;
var line2_a:Number = 1/(line2_p2.x - line2_p1.x);
var line2_b:Number = 1/(line2_p2.y - line2_p1.y);
var line2_c:Number = (line2_a*line1_p1.x  +  -1*line2_b*line2_p1.y)*-1;

var matrix1:Matrix = new Matrix(line1_a , line1_b*-1 , line2_a , line2_b*-1 );
var matrix2:Matrix = new Matrix(line1_c*-1 , line2_c*-1 );
var matrix3:Matrix = new Matrix();
if(matrix1.a*matrix1.d == matrix1.b*matrix1.c) {   //만약 역행렬이 존재하지 않으면
   if(matrix2.a/matrix2.c != matrix1.a/matrix2.c) {  //만약 두 직선이(일치하지 않고)평행하면
       //두  직선(선분)이 평행하므로 교차하지 않음
   }
   else {
     // 두 직선이 일치함. 상황에 따라 추가 코딩.
   }
}
else {  //(위의 if의 부정을 받아)만약 역행렬이 존재하면,
   matrix1.invert();                                 //행렬1을 역행렬화 함
   matrix3 = matrix1.concat(matrix2);        //행렬1과 행렬2의 행렬곱을 구해서 행렬3에 대입
}



일단 이렇게해서 두 직선의 교점의 좌표가 행렬3에 들어가게 됩니다.
위쪽의 행렬수식을 참고하면
matrix3.a 에는 교점의 x좌표가 들어가고
matrix3.c 에는 교점의 y좌표가 들어간다는 것을 알 수 있습니다.

그런데 구하려는 것은 직선의 교점이 아닌 선분의 교점입니다.
구한 (교)점이 선분에 포함되는지를 체크해야 합니다.

if( Math.min(line1_p1.x,line1_p2.x) <= matrix3.a  &&  Math.max(line1_p1.x,line1_p2.x) >= matrix3.a 
    Math.min(line1_p1.y,line1_p2.y) <= matrix3.b  &&  Math.max(line1_p1.y,line1_p2.y) >= matrix3.b  
    &&
    Math.min(line2_p1.x,line2_p2.x) <= matrix3.a  &&  Math.max(line2_p1.x,line2_p2.x) >= matrix3.a 
    Math.min(line2_p1.y,line2_p2.y) <= matrix3.b  &&  Math.max(line2_p1.y,line2_p2.y) >= matrix3.b ) 
   { 
      //교차.
   }
else {
   //교차하지 않음.
}


이렇게 교차여부와 교점의 좌표를 구할 수 있습니다.
(교차여부 확인하는 코드는 더 짧게 줄일 수 있지만 여기서는 쉽게 하기위해서, 교점좌표가 두 선분의 사이에 있는지 
 부등호를 사용하여 조건을 작성했습니다.)  






+ Recent posts

티스토리툴바