[기하] ccw, 선분교차

간결한 기하 코드를 위한 벡터 클래스

실제로는 문제에 맞게 필요한 부분만 구현하거나, 변형해서 사용한다.
아래서 작성할 코드들을 간결하게 하기 위해 필요한 기능을 대부분 구현해놓았다. (종만북)
2차원 벡터이며, 잘 이해하면 n차원으로 그대로 확장이 가능하다.

const double PI = acos(-1.0);
struct Vector2{
   
    double x, y;

    explicit Vector2(double x_=0, double y_=0) : 
        x(x_), y(y_) {}

    bool operator ==(const Vector2& b) const {
        return x == b.x && y == b.y;
    }
	// x,y순서대로 정렬
    bool operator <(const Vector2& b) const {
        return x != b.x ? x < b.x : y < b.y;
    }

    Vector2 operator + (const Vector2 & b) const {
        return Vector2(x + b.x, y + b.y);
    }

    Vector2 operator - (const Vector2& b) const {
        return Vector2(x - b.x, y - b.y);
    }

    Vector2 operator *(double b) const {
        return Vector2(b * x, b * y);
    }
	// 벡터의 크기(길이)라고 생각하면 된다. 
    inline double norm() const {
        return hypot(x, y);
    }
	// 정규화
    Vector2 normalize() const {
        return Vector2(x / norm(), y / norm());
    }
	// x기준으로 시계방향 각도 
    double polar() const {
        return fmod(atan2(y, x) + 2 * PI, 2 * PI);
    }
	// 내적
    double dot(const Vector2& b) const {
        return x * b.x + y * b.y;
    }
	//외적
    double cross(const Vector2& b) const {
        return x * b.y - y * b.x;
    }
	//정사영
    Vector2 projection(const Vector2& b) const {
        Vector2 normed = b.normalize();
        return normed * normed.dot(*this);
    }
};

ccw(Counter Clock Wise)

// 방향만 판단하려면 부호만 리턴할 수 있다.
// 값은 면적 계산에 사용할 수 있다.
double ccw(Vector2 a, Vector2 b) {
	return a.cross(b);
}

// a->b->c로 이어지는 선분의 방향
double ccw(Vector2 a, Vector2 b, Vector2 c) {
	return ccw(b-a, c-a);
}

외적의 성질을 이용해서, 두 선분(벡터)가 이루는 각의 방향을 판단하는 알고리즘이다.
양수면 a를 기준으로 b와이루는 각도가 반시계방향, 0이면 한 직선에 포함, 음수이면 시계방향이다.

직선 교차

먼저 교차의 정의를 명확히 하자. 엄밀한 수학정인 정의는 알지 못한다. 프로그래밍 문제 해결의 측면에서, 선분의 일부가 겹쳐도(즉, 유일한 교점을 정의할 수 없어도) 교차하는 것으로 하자.

bool lineIntersection(Vector2 a1, Vector2 a2, Vector2 b1, Vector b2) {
	//실수 오차 고려
	if ( fabs((a2-a1).cross(b2-b1)) <= EPSILON)
    	return true;
    else
    	return false;
}

직선은 무한히 이어진 선분이기 때문에, 평행하지만 않다면 분명 교차한다.

교점을 직접 구하고 싶다면 좀 복잡해진다. 두 직선이 평행하다면 두 직선이 완전히 일치하는 경우도 존재할 수 있지만 false를 반환하도록 하겠다. 즉, 교점이 유일한경우만 true를 반환하고 교점을 res에 넣는다.

bool lineIntersection(Vector2 a1, Vector2 a2, 
Vector2 b1, Vector b2, Vector& res) {
	Vector2 a = a2-a1;
    Vector2 b = b2-b1;
	double det = (a).cross(b);
	if (fabs(det) <= EPSILON)
    	return false;
        
    // a1 + a * p
    res = a1 + a*(b1.cross(b) - a1.cross(b)) / det;
    return true;
}

