ccw와 선분교차판정 정리

기하문제를 너무 안푼것 같아서 풀려고 하는데,기하문제풀이를 할때 빈번하게 나오는 ccw와 선분교차 판정에 대해 정리를 한번 하고 가고자 한다.

 

일단 선분교차판정은 A점(x1, y1)과 B점(x2, y2)이 이어져 있는 AB선분이 있고, C점(x3, y3)과 D점(x4, y4)이 이어져 있는 CD선분이 있다고 할때 두 선분이 교차하는지 교차하지 않는 따지는 작업이라 생각하면 된다.

 

이때에 두 선분이 교차하는 경우의 수는 크게는 2가지가 있다. 

 

먼저, 아래와 같은 두 선분이 일찍선상에 놓이는 형태로 겹치는 경우

 

다음으로, 아래와 같은 두 선분이 서로다른 방향잡고 있는 크로스형태. 

 

 

일단, 첫번째 경우에는 겹치는 경우인데, 위 선분을 X축으로 눕히든 Y축으로 눕히든 눕혀보면 AB선분 중 가장 긴 값보다 CD의 가장 작은값이 작다면 겹치는 모양새가 된다. 동시에 CD의 가장 긴값은 AB의 가장 작은값보다 커야 한다. 대략적으로 이 두조건이 만족되어야 한다. 자세한건 코드로 보면서 상세한 조건을 체크해야 할것으로 보인다.

 

두번째 경우에는 이를 수식으로 표현하는 규칙은 직관적으로 떠올리기 어려운 만큼 외워야 한다. 

1)A -> B -> C를 순서로 선을 이어보면 이것은 시계 방향으로 돌고 있는 모양새가 된다.

2)A -> B -> D를 순서로 선을 이어보면 이것은 시계 반대방향으로 돌고 있는 모양새가 된다.

즉, A,B,C의 관계가 시계방향이어야 하고, A,B,D의 관계가 시계반대방향이어야 한다. 사실 선분의 위치에 따라 그 반대 경우도 존재할수 있으나 일단 러프하게 이정도 룰이 있다고만 숙지하자. 자세한건 코드로 보자.

 

 

이제 코드를 봐보자. 코드의 주석에 상세히 써놨으니 확인해보면 이해가 될것같다. 아래 코드의 동작에 대한 상세한 절차도 적어보도록 하겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {


//    세점 A,B,C의 모양과 방향에 대한 판별
//    (x2 - x1) / (y2 - y1) =  (x3 - x1) /  (y3 - y1) 기반 식 생성
//    1은 반시계, -1은 시계, 0은 일직성 => 결과값을 외우지 않고, (0,0), (0,1), (1,0)을 한번 돌려보는게 나음.(이건 -1)
    static int ccw(long x1, long y1, long x2, long y2, long x3, long y3) {
        long value = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
        if (value > 0) return 1;
        if (value < 0) return -1;
        return 0;
    }

//    두 선이 겹치는지 판별(a1, a2는 AB의 점. b1, b2는 CD의 점)
//    아래 식은 더 앞에 있는 AB의 선상에 CD가 겹치면서 이어지거나, 더 앞에 있는 CD의 선상에 AB가 이어지는 경우 모두포함
    static boolean overlap(long a1, long a2, long b1, long b2) {
        return Math.max(a1, a2) >= Math.min(b1, b2)
                && Math.max(b1, b2) >= Math.min(a1, a2);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

//        입력: 선분 AB
        StringTokenizer st = new StringTokenizer(br.readLine());
        long x1 = Long.parseLong(st.nextToken());
        long y1 = Long.parseLong(st.nextToken());
        long x2 = Long.parseLong(st.nextToken());
        long y2 = Long.parseLong(st.nextToken());

//        입력: 선분 CD
        st = new StringTokenizer(br.readLine());
        long x3 = Long.parseLong(st.nextToken());
        long y3 = Long.parseLong(st.nextToken());
        long x4 = Long.parseLong(st.nextToken());
        long y4 = Long.parseLong(st.nextToken());

//        CCW 계산 : ABC, ABD, CDA, CDB
//        AB, CD 선분에서 확인 해야 할 관계는 AB선분과 C, AB선분과 D, CD선분과 A CD선분과 B의 관계뿐.
        int ab1 = ccw(x1, y1, x2, y2, x3, y3);
        int ab2 = ccw(x1, y1, x2, y2, x4, y4);
        int cd1 = ccw(x3, y3, x4, y4, x1, y1);
        int cd2 = ccw(x3, y3, x4, y4, x2, y2);


//        1.선분의 겹침 판정 : 네 점이 모두 일직선인 경우(가로, 세로, 대각 모두 동일)
        if (ab1 == 0 && ab2 == 0 && cd1 == 0 && cd2 == 0) {
            if (overlap(x1, x2, x3, x4) && overlap(y1, y2, y3, y4)) {
                System.out.println(1); // 조금이라도 겹침
            } else {
                System.out.println(0); // 겹치는 않으나, 교차도 아님.
            }
            return;
        }
        
//        2.선분의 교차여부 판별
//        2-1)선분 AB 기준으로 C, D가 서로 다른 방향(또는 한 점이 선 위)
//        2-2)선분 CD 기준으로 A, B가 서로 다른 방향(또는 한 점이 선 위)
        if (ab1 * ab2 <= 0 && cd1 * cd2 <= 0) {
            System.out.println(1); // 교차함.
        } else {
            System.out.println(0); // 교차하지 않음.
        }


    }
}

 

 

