Ray Casting Algorithm

Ray casting algorithm은 inside-polygon test의 일종이다. 점과 (단순)다각형이 있을 때, 점이 다각형 안에 들어있는가를 판별한다.

 

만약 다각형이 볼록하다면 점이 다각형 안에 들어있는지 여부의 검사는 ray casting algorithm을 떠올리지 않아도 쉽다. CCW를 이용하면 된다. 모든 변 $A_i A_{i+1}$에 대하여, 점 $P$가 변에서 다각형 안으로 들어가는 방향에 존재한다면, 즉 점이 반시계방향으로 배열돼 있다는 가정에서 $ccw(A_i , A_{i+1} , P) > 0$이 모든 $i$에 대해 성립한다면 그 점은 다각형 안에 있다.

 

다각형이 볼록할 때에 inside-polygon test를 더 빠른 시간인 $O( \log n)$에 할 수도 있다. 이는 ray casting algorithm을 모두 설명한 다음에 후술한다.

 

int n;
pint p[10004];
 
int ccw(pint a, pint b, pint c) {
    lint k = a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y;
    if (k>0) return 1;
    if (k<0) return -1;
    return 0;
}
 
bool okay(pint a) {
    bool one = false, mone = false;
    for (int i=0; i<n; i++) {
        int k = ccw(p[i], p[i+1], a);
        if (k == 1) one = true;
        if (k == -1) mone = true;
    }
    return not (one and mone);
}
 

 

만약 다각형이 오목해지기 시작한다면 이렇게 생각하기 정말 귀찮아지는데... ray casting algorithm은 다음과 같은 아이디어를 이용한다.

 

점에서 시작하는 아무 반직선을 그어보자. 이 반직선이 다각형과 짝수 번 만난다면 점은 다각형 밖에, 홀수 번 만난다면 점은 다각형 안에 있다.

 

다각형의 변은 항상 다각형의 내부와 외부를 가른다는 점에서 자명하면서도 멋진 명제이다. 반직선의 방향은 여기서 아무 상관이 없다. 이제 다각형의 각 변에 대해서 이 반직선과 교차하는지 잘 검사해 주고 카운트하자. 선분 교차를 판별하는 게 은근 빡센데, 그건 이렇게 하면 된다:

 

선분 $AB$와 선분 $CD$가 교차하려면, $ccw(A, B, C) \neq ccw(A, B, D)$이고, $ccw(C, D, A) \neq ccw(C, D, B)$이다. 각 선분의 양끝이 다른 선분으로 인하여 분리되어야 한다는 것이다. $AB$와 $CD$가 한 직선 위에 있는 예외의 경우가 있는데, 이 경우에는 두 직선이 겹치는 부분이 있는지 판별하면 된다.

 

뭐.. 반직선이야 무한히 그어야 하지만 무한 같은 건 세상에 없으니 엄청 멀리 점 하나를 찍고 그 점과 잇는 선분을 그어서 반직선이라 우기자. 코드는 아래와 같다!

 

하지만 기하 알고리즘이 늘 그렇듯, 짜증나는 예외들이 존재한다. 아래 그림의 (1), (3), (4), (5)와 같은 것들이다. 

 

게다가 입력으로 주어지는 점 자체가 그냥 다각형 위에 존재할 수도 있다. 생각만 해도 화가 나지 않을 수 없다. 곰곰이 생각해 보자. 저런 경우들을 없앨 방법 중 한 가지는 저런 기울기들을 피해서 기울기를 잘 잡도록 설정해두는 것이다. $y=20.001021x + k$ 와 같이 아무 실수나 기울기로 잡은 다음 선을 그으면 그림에 그려진 예외의 경우를 피할 수도 있을 것이다. 그럴 경우에도 판정해야 하는 점 자체가 다각형의 꼭짓점과 같은 점이면 그런 경우를 피할 수 없다. 그것만은 예외로 판정해 주자.

 

글을 올리기 전 추가로 검색하다 깨달았는데, 만약 모든 좌표가 정수라면, 멀리 떨어진 점을 잡을 때 판정해야 할 점과 y좌표가 1만큼 차이나도록 하면, 절대 꼭짓점과 겹치거나 직선이 변과 겹치게 되어 무한히 많은 교점을 가지게 되는 일이 발생하지 않는다.

 

int n;
pint p[10004];
 
int ccw(pint a, pint b, pint c) {
    lint k = a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y;
    if (k>0) return 1;
    if (k<0) return -1;
    return 0;
}
 
bool intersect(pint a, pint b, pint c, pint d) {
    int x = ccw(a, b, c) * ccw(a, b, d);
    int y = ccw(c, d, a) * ccw(c, d, b);
 
    if (!x and !y) {
        if (a>b) swap(a, b);
        if (c>d) swap(c, d);
        return a <= d and c <= b;
    } else return x != 1 and y != 1;
}
 
bool okay(pint a) {
    pint b = pint(1020001021ll, a.y + 1);
 
    for (int i=0; i<n; i++) if (p[i] == a) 
        return true;
 
    int cnt = 0;
    for (int i=0; i<n; i++) {
        cnt += intersect(p[i], p[i+1], a, b);
    }
 
    return cnt % 2 != 0;
}
 

 

 

하지만 저런 예외의 가능성을 각오하고 가오있게 수평방향으로 반직선을 긋고 싶다면, 아래와 같이 괜찮은 아이디어를 내 주면 된다.

 

- 교차하는 변의 양 끝 중 하나가 반직선에서 윗방향(ccw를 했을 때 양수인 방향)인 변만 "교차했다"라고 판정하면, 정말로 선분이 다각형 안팎을 왔다갔다할 때에만 셈하게 된다.

 

증명은 알아서 해 보자. 이를 두고 "직선을 내 마음 속에서만 아주아주 살짝 올리기"라고 표현하기도 하나보다(알고리즘 문제해결 전략). 그걸 바꾼 okay 함수는 다음과 같이 생겼다.

 

bool okay(pint a) {
    pint b = pint(1020001021ll, a.y);
 
    for (int i=0; i<n; i++) if (p[i] == a) 
        return true;
 
    int cnt = 0;
    for (int i=0; i<n; i++) {
        cnt += (ccw(p[i], a, b) == 1 or ccw(p[i+1], a, b) == 1) and intersect(p[i], p[i+1], a, b);
    }
 
    return cnt % 2 != 0;
}
 

 

한편, 볼록다각형의 경우에는 무조건 반직선이 다각형과 두 번 이하만 만나게 된다. 그렇다면 교차점을 이분 탐색을 이용하여 구할 수 있다.