Procure um par de segmentos que se cruzam

Fornecidos $n$ segmentos de linha em um plano. É necessário verificar se pelo menos dois deles se cruzam. Se a resposta for sim, print esse par de segmentos que se cruzam; basta escolher qualquer um deles entre várias respostas.

O algoritmo de bruta força é iterar sobre todos os pares de segmentos em $O(n^2)$ e verifique se cada par se cruza ou não. Este artigo descreve um algoritmo com o tempo de execução $O(n \log n)$, que é baseado no algoritmo sweep line.

Algoritmo

Desenhamos uma linha vertical mentalmente $x = -\infty$ e começar a mover essa linha para a direita. No curso de seu movimento, essa linha se encontrará com segmentos e, a cada vez que um segmento se cruza com a nossa linha, ele se cruza exatamente em um ponto (assumiremos que não existem segmentos verticais).

sweep line and line segment intersection

Portanto, para cada segmento, em algum momento, seu ponto aparecerá na linha de varredura(x); depois, com o movimento da linha, esse ponto se moverá e, finalmente, em algum momento, o segmento desaparecerá da linha.

Estamos interessados na ordem relativa dos segmentos ao longo do vertical. Namely, iremos armazenar uma lista de segmentos cruzando a sweep line em um dado momento, em que os segmentos serão ordenados pelas suas coordenadas-$y$ sobre a sweep line.

relative order of the segments across sweep line

Essa ordem é interessante porque os segmentos que se cruzam terão a mesma coordenada-$y$ pelo menos uma vez:

intersection point having same y-coordinate

Formularemos declarações importantes:

Para entender essas declarações, as seguintes observações são suficientes:

Assim, todo o algoritmo executará não mais do que $2n$ testes na interseção de um par de segmentos, e irá executar $O(n)$ operações com uma fila de segmentos ($O(1)$ operações no momento que um segmento aparecer e desaparecer).

O comportamento assintótico do algoritmo será portanto $O(n \log n)$.

Implementação

Apresentamos a implementação completa do algoritmo descrito:

const double EPS = 1E-9;

struct pt {     //coordenadas
    double x, y;
};

struct seg {   //segmentos
    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)      //overflow de operador
{
    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 {      //estrutura dos eventos      
    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;      //fila de segmentos
vector<set<seg>::iterator> where;  //iteradores com a posição de cada segmento na fila 

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

A função principal é solve(), que retorna o número de segmentos que se cruzam, ou $(-1, -1)$, se não existirem interseções.

A verificação da interseção de dois segmentos é realizada pela função intersect (), usando um algoritmo baseado na área orientada do triângulo.

A fila de segmentos é a variável global s, um set<event>. Iteradores que especificam a posição de cada segmento na fila (para remoção conveniente de segmentos da fila) são armazenados na array global where.

Duas funções auxiliares prev() e next() também são introduzidos, que retornam os iteradores para os elementos anteriores e posteriores(seguintes) (ou end(), se não existir tal elemento).

A constante EPS denota o erro de comparar dois números reais (é usado principalmente ao verificar a interseção de dois segmentos).