1.먼저, A,B,C,D 점에 대한 x,y좌표를 입력받는다.

 

2.그다음 ABC, ABD, CDA, CDB라는 가상의 선에 대해 시계방향인지 시계반대방향인지 또는 동일선상인지를 따지는 ccw 판정을 해야 한다. 왜 4가지 경우를 따지는 거냐면 AB선 CD선이 겹치는지 여부를 따지기 위함이라 ACB 같은 검증은 필요 없기 때문이다.

 

3.ccw식에서 시계방향을 따지는 식이 어떻게 도출된것인지를 알고 싶다면, 중고등학교때 배웠던, (x2 - x1) / (y2 - y1)와 (x3 - x1) /  (y3 - y1) 이런 형태의 기울기 구하는 공식을 떠올리면 좋을것 같다.

 

BA의 기울기 CA의 기울기를 두고 시계방향인지, 시계반대방향인지, 또는 == 관계라면 기울기가 같으니 겹치는것인지를 판명하는 아이디어라고 생각하면 좋을것 같다. 

 

그래서 식을 억지로 외우기 보다

 

(x2 - x1) / (y2 - y1) == (x3 - x1) /  (y3 - y1) 이렇게 두고,

 

(x2 - x1) * (y3 - y1)  == (x3 - x1)  * (y2 - y1)  이렇게 양변을 곱함으로서 나눗셈 부분을 없애주고,

 

(x2 - x1) * (y3 - y1)  - (x3 - x1)  * (y2 - y1) == 0 우변을 좌변으로 넘기고

 

이제 이 결과값이 == 0인지 0보다 큰지. 0보다 작은지를 따져주면 될것 같다.  

 

일단 0이면 같은기울기로 겹치는 결과를 의미한다. 0보다크면 1을 리턴했고, 0보다 작으면 -1을 리턴하도록 코드를 작성했다. 1의 경우엔 반시계. -1의 경우엔 시계방향이다.

 

1이 시계인지 -1이 반시계인지 이것도 외우는건 쉽지가 않다. 외우지 않고, 케이스를 한번 넣어 봄으로서 검증하는게 더 확실하고 빠르다.

 

(0,0), (0,1), (1,0) 이런 형태의 ABC를 집어넣어보는것이다. 이건 결과값이 -1이 나오고, A->B->C의 모양을 보면 이는 시계방향이다는 것을 알수가 있다.

 

4.이를 활용해서 위의 식에서는 겹침여부부터 판정하고 있다. 

 

일단, 모든 점들의 기울기가 같아야 한다. 다만, 일직선상에 있긴 있는데 겹치는 부분이 없을수 있기에 겹치는지 여부는 별도로 판정해야 한다. 아래 같은 그림은 기울기는 같지만 같은 선상에 없다.

즉, 일단 "모든 기울기가 같은지 확인하는 코드 && 겹치는지 여부 판정" 두개의 작업을 해줘야 겹치는지 판정할수 있다. 위 코드의 overlaps코드가 겹침여부 판정코드다.

 

5.이제 교차여부를 판정해보자. 먼저, 겹침여부부터 판정을 해준 이후에 교차여부작업을 해야 문제가 안생김에 주의하자.

1)선분 AB 기준으로 C, D가 서로 다른 방향(또는 한 점이 선 위)

2)선분 CD 기준으로 A, B가 서로 다른 방향(또는 한 점이 선 위)

 

즉 AB입장에서 C는 시계방향이거나 D는 시계반대방향이어서 서로 다른방향에 놓여있어야 cross가 될수 있다. 반대로 C가 시계반대방향이고, D가 시계방향이어도 상관은 없다. CD 입장에서의 A,B도 마찬가지다.

 

어?! 이거 반례 있지 않을까요? 라고 생각할수 있으나 이런식의 선분을 생각해보면 명확해 진다. AB입장에 C,D가 둘다 시계방향이다. 그러면 이렇게 크로스가 생기지가 않는다. 즉 같은 방향이면 크로스가 발생안한다는걸 알수 있다.

 

 

사실 이런류의 선분교차에 대한 판정은 기하학의 여러 분야에서 활용될수 있다고 생각한다. 다만, 문제를 풀면서 이런식의 코드를 떠올리는것은 쉽지가 않기에, 이런 류의 온전히 이해한 템플릿 코드 한세트는 가지고 있어야 할것 같다.

 

다만, 코테를 준비하는 개발자에겐 필요 없는 코드일것도 같다. 애초에 기하, 수학 이쪽은 출제빈도가 적으니 순수 즐거움으로만 코딩하실 분들에게만 의미가 있지 싶다.