두 선분의 교차 여부 확인하기¶
두 선분 $(a, b)$와 $(c, d)$가 주어집니다. 두 선분이 교차하는지 확인해야 합니다. 물론 두 선분의 교집합을 구한 뒤 그것이 비어 있지 않은지 확인할 수도 있지만, 좌표가 정수인 선분에 대해서는 이 방법을 정수 연산만으로 수행할 수 없습니다. 여기서 설명하는 방법은 정수 연산만으로 동작할 수 있습니다.
알고리즘¶
먼저 두 선분이 같은 직선 위에 있는 경우를 생각해 봅시다. 이 경우에는 $Ox$와 $Oy$ 위로의 두 선분의 사영이 각각 교차하는지 확인하는 것으로 충분합니다. 그 외의 경우에는 $a$와 $b$가 직선 $(c, d)$의 같은 쪽에 있으면 안 되고, $c$와 $d$도 직선 $(a, b)$의 같은 쪽에 있으면 안 됩니다. 이는 외적을 몇 번 계산하여 확인할 수 있습니다.
구현¶
위 알고리즘은 정수 좌표의 점에 대해 구현되어 있습니다. 물론 double을 다루도록 쉽게 수정할 수 있습니다.
struct pt {
long long x, y;
pt() {}
pt(long long _x, long long _y) : x(_x), y(_y) {}
pt operator-(const pt& p) const { return pt(x - p.x, y - p.y); }
long long cross(const pt& p) const { return x * p.y - y * p.x; }
long long cross(const pt& a, const pt& b) const { return (a - *this).cross(b - *this); }
};
int sgn(const long long& x) { return x >= 0 ? x ? 1 : 0 : -1; }
bool inter1(long long a, long long b, long long c, long long d) {
if (a > b)
swap(a, b);
if (c > d)
swap(c, d);
return max(a, c) <= min(b, d);
}
bool check_inter(const pt& a, const pt& b, const pt& c, const pt& d) {
if (c.cross(a, d) == 0 && c.cross(b, d) == 0)
return inter1(a.x, b.x, c.x, d.x) && inter1(a.y, b.y, c.y, d.y);
return sgn(a.cross(b, c)) != sgn(a.cross(b, d)) &&
sgn(c.cross(d, a)) != sgn(c.cross(d, b));
}