티바이트

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

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

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

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

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

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

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

그림 1. 교차하는 두 선분                                  

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

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

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

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

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

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

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

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

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

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

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

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

결론

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

소스코드

동작하는 전체 코드는(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보다 크면 시계방향으로 처리하면 된다.