Function runs_from_graph

src/svgfill/src/arrange_polygons.cpp:1117–1219

}

std::vector<LineRun> runs_from_graph(const CenterLineGraphData& graph, double angle_tol_deg = 3., double line_dist_tol = 0.15) {
    std::vector<bool> visited(graph.edges.size(), false);
    std::vector<LineRun> runs;

    for (size_t seed_ei = 0; seed_ei < graph.edges.size(); ++seed_ei) {
        if (visited[seed_ei]) {
            continue;
        }

        const auto& seed_edge = graph.edges[seed_ei];
        auto seed_a = graph.points_double[seed_edge.first];
        auto seed_b = graph.points_double[seed_edge.second];
        auto seed_dir = seed_b - seed_a;
        if (seed_dir.squared_length() < 1.e-18) {
            visited[seed_ei] = true;
            continue;
        }

        std::vector<size_t> queue = {seed_ei};
        std::set<size_t> component_edges;

        while (!queue.empty()) {
            auto ei = queue.back();
            queue.pop_back();
            if (!component_edges.insert(ei).second) {
                continue;
            }

            const auto& edge = graph.edges[ei];
            std::array<size_t, 2> vertices = {edge.first, edge.second};
            for (auto v : vertices) {
                for (auto ej : graph.incident_edges[v]) {
                    if (ej == ei || visited[ej] || component_edges.count(ej)) {
                        continue;
                    }
                    const auto& candidate = graph.edges[ej];
                    auto test_a = graph.points_double[candidate.first];
                    auto test_b = graph.points_double[candidate.second];
                    if (edge_supports_same_line(seed_a, seed_b, test_a, test_b, angle_tol_deg, line_dist_tol)) {
                        queue.push_back(ej);
                    }
                }
            }
        }

        for (auto ei : component_edges) {
            visited[ei] = true;
        }

        std::set<size_t> component_vertices;
        auto ref = unit(seed_dir);
        DDir direction_sum{0., 0.};
        double total_length = 0.;
        double weighted_width_sum = 0.;

        for (auto ei : component_edges) {
            const auto& edge = graph.edges[ei];
            component_vertices.insert(edge.first);