ホーム > libalgo

線分アレンジメント

概要

線分の集合を入力とし,任意の2線分の交点を頂点とし,頂点間に辺が存在する $\leftrightarrow$ 両方を含む線分が存在するという条件を満たすグラフを作ります.

実装

//@require intersection.cc
Graph segment_arrangement(const std::vector<L> &ss, std::vector<P> &ps) {
    for (int i = 0; i < (int)ss.size(); ++i) {  // O(n^2)
        ps.push_back(ss[i][0]);
        ps.push_back(ss[i][1]);
        for (int j = i + 1; j < (int)ss.size(); ++j)
            if (intersectSS(ss[i], ss[j])) ps.push_back(crosspointLL(ss[i], ss[j]));
    }
    std::sort(ps.begin(), ps.end());
    ps.erase(std::unique(ps.begin(), ps.end()), ps.end());
    Graph g(ps.size());
    for (int i = 0; i < (int)ss.size(); ++i) {
        std::vector<std::pair<double, int>> list;
        for (int j = 0; j < (int)ps.size(); ++j)
            if (intersectSP(ss[i], ps[j]))
                list.push_back(std::make_pair(norm(ss[i][0] - ps[j]), j));
        std::sort(list.begin(), list.end());
        for (int j = 0; j + 1 < (int)list.size(); ++j) {
            int a = list[j].second, b = list[j + 1].second;
            Weight len = abs(ps[a] - ps[b]);
            add_edge(g, a, b, len);
        }
    }
    return g;
}

参考文献

Spagetti Source