[JAVA] CCW

CCW 란?

• Counter-ClockWise의 줄임말로 평면상의 3개의 점의 위치관계를 판한다는 알고리즘
• 세 점 A(X1, Y1), B(X2, Y2), C(X3, Y3) 이 있다고 가정했을 때
  • CCW의 공식은 CCW = ( X1*Y2 + X2*Y3 + X3*Y1 ) - ( X2*Y1 + X3*Y2 + X1*Y3 )
• 공식을 따로 외울 필요없이 아래 그림처럼 X1, Y1을 한 번 더 쓴 후, 검은 화살표 곱은 더하고 빨간 화살표 곱은 빼주면 됨

• 계산된 CCW 값으로는 2가지를 알 수 있음

1. CCW의 부호에 따라 시계방향, 반시계방향, 일직선의 위치관계에 있는지 파악 가능

                 CCW < 0 => 시계 방향                           CCW == 0 => 일직선                         CCW > 0 => 반시계 방향

2. CCW의 절대값은 세 점의 벡터의 외적값을 나타냄
   • 절대값을 2로 나누면 세 점으로 이루어진 삼각형의 넓이

• 각각의 특성을 활용한 문제들을 풀어보며 정리

CCW 값의 부호를 활용한 문제

https://www.acmicpc.net/problem/17387

17387번: 선분 교차 2

풀이 방법

• 점 A, B가 양끝점인 선분 L1 과 점 C, D가 양끝점인 선분 L2가 교차했는지 여부를 파악하는 문제

• 위 그림과 같이 만약 L1, L2가 교차한다면 점 A, B를 기준으로 C와 D는 서로 반대방향에 있어야 함
• 하나가 시계방향(음수)이면 다른 하나는 반시계방향(양수)여야 함
• 따라서 CCW(A,B,C) * CCW(A,B,D), CCW(C,D,A) * CCW(C,D,B) 두 값이 모두 음수라면 두 선분은 교차함을 의미
• 하나라도 양수이면 두 선분은 교차하지 않음
• 하나만 0이라면 세 점이 동일 직선에 있는 경우여서 교차로 판단

• 이제 CCW값이 둘 다 0이 나오는 상황을 생각해야 함
• 이 때는 위와 같이 두가지 경우가 존재함
• Case 1은 교차로 판단해야하고, Case 2는 교차 안함으로 판단해야함
• 이 상황에서는 조건이 하나 더 필요함
  • A, B의 x 중 큰 값이 C, D의 x 중 작은 값보다 크거나 같아야하고
  • C, D의 x 중 큰 값이 A, B의 x 중 작은 값보다 커거나 같아야 함
  • y도 성립해야 됨

코드

import java.util.Scanner;

public class p17387 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Point a = new Point(sc.nextLong(), sc.nextLong());
        Point b = new Point(sc.nextLong(), sc.nextLong());
        Point c = new Point(sc.nextLong(), sc.nextLong());
        Point d = new Point(sc.nextLong(), sc.nextLong());

        int res1 = ccw(a, b, c) * ccw(a, b, d);
        int res2 = ccw(c, d, a) * ccw(c, d ,b);

        if(res1 == 0 && res2 == 0) {
            if(Math.min(a.x, b.x) <= Math.max(c.x, d.x) && Math.min(c.x, d.x) <= Math.max(a.x, b.x) &&
                    Math.min(a.y, b.y) <= Math.max(c.y, d.y) && Math.min(c.y, d.y) <= Math.max(a.y, b.y)) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        } else if(res1 <= 0 && res2 <= 0) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }

    }

    static int ccw(Point a, Point b, Point c) {
        long result = ( a.x * b.y + b.x * c.y + c.x * a.y) - ( a.x * c.y + c.x * b.y + b.x * a.y);
        if(result == 0) return 0;
        else if(result > 0) return 1;
        else return -1;
    }

    static class Point {
        long x, y;

        public Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }
}

CCW 값의 절대값을 활용한 문제

https://www.acmicpc.net/problem/2166

2166번: 다각형의 면적

풀이 방법

• 아래와 같이 4개의 점이 순서대로 입력되었다고 생각했을 때, 빨간선 내부의 도형의 넓이를 구하는 문제

• 계산을 간단하게 하기 위해 원점을 사용해서 문제를 풀어봄
• 순서대로 원점을 포함한 두 점의 외적값을 구해야 됨
• CCW(1, 2, 원점)을 계산한 후 2로 나눠주면 아래의 그림에서 파란색으로 색칠된 부분의 넓이를 구할 수 있음

• 이 때, 부호를 생각해보면 CCW(1, 2, 원점), CCW(3, 4, 원점), CCW(4, 1, 원점) 은 모두 시계방향의 계산이기 때문에 + 부호를 갖게 되지만
• CCW(2, 3, 원점)은 반시계 방향의 계산이기 때문에 - 부호를 갖게 됨

 

• 결과적으로 양수값을 가지는 파란색 부분의 값과 음수값을 가지는 노란색 부분의 값을 모두 더하면 모든 점들로 이루어진 다각형의 넓이가 나옴
  • 두 점과 원점의 CCW 공식을 정리하면 CCW = X1 * Y2 - X2 * Y1 으로 단순화 할 수도 있음

코드

import java.util.Scanner;

public class p2166 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Point[] points = new Point[n];
        for(int i = 0 ; i < n ; i ++) {
            points[i] = new Point(sc.nextLong(), sc.nextLong());
        }

        Point zeroPoint = new Point(0, 0);
        double ans = 0;
        for(int i = 1 ; i < n ; i ++) {
            ans += (double) ccw(points[i - 1], points[i], zeroPoint) / 2.0;
        }
        ans += (double) ccw(points[n - 1], points[0], zeroPoint) / 2.0;
        System.out.printf("%.1f",Math.abs(ans));
    }

    static long ccw(Point a, Point b, Point c) {
        return( a.x * b.y + b.x * c.y + c.x * a.y) - ( a.x * c.y + c.x * b.y + b.x * a.y);
    }

    static class Point {
        long x, y;

        public Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }
}