Encontrar la intersección de dos segmentos

Se dan dos segmentos AB y CD, descritos como pares de sus extremos. Cada segmento puede ser un solo punto si sus extremos coinciden. Hay que encontrar la intersección de estos segmentos, que puede ser vacía (si los segmentos no se intersectan), un solo punto o un segmento (si los segmentos dados se superponen).

Solución

Podemos encontrar el punto de intersección de los segmentos de la misma forma que la intersección de rectas: reconstruir las ecuaciones de las rectas a partir de los extremos de los segmentos y comprobar si son paralelas.

Si las rectas no son paralelas, hay que encontrar su punto de intersección y comprobar si pertenece a ambos segmentos (para ello basta verificar que el punto de intersección pertenece a cada segmento proyectado sobre los ejes X e Y). En este caso la respuesta será o bien “sin intersección” o el único punto de intersección de las rectas.

El caso de rectas paralelas es un poco más complicado (el caso de uno o más segmentos que son un solo punto también pertenece aquí). En este caso hay que comprobar que ambos segmentos pertenecen a la misma recta. Si no, la respuesta es “sin intersección”. Si sí, la respuesta es la intersección de los segmentos que pertenecen a la misma recta, que se obtiene ordenando los extremos de ambos segmentos en orden creciente de cierta coordenada y tomando el más a la derecha de los extremos izquierdos y el más a la izquierda de los extremos derechos.

Si ambos segmentos son puntos aislados, estos puntos tienen que ser idénticos, y tiene sentido realizar esta comprobación por separado.

Al comienzo del algoritmo añadamos una comprobación de caja envolvente (bounding box): es necesaria para el caso en que los segmentos pertenecen a la misma recta, y (al ser una comprobación ligera) permite que el algoritmo funcione más rápido en promedio sobre tests aleatorios.

Implementación

Aquí está la implementación, incluyendo todas las funciones auxiliares para el procesamiento de rectas y segmentos.

La función principal intersect devuelve true si los segmentos tienen una intersección no vacía, y guarda los extremos del segmento de intersección en los argumentos left y right. Si la respuesta es un solo punto, los valores escritos en left y right serán iguales.

const double EPS = 1E-9;

struct pt {
    double x, y;

    bool operator<(const pt& p) const
    {
        return x < p.x - EPS || (abs(x - p.x) < EPS && y < p.y - EPS);
    }
};

struct line {
    double a, b, c;

    line() {}
    line(pt p, pt q)
    {
        a = p.y - q.y;
        b = q.x - p.x;
        c = -a * p.x - b * p.y;
        norm();
    }

    void norm()
    {
        double z = sqrt(a * a + b * b);
        if (abs(z) > EPS)
            a /= z, b /= z, c /= z;
    }

    double dist(pt p) const { return a * p.x + b * p.y + c; }
};

double det(double a, double b, double c, double d)
{
    return a * d - b * c;
}

inline bool betw(double l, double r, double x)
{
    return min(l, r) <= x + EPS && x <= max(l, r) + EPS;
}

inline bool intersect_1d(double a, double b, double c, double d)
{
    if (a > b)
        swap(a, b);
    if (c > d)
        swap(c, d);
    return max(a, c) <= min(b, d) + EPS;
}

bool intersect(pt a, pt b, pt c, pt d, pt& left, pt& right)
{
    if (!intersect_1d(a.x, b.x, c.x, d.x) || !intersect_1d(a.y, b.y, c.y, d.y))
        return false;
    line m(a, b);
    line n(c, d);
    double zn = det(m.a, m.b, n.a, n.b);
    if (abs(zn) < EPS) {
        if (abs(m.dist(c)) > EPS || abs(n.dist(a)) > EPS)
            return false;
        if (b < a)
            swap(a, b);
        if (d < c)
            swap(c, d);
        left = max(a, c);
        right = min(b, d);
        return true;
    } else {
        left.x = right.x = -det(m.c, m.b, n.c, n.b) / zn;
        left.y = right.y = -det(m.a, m.c, n.a, n.c) / zn;
        return betw(a.x, b.x, left.x) && betw(a.y, b.y, left.y) &&
               betw(c.x, d.x, left.x) && betw(c.y, d.y, left.y);
    }
}