Method SegmentLookup

src/svgfill/src/arrange_polygons.cpp:674–690

    typedef std::vector<Polygon_2>::const_iterator PolygonIt;

    SegmentLookup(const std::vector<Polygon_2>& polygons)
        : polygons_ref_(polygons) 
    {
        // Unfortunately CGAL does not seem to have a ready to use aabb primitive for segments in 2D,
        // so we have to use 3D segments and aabb tree for 2D polygons.
        for (auto it = polygons.begin(); it != polygons.end(); ++it) {
            for (auto eit = it->edges_begin(); eit != it->edges_end(); ++eit) {
                CGAL::Segment_3<K> seg3d(
                    CGAL::Point_3<K>(eit->source().x(), eit->source().y(), 0),
                    CGAL::Point_3<K>(eit->target().x(), eit->target().y(), 0));
                all_segs.push_back(seg3d);
                seg_to_poly[&all_segs.back()] = it;
            }
        }
        tree_ = Tree(all_segs.begin(), all_segs.end());
        tree_.accelerate_distance_queries();
    }

    // This part is the most computationally expensive. Caching effectively halves the lookup time here, since every vertex on the subdivided corridor mesh has on average two outgoing edges.
    PolygonIt input_polygon_boundary(const Point_2& p, double tol = 1e-5) {