Function edge_slide

src/svgfill/src/arrange_polygons.cpp:1791–1861

}

void edge_slide(Graph2D<K>& G) {
    std::list<CGAL::Segment_2<K>> edges_to_remove, edges_to_insert;

    for (auto vit = G.vertices_begin(); vit != G.vertices_end(); ++vit) {
        auto& selected = vit->first;

        if (vit->second.size() >= 3) {
            for (auto vjt = vit->second.begin(); vjt != vit->second.end(); ++vjt) {
                auto& neighbour = *vjt;
                bool processed_neighbour = false;

                if (G.find(neighbour)->second.size() == 2 && !is_parallel_2degree_node(G.find(neighbour))) {
                    auto vkt = G.find(neighbour)->second.begin();
                    if (selected == *vkt) {
                        vkt++;
                    }
                    auto& other = *vkt;

                    if ((other - neighbour).squared_length() < (neighbour - selected).squared_length()) {
                        continue;
                    }

                    auto incoming = CGAL::Ray_2<K>(other, neighbour - other);
                    boost::optional<CGAL::Segment_2<K>> closest_neighbouring_segment;
                    boost::optional<CGAL::Point_2<K>> closest_intersection_point;
                    K::FT sq_distance_along_ray = std::numeric_limits<double>::infinity();

                    for (auto vlt = vit->second.begin(); vlt != vit->second.end(); ++vlt) {
                        auto& other_neighbour = *vlt;
                        if (vlt != vjt) {
                            CGAL::Segment_2<K> neighbouring_segment(selected, other_neighbour);
                            auto x = CGAL::intersection(incoming, neighbouring_segment);
                            if (x) {
                                if (auto* xp = variant_get<CGAL::Point_2<K>>(&*x)) {
                                    auto dist = ((*xp) - other).squared_length();
                                    if (dist < sq_distance_along_ray) {
                                        closest_neighbouring_segment = neighbouring_segment;
                                        closest_intersection_point = *xp;
                                        sq_distance_along_ray = dist;
                                    }
                                }
                            }
                        }
                    }

                    if (closest_intersection_point && closest_neighbouring_segment) {
                        edges_to_remove.push_back(*closest_neighbouring_segment);
                        edges_to_remove.push_back({neighbour, selected});
                        edges_to_insert.push_back({closest_neighbouring_segment->source(), *closest_intersection_point});
                        edges_to_insert.push_back({closest_neighbouring_segment->target(), *closest_intersection_point});
                        edges_to_insert.push_back({neighbour, *closest_intersection_point});

                        processed_neighbour = true;
                    }
                }
                if (processed_neighbour) {
                    // Only one neigbour is processed because otherwise we obtain intersections
                    break;