Encontrando a interseção de dois segmentos

Você recebe dois segmentos AB e CD, descritos como pares de seus pontos de extremidade/finais. Cada segmento pode ser um único ponto se seus pontos finais forem os mesmos. Você precisa encontrar a interseção desses segmentos, que podem estar vazios (se os segmentos não se cruzam), um único ponto ou segmento (se os segmentos se cruzarem/sobrepuserem, ou seja, uma interseção).

Solução

Podemos encontrar o ponto de interseção dos segmentos da mesma maneira que na interseção de linhas: reconstruindo as equações de linha a partir dos pontos finais dos segmentos e verificando se são paralelas.

Se as linhas não são paralelas, precisamos encontrar seu ponto de interseção e verificar se ele pertence aos dois segmentos (para fazer isso, é suficiente verificar se o ponto de interseção pertence a cada segmento projetado nos eixos X e Y). Nesse caso, a resposta será "sem interseção" ou o ponto único da interseção das linhas/retas.

O caso de linhas paralelas é um pouco mais complicado (o caso de um ou mais segmentos sendo um único ponto também pertence aqui). Nesse caso, precisamos verificar se os dois segmentos pertencem à mesma linha. Caso contrário, a resposta é "sem interseção". Se o fizerem, a resposta é a interseção dos segmentos pertencentes à mesma linha, que é obtida ordenando os pontos finais de ambos os segmentos na ordem crescente das determinadas coordenadas e tomando o "mais à direita dos pontos finais esquerdos" e o "ponto mais à esquerda dos pontos finais à direita".

No início do algoritmo, vamos adicionar uma caixa de seleção - é necessário para o caso em que os segmentos pertencem à mesma linha e (sendo uma verificação leve), permite que o algoritmo trabalhe mais rápido, em média, em testes aleatórios.

Implementação

Aqui está uma implementação incluindo todas as funções auxiliares para processamento de linhas e segmentos.

A função principal intersect retorna true se os segmentos tiverem uma interseção não vazia e armazena pontos de extremidade do segmento de interseção nos argumentos left e right. Se a resposta for um ponto único, os valores escritos para left e right serão os mesmos.

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);
    }
}