선분 교차 판정

주어진 선분 2개의 교차 여부를 판정하는 방법이다.
이 또한 CCW를 사용하면 간편하게 해결할 수 있다.

여러 경우를 생각해야 하는데,
주어진 점 4개를 각각 base로 삼아서 다른 선분의 양 끝점으로 향하는 방향이 서로 반대인지를 확인하면 된다.

다만 주의해야 할 점이 있는데,
선분이 일직선으로 배치되어 있는 경우 CCW 만 맹신하면 정확히 판단할 수 없다.
왜냐하면 두 선분이 일직선으로 존재하되 겹치지 않은 경우와 겹친 경우 모두 CCW가 0으로 같기 때문이다.

따라서 두 선분이 겹치는 지 여부도 추가로 조사해주어야 한다.

코드로 나타내면 아래와 같다.

typedef long long ll;

// Point 구조체 정의
struct Point {
	int x;
    int y;
    
    // 연산자 오버로딩
    Point operator-(Point other) {
    	Point ret;
        ret.x = this->x - other.x;
        ret.y = this->y - other.y;
        
        return ret;
    }
};

ll ccw(Point a, Point b) {
	return a.x * b.y - a.y * b.x;
}

ll ccw(Point base, Point a, Point b) {
	return ccw(base, a, b);
}

int direction(Point base, Point a, Point b) {
	ll res = ccw(base, a, b);
    
    if(res > 0) return 1;			// 시계 반대방향
    else if(res < 0) return -1;		// 시계 방향
    else return 0;					// 일직선
}

// 점 target이 점 a와 점 b 사이에 존재하는지 확인하는 함수
bool isBetween(Point a, Point b, Point target) {
	// 일직선이 아니면 사이에 존재할 수 없다.
	if(direction(a, b, target) != 0) return false;
    
    // 점 a와 점 b가 수직인 경우
    if(a.x == b.x) {
    	return (a.y <= target.y && target.y <= b.y) ||
        	   (b.y <= target.y && target.y <= a.y);
    }
    // 점 a와 점 b가 수직이 아닌 경우
    else {
    	return (a.x <= target.x && target.x <= b.x) ||
        	   (b.x <= target.x && target.x <= a.x);
    }
}

// 선분 ab와 선분 cd가 겹치는지 여부 확인 -> 일직선 겹침 고려 X
bool _isIntersect(Point a, Point b, Point c, Point d) {
	// 한 선분을 기준으로 다른 선분의 양 끝점을 향하는 방향이 반대인지 확인
	return (direction(a, b, c) * direction(a, b, d) < 0) &&
    	   (direction(c, d, a) * direction(c, d, b) < 0);
}

// 선분 ab와 선분 cd가 겹치는지 여부 확인 -> 일직선 겹침 고려 O
bool isIntersect(Point a, Point b, Point c, Point d) {
	// 일직선인 경우에 한 선분의 점이 다른 선분 사이에 있는지도 확인
    return _isIntersect(a, b, c, d) ||
    	   (isBetween(a, b, c) || isBetween(a, b, d) ||
            isBetween(c, d, a) || isBetween(c, d, b));
}