[알고리즘] CCW(Counter Clockwise) 알고리즘

CCW 알고리즘

• CCW(Counter Clockwise)는 세 점의 방향 관계를 판별하는 알고리즘이다.
• 주로 기하학적 문제에서 사용되며, 점 A, B, C가 있을 때 이 세 점이 시계 방향으로 배열되어 있는지, 반 시계 방향으로 배열되어 있는지를 판단한다.
• 이를 통해 다각형의 내부에 점이 있는지, 선분이 교차하는지 등을 판별할 수 있다.

원리

• 벡터의 외적(cross product)을 이용하여 세 점의 방향을 결정한다.
• 점 A, B, C의 좌표를 (Ax, Ay), (Bx, By), (Cx, Cy)라 할 때, 다음과 같은 수식을 사용한다.

CCW 값 = (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)

• CCW 값 > 0: 점 A, B, C가 반시계 방향으로 배열되어 있음
• CCW 값 < 0: 점 A, B, C가 시계 방향으로 배열되어 있음
• CCW 값 = 0: 점 A, B, C가 일직선 상에 있음

 

수학적 배경

• 주어진 세 점 A(x1,y1), B(x2,y2), C(x3,y3)에 대해 행렬식을 사용한다.
• 자세한 증명은 다음 영상에서 이해하면 된다.

 

C++ 예제 코드

#include <iostream>

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {} // 생성자 (0으로 초기화)
};

int ccw(Point A, Point B, Point C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

int main() {
    Point A(1, 1);
    Point B(4, 4);
    Point C(6, 2);

    int result = ccw(A, B, C);

    if (result > 0) {
        std::cout << "반시계 방향" << std::endl;
    } else if (result < 0) {
        std::cout << "시계 방향" << std::endl;
    } else {
        std::cout << "일직선 상에 있음" << std::endl;
    }

    return 0;
}

 

다각형 내부 점 판별

• 주어진 점이 다각형 내부에 있는지 외부에 있는지를 판단한다.
• 가장 일반적으로 홀짝 법칙을 이용하여 점에서 수평으로 무한히 길게 선을 그었을 때, 이 선이 다각형의 변과 몇 번 교차하는지를 확인하는 방식
• 교차 횟수가 홀수이면 점은 다각형 내부, 짝수이면 외부에 있음

예제 코드

#include <iostream>
#include <vector>

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
};

int ccw(Point A, Point B, Point C) {
    int value = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
    if (value > 0) return 1;   // 반시계 방향
    if (value < 0) return -1;  // 시계 방향
    return 0;                  // 일직선 상에 있음
}

