프로그래밍 연습장

Ray Casting Algorithm 본문

알고리즘

Ray Casting Algorithm

김준원 2019. 7. 21. 00:33

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을 모두 설명한 다음에 후술한다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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>0return 1;
    if (k<0return -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);
}
 
cs

 

 

만약 다각형이 오목해지기 시작한다면 이렇게 생각하기 정말 귀찮아지는데... 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만큼 차이나도록 하면, 절대 꼭짓점과 겹치거나 직선이 변과 겹치게 되어 무한히 많은 교점을 가지게 되는 일이 발생하지 않는다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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>0return 1;
    if (k<0return -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;
}
 
cs

 

 

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

 

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

 

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

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}
 
cs

 

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

'알고리즘' 카테고리의 다른 글

de Bruijn 수열  (2) 2020.02.21
Ray Casting Algorithm  (5) 2019.07.21
Skip List  (2) 2018.03.31
키타마사 법  (0) 2018.03.25
Manacher의 알고리즘과 Z 알고리즘  (0) 2018.02.27
그래프의 간선 리스트 표현  (2) 2017.12.06
5 Comments
  • 프로필사진 joon 2020.03.29 20:44 안녕하세요!
    진짜 블로그 설명 너무 너무 잘보고 있습니다 이번 Ray Casting Algorithm 을 보면서
    하나 궁금한점이 있어서 감히 질문 드립니다
    "만약 모든 좌표가 정수라면, 멀리 떨어진 점을 잡을 때 판정해야 할 점과 y좌표가 1만큼 차이나도록 하면, 절대 꼭짓점과 겹치거나 직선이 변과 겹치게 되어 무한히 많은 교점을 가지게 되는 일이 발생하지 않는다."
    실제로 어떻게든 그려봐도 겹치거나 하는 선분이 존재 하지 않는 것 같습니다.
    (다각형의 어떤 선분과 판정 해야할 점의 y좌표가 1만큼 차이나는 점과 판정해야할 점을 잇는 선분이 겹치지 않는 다는 것이죠)
    혹시 어떤 원리에서 그런 것인지 증명 혹은 관련 개념이 있는지 알 수 있을까요?
  • 프로필사진 BlogIcon 김준원 2020.04.01 23:29 신고 이 글에서 꼭짓점들의 좌표가 정수 위에 있다고 가정하고 있기 때문입니다. 예를 들면 (0, 0)과 (10억, 1)을 잇는 선을 그리면 사이에 정수 좌표를 가지는 점이 없기 때문에 물론 다각형의 꼭짓점도 그 위에 있을 수 없을 것입니다. 또한, 이 직선의 기울기는 10억 분의 1이기 때문에, 만약 좌표들이 있을 수 있는 범위가 10억보다 작다면 이 직선과 평행한 변도 그릴 수 없을 것입니다.
    물론 다각형의 좌표가 실수가 될 수 있다면, 이 방법이 통하지 않습니다.
  • 프로필사진 joon 2020.04.04 02:10 아 답변 정말 감사드립니다!!
    꼭짓점들의 좌표가 정수 위에 있다는 가정하에만 가능 하군요
    블로그글들이 정리가 너무 잘되어 있어서 종종 모르는 알고리즘 만나면 참고하며 공부하다 갑니다
    다시 한번 친절한 답변 정말 감사들립니다!
  • 프로필사진 Kim 2021.07.28 23:31 안녕하세요!
    이번 게시물을 올려주셔서 정말 감사합니다. 유익한 게시물 너무너무 잘 보고 있습니다.
    다만 한가지 그림 (1), (2), (3), (4)가 안보여서 질문드립니다!
    혹시 그림을 올려 주실 수 있을까요? 정말 감사합니다.
  • 프로필사진 익명 2021.07.28 23:33 비밀댓글입니다
댓글쓰기 폼