Buscar un par de segmentos que se intersectan

Dados $n$ segmentos de recta en el plano. Se requiere comprobar si al menos dos de ellos se intersectan entre sí. Si la respuesta es sí, entonces imprimir este par de segmentos que se intersectan; basta con elegir cualquiera de ellos entre varias respuestas.

El algoritmo de solución naive es iterar sobre todos los pares de segmentos en $O(n^2)$ y comprobar para cada par si se intersectan o no. Este artículo describe un algoritmo con tiempo de ejecución $O(n \log n)$ , que se basa en el algoritmo de línea de barrido (sweep line).

Algoritmo

Tracemos mentalmente una recta vertical $x = -\infty$ y empecemos a mover esta recta hacia la derecha. En el curso de su movimiento, esta recta se encontrará con segmentos, y en cada momento un segmento intersecta con nuestra recta en exactamente un punto (asumiremos que no hay segmentos verticales).

línea de barrido e intersección de segmentos

Así, para cada segmento, en algún momento aparecerá su punto en la línea de barrido, luego con el movimiento de la recta este punto se moverá, y finalmente, en algún momento, el segmento desaparecerá de la recta.

Nos interesa el orden relativo de los segmentos a lo largo de la vertical. A saber, guardaremos una lista de segmentos que cruzan la línea de barrido en un momento dado, donde los segmentos estarán ordenados por su coordenada $y$ en la línea de barrido.

orden relativo de los segmentos a través de la línea de barrido

Este orden es interesante porque los segmentos que se intersectan tendrán la misma coordenada $y$ al menos en un momento:

punto de intersección con la misma coordenada y

Formulamos las afirmaciones clave:

Para encontrar un par que se intersecta, basta con considerar solo segmentos adyacentes en cada posición fija de la línea de barrido.
Basta con considerar la línea de barrido no en todas las posiciones reales posibles $(-\infty \ldots +\infty)$ , sino solo en aquellas posiciones en las que aparecen segmentos nuevos o desaparecen los viejos. En otras palabras, basta con limitarse solo a las posiciones iguales a las abscisas de los puntos extremos de los segmentos.
Cuando aparece un segmento nuevo, basta con insertarlo en el lugar deseado de la lista obtenida para la línea de barrido anterior. Solo debemos comprobar la intersección del segmento agregado con sus vecinos inmediatos en la lista arriba y abajo.
Si el segmento desaparece, basta con quitarlo de la lista actual. Después de eso, es necesario comprobar la intersección de los vecinos superior e inferior en la lista.
No existen otros cambios en la secuencia de segmentos en la lista, excepto los descritos. No se requieren otras comprobaciones de intersección.

Para entender la verdad de estas afirmaciones, bastan las siguientes observaciones:

Dos segmentos que no se intersectan nunca cambian su orden relativo.
De hecho, si un segmento estaba primero más alto que el otro, y luego se volvió más bajo, entonces entre estos dos momentos hubo una intersección de estos dos segmentos.
Dos segmentos que no se intersectan tampoco pueden tener las mismas coordenadas $y$ .
De esto se sigue que en el momento de la aparición del segmento podemos encontrar la posición para este segmento en la cola, y no tendremos que reordenar este segmento en la cola nunca más: su orden relativo a los demás segmentos de la cola no cambiará.
Dos segmentos que se intersectan en el momento de su punto de intersección serán vecinos el uno del otro en la cola.
Por lo tanto, para encontrar pares de segmentos que se intersectan basta con comprobar la intersección de todos y solo aquellos pares de segmentos que en algún momento durante el movimiento de la línea de barrido fueron vecinos al menos una vez.
Es fácil notar que basta solo con comprobar el segmento agregado con sus vecinos superior e inferior, así como al quitar el segmento — sus vecinos superior e inferior (que después de quitarlo se convertirán en vecinos el uno del otro).
Debe notarse que en una posición fija de la línea de barrido, debemos primero agregar todos los segmentos que empiezan en esta coordenada x, y solo luego quitar todos los segmentos que terminan aquí.
Así, no nos perdemos la intersección de segmentos en el vértice: es decir, tales casos en los que dos segmentos tienen un vértice en común.
Nótese que los segmentos verticales de hecho no afectan la corrección del algoritmo.
Estos segmentos se distinguen por el hecho de que aparecen y desaparecen al mismo tiempo. Sin embargo, debido al comentario anterior, sabemos que todos los segmentos se agregarán a la cola primero, y solo luego se borrarán. Por lo tanto, si el segmento vertical intersecta con algún otro segmento abierto en ese momento (incluyendo el vertical), se detectará.
¿En qué lugar de la cola colocar los segmentos verticales? Después de todo, un segmento vertical no tiene una coordenada $y$ específica, se extiende por todo un segmento a lo largo de la coordenada $y$ . Sin embargo, es fácil entender que cualquier coordenada de este segmento se puede tomar como coordenada $y$ .