bool isInsidePolygon(const std::vector<Point>& polygon, Point p) {
    int n = polygon.size();
    int count = 0;
    for (int i = 0; i < n; i++) {
    	// 다각형의 한 변인 선분 ab와 점 p의 ccw 계산
        Point a = polygon[i];
        Point b = polygon[(i + 1) % n];
        if (ccw(a, b, p) == 0 && (p.x - a.x) * (p.x - b.x) <= 0 && (p.y - a.y) * (p.y - b.y) <= 0) {
            return true; // 점이 다각형의 변 위에 있음
        }
        if ((a.y > p.y) != (b.y > p.y)) {
            if (p.x < (b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x) {
                count++;
            }
        }
    }
    return count % 2 == 1;
}

int main() {
    std::vector<Point> polygon = { {1, 1}, {4, 1}, {4, 4}, {1, 4} };
    Point p(2, 2);

    if (isInsidePolygon(polygon, p)) {
        std::cout << "점은 다각형 내부에 있습니다." << std::endl;
    } else {
        std::cout << "점은 다각형 외부에 있습니다." << std::endl;
    }

    return 0;
}

 

조건문 설명

(a.y > p.y) != (b.y > p.y)

• 점 p의 y좌표와 다각형 변의 y좌표를 비교하여 점 p가 변의 위쪽에 있는지, 아래쪽에 있는지를 확인
• (p.y가 a.y와 b.y의 사이에 있는 값인지 확인)

p.x < (b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x

• (b.x - a.x) / (b.y - a.y)는 선분 ab의 x와 y방향의 길이로 선분 ab의 기울기를 계산한다.
  • 정수로 선언하여 자료형이 최대한 터지지 않게끔 (p.y - a.y)를 먼저 곱한 것
• (p.y - a.y)는 점 P와 점 A 사이의 y축 거리로 이를 ab의 기울기에 곱해주면 점 P의 y좌표가 동일한 가상의 수평선을 그었을 때, 이 수평선이 선분 ab와 교차하는 지점의 x좌표가 나옴
• x좌표에 점 a의 x좌표를 더하여 실제 교차 지점의 x좌표를 구함
• 이 x좌표가 p.x보다 작은지를 확인하여 작다면 점 p는 선분 ab의 좌측에, 크다면 우측에 위치함
• 좌측에 있는 경우만 count를 증가시켜 교차하는 것으로 판단

 

선분 교차 판별

• 두 선분이 평면에서 교차하는지 여부를 판단하는 알고리즘
• 네 점의 상대적인 방향성을 계산하여 선분이 교차하는지를 확인
• 선분 AB, CD가 교차하는지 판별할 때 점 A, B, C의 CCW값과 A, B, D의 CCW 값이 다르며, C, D, A의 CCW값과 C, D, B의 CCW값이 다르면 선분이 교차함을 알 수 있다.

예제 코드

#include <iostream>

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
};

int ccw(Point A, Point B, Point C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

bool isIntersect(Point A, Point B, Point C, Point D) {
    int ccw1 = ccw(A, B, C);
    int ccw2 = ccw(A, B, D);
    int ccw3 = ccw(C, D, A);
    int ccw4 = ccw(C, D, B);

    return (ccw1 * ccw2 < 0) && (ccw3 * ccw4 < 0);
}

int main() {
    Point A(1, 1), B(4, 4);
    Point C(1, 4), D(4, 1);

    if (isIntersect(A, B, C, D)) {
        std::cout << "선분이 교차합니다." << std::endl;
    } else {
        std::cout << "선분이 교차하지 않습니다." << std::endl;
    }

    return 0;
}

 

이 때, isIntersect 함수의 return 문을 return (ccw1 != ccw2) && (ccw3 != ccw4); 가 아닌 이유는 괄호 안의 값이 0일 경우 일직선 상에 존재할 수 있기 때문

 

 

일직선 상에 있을 경우를 예외로 처리한 예제 코드

#include <iostream>

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
};

int ccw(Point A, Point B, Point C) {
    int value = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
    if (value > 0) return 1;   // 반시계 방향
    if (value < 0) return -1;  // 시계 방향
    return 0;                  // 일직선 상에 있음
}

bool isIntersect(Point A, Point B, Point C, Point D) {
    int ccw1 = ccw(A, B, C);
    int ccw2 = ccw(A, B, D);
    int ccw3 = ccw(C, D, A);
    int ccw4 = ccw(C, D, B);

    if (ccw1 == 0 && ccw2 == 0 && ccw3 == 0 && ccw4 == 0) {
        return false; // 세 점이 일직선 상에 있는 경우 교차하지 않음
    }

    return (ccw1 * ccw2 < 0) && (ccw3 * ccw4 < 0);
}

int main() {
    Point A(1, 1), B(4, 4);
    Point C(1, 4), D(4, 1);
    Point E(2, 2), F(6, 6);

    // 선분이 교차하는 경우
    if (isIntersect(A, B, C, D)) {
        std::cout << "선분이 교차합니다." << std::endl;
    } else {
        if (ccw(A, B, C) == 0 && ccw(A, B, D) == 0) {
            std::cout << "세 점이 일직선 상에 있습니다." << std::endl;
        } else {
            std::cout << "선분이 교차하지 않습니다." << std::endl;
        }
    }

    // 세 점이 일직선 상에 있는 경우
    if (isIntersect(A, B, E, F)) {
        std::cout << "선분이 교차합니다." << std::endl;
    } else {
        if (ccw(A, B, E) == 0 && ccw(A, B, F) == 0) {
            std::cout << "세 점이 일직선 상에 있습니다." << std::endl;
        } else {
            std::cout << "선분이 교차하지 않습니다." << std::endl;
        }
    }

    return 0;
}