Comprobar si dos segmentos se intersectan
Se dan dos segmentos y . Hay que comprobar si se intersectan. Por supuesto, se puede encontrar su intersección y comprobar que no sea vacía, pero esto no se puede hacer en enteros para segmentos con coordenadas enteras. El enfoque descrito aquí puede trabajar en enteros.
Algoritmo
Primero, considérese el caso en que los segmentos son parte de la misma recta. En este caso basta comprobar si sus proyecciones sobre y se intersectan. En el otro caso y no deben yacer del mismo lado de la recta , y y no deben yacer del mismo lado de la recta . Esto se puede comprobar con un par de productos cruz.
Implementación
El algoritmo dado está implementado para puntos enteros. Por supuesto, se puede modificar fácilmente para trabajar con dobles.
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));
}