Function extractClosedLoops

source/MRMesh/MREdgePaths.cpp:417–459

}

std::vector<EdgeLoop> extractClosedLoops( const MeshTopology & topology, EdgeBitSet & edges )
{
    MR_TIMER;
    std::vector<EdgeLoop> res;
    for ( ;; )
    {
        UnionFind<VertId> vertComponents( topology.vertSize() );
        EdgeId loopEdge;
        for ( EdgeId e : edges )
        {
            const auto o = topology.org( e );
            const auto d = topology.dest( e );
            assert( o != d );
            if ( vertComponents.united( o, d ) )
            {
                loopEdge = e;
                break;
            }
            vertComponents.unite( o, d );
        }
        if ( !loopEdge.valid() )
            break;

        edges.reset( loopEdge );
        auto path = buildSmallestMetricPath( topology, [&]( EdgeId e )
        {
            return edges.test( e.sym() ) ? 1.0f : 1e5f; // sym() because inside buildSmallestMetricPath we search from finish to start
        }, topology.dest( loopEdge ), topology.org( loopEdge ) );
        assert ( !path.empty() );
        for ( EdgeId e : path )
        {
            assert( edges.test( e ) );
            edges.reset( e );
        }

        path.push_back( loopEdge );
        assert( isEdgeLoop( topology, path ) );

        res.push_back( std::move( path ) );
    }

    return res;
}

std::vector<EdgeLoop> extractClosedLoops( const MeshTopology & topology, const std::vector<EdgeId> & inEdges, EdgeBitSet * outNotLoopEdges )
{