Así, todo el algoritmo realizará no más de $2n$ pruebas de intersección de un par de segmentos, y realizará $O(n)$ operaciones con una cola de segmentos ( $O(1)$ operaciones en el momento de aparición y desaparición de cada segmento).

El comportamiento asintótico final del algoritmo es así $O(n \log n)$ .

Implementación

Presentamos la implementación completa del algoritmo descrito:


const double EPS = 1E-9;
 
struct pt {
    double x, y;
};
 
struct seg {
    pt p, q;
    int id;
 
    double get_y(double x) const {
        if (abs(p.x - q.x) < EPS)
            return p.y;
        return p.y + (q.y - p.y) * (x - p.x) / (q.x - p.x);
    }
};
 
bool intersect1d(double l1, double r1, double l2, double r2) {
    if (l1 > r1)
        swap(l1, r1);
    if (l2 > r2)
        swap(l2, r2);
    return max(l1, l2) <= min(r1, r2) + EPS;
}
 
int vec(const pt& a, const pt& b, const pt& c) {
    double s = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    return abs(s) < EPS ? 0 : s > 0 ? +1 : -1;
}
 
bool intersect(const seg& a, const seg& b)
{
    return intersect1d(a.p.x, a.q.x, b.p.x, b.q.x) &&
           intersect1d(a.p.y, a.q.y, b.p.y, b.q.y) &&
           vec(a.p, a.q, b.p) * vec(a.p, a.q, b.q) <= 0 &&
           vec(b.p, b.q, a.p) * vec(b.p, b.q, a.q) <= 0;
}
 
bool operator<(const seg& a, const seg& b)
{
    double x = max(min(a.p.x, a.q.x), min(b.p.x, b.q.x));
    return a.get_y(x) < b.get_y(x) - EPS;
}
 
struct event {
    double x;
    int tp, id;
 
    event() {}
    event(double x, int tp, int id) : x(x), tp(tp), id(id) {}
 
    bool operator<(const event& e) const {
        if (abs(x - e.x) > EPS)
            return x < e.x;
        return tp > e.tp;
    }
};
 
set<seg> s;
vector<set<seg>::iterator> where;
 
set<seg>::iterator prev(set<seg>::iterator it) {
    return it == s.begin() ? s.end() : --it;
}
 
set<seg>::iterator next(set<seg>::iterator it) {
    return ++it;
}
 
pair<int, int> solve(const vector<seg>& a) {
    int n = (int)a.size();
    vector<event> e;
    for (int i = 0; i < n; ++i) {
        e.push_back(event(min(a[i].p.x, a[i].q.x), +1, i));
        e.push_back(event(max(a[i].p.x, a[i].q.x), -1, i));
    }
    sort(e.begin(), e.end());
 
    s.clear();
    where.resize(a.size());
    for (size_t i = 0; i < e.size(); ++i) {
        int id = e[i].id;
        if (e[i].tp == +1) {
            set<seg>::iterator nxt = s.lower_bound(a[id]), prv = prev(nxt);
            if (nxt != s.end() && intersect(*nxt, a[id]))
                return make_pair(nxt->id, id);
            if (prv != s.end() && intersect(*prv, a[id]))
                return make_pair(prv->id, id);
            where[id] = s.insert(nxt, a[id]);
        } else {
            set<seg>::iterator nxt = next(where[id]), prv = prev(where[id]);
            if (nxt != s.end() && prv != s.end() && intersect(*nxt, *prv))
                return make_pair(prv->id, nxt->id);
            s.erase(where[id]);
        }
    }
 
    return make_pair(-1, -1);
}

La función principal aquí es solve(), que devuelve los segmentos que se intersectan si existen, o $(-1, -1)$ , si no hay intersecciones.

La comprobación de la intersección de dos segmentos se realiza con la función intersect (), usando un algoritmo basado en el área orientada del triángulo.

La cola de segmentos es la variable global s, un set<event>. Los iteradores que especifican la posición de cada segmento en la cola (para quitar segmentos de la cola de forma conveniente) se guardan en el arreglo global where.

También se introducen dos funciones auxiliares prev() y next(), que devuelven iteradores al elemento anterior y al siguiente (o end(), si uno no existe).

La constante EPS denota el error de comparar dos números reales (se usa principalmente al comprobar dos segmentos para intersección).

Problemas

TIMUS 1469 No Smoking!