수학, 알고리즘, 프로그래밍




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



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



CCW, CW, 벡터, 수학, 알고리즘, 행렬




( 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보다 크면 시계방향으로 처리하면 된다.







hitTest, matrix, 선과 선의, 선분, 수학, 직선의방정식, 충돌체크, 플래시, 행렬, 히트테스트


 

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




점 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

티스토리툴바