아이디어는 다음과 같다. a1~a2로 이루어진 직선을 a, 마찬가지로 b1~b2로 이루어진 직선 b이다.
a = a2-a1(직선 a의 방향벡터), b=(b2-b1)(직선 b의 방향벡터)라고 하면, p와 q에 대한 연립방정식을 풀면 교점을 구할 수 있다는 것을 알 수 있다. (평행이 아닌 경우에만)

a1 + p*a = b1 + q*b
-> a1.x + p*a.x = b1.x + q*b.x
-> a1.y + p*a.y = b1.y + q*b.y

연립방정식을 잘 풀면,

p = (b1*b - a1*b) / a*b 이다.
(이미 a*b ==0이면 평행하다는 것을 보였다. 평행한 경우를 제외하고는 교점이 무조건 정의된다는 것을 알 수 있다.)

p 를 a1 + p*a에 대입하면, 교점을 알 수 있다.

선분의 교차

선분의 교차는 더 복잡하다.
1) 한 직선에 있지 않음(비교차, 서로 중간에서 교차, 한선분의 끝과 교차)
2) 두 선분이 한 직선에 있음(안겹침, 한점겹침, 부분겹침, 포함)
등등 고려해야할 케이스가 많다.

bool segmentIntersects(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2) {
    double ccw1 = ccw(a1, a2, b1) * ccw(a1, a2, b2);
    double ccw2 = ccw(b1, b2, a1) * ccw(b1, b2, a2);
    // 두 선분이 한직선
    if (ccw1 == 0 && ccw2 == 0) {
        // a1<a2 and b1<b2
        if (a2 < a1) swap(a1, a2);
        if (b2 < b1) swap(b1, b2);
        return !(a2 < b1 || b2 < a1);
    }
    // 평행하지 않은 case(둘다 0아님) + 한점에서 만나는 케이스 (둘중 하나만 0)
    else
        return ccw1 <= 0.0 && ccw2 <= 0.0;
}

ccw를 활용해서 해결할 수 있다.

직점 교점을 구하고 싶은 경우는 우선, 평행한 경우와 평행하지 않은 경우로 나누어 해결할 수 있다.

1) 평행하지 않다면, 직선의 교점 구하는 알고리즘을 활용해 구한 교점이 각 선분에 포함되는지 판단하면 된다.
2) 평행하다면, 두 선분이 서로 겹치는지 판단하고 겹치면 교선분 중의 임의의 점을 선택하면 된다.

bool segmentIntersects(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, Vector2& res) {
	// WLOG, a1<a2, b1<b2
    if(a2<a1) swap(a1,a2);
    if(b2<b1) swap(b1,b2);

    // 평행한 경우, 
    if (!lineIntersection(a1,a2,b1,b2,res)) {
        // 평행하지만 한직선에 있지 않은경우 + 
        // 한직선에 있어도 서로 겹치지 않는경우 
        if (ccw(a1,a2,b1)!=0 || a2<b1 || b2<a1)
        	return false;
        // 최소 한점 이상에서 겹치는게 확실하다.
        // 잘 선택해서 res에넣고 true를 리턴하자.
        if (a1<b1) res = b1; else res = a1;
        return true;
    }
    // 평행하지 않은 경우
    // lineIntersection의 결과로, 선분을 직선으로 연장했을 때의 교점이
    // 현재 res에 들어있다. 각 선분에 포함되는지 보자.

   	if (res<a1 || a2<res || res<b1 || b2<res)
        return false;
    return true;

}

점과 선의 거리

내적과 정사영의 개념을 알면 쉽게 해결할 수 있다.
a1, a2가 이루는 직선에 b가 내린 수선의 발을 구하는 코드이다.

Vector2 perpendicularFoot(Vector2 a1, Vector2 a2, Vector2 b) {
	return a1 + (b-a1).projection(a2-a1);
}

수선의 발과 b와의 거리를 구하면 된다.

double pointToLine(Vector2 a1, Vector2 a2, Vector2 b) {
	return (b-perpendicularFoot(a1,a2,b)).norm();
}