Function getNLargeByLengthComponents

source/MRMesh/MRPolylineComponents.cpp:143–210

template <typename V>
std::vector<UndirectedEdgeBitSet> getNLargeByLengthComponents( const Polyline<V>& polyline, const LargeByLengthComponentsSettings& settings )
{
    MR_TIMER;
    std::vector<UndirectedEdgeBitSet> res;

    assert( settings.maxLargeComponents > 0 );
    if ( settings.maxLargeComponents <= 0 )
    {
        if ( settings.numSmallerComponents )
            *settings.numSmallerComponents = -1; //unknown
        return res;
    }
    if ( settings.maxLargeComponents == 1 )
    {
        res.push_back( getLargestComponent( polyline, settings.minLength, settings.numSmallerComponents ) );
        return res;
    }

    auto unionFind = getUnionFindStructure( polyline.topology );
    const auto& roots = unionFind.roots();

    HashMap<UndirectedEdgeId, float> root2length;
    for ( auto ue : undirectedEdges( polyline.topology ) )
        root2length[roots[ue]] += polyline.edgeLength( EdgeId( ue ) );

    struct LengthRoot
    {
        float length = 0;
        UndirectedEdgeId root;
        constexpr auto operator <=>( const LengthRoot& ) const = default;
    };

    std::vector<LengthRoot> lengthRootVec;
    lengthRootVec.reserve( root2length.size() );
    // fill it with not too small components
    for ( const auto& [root, length] : root2length )
    {
        if ( length >= settings.minLength )
            lengthRootVec.push_back( { length, root } );
    }

    // leave at most given number of roots sorted in descending by area order
    if ( lengthRootVec.size() <= settings.maxLargeComponents )
    {
        if ( settings.numSmallerComponents )
            *settings.numSmallerComponents = 0;
        std::sort( lengthRootVec.begin(), lengthRootVec.end(), std::greater() );
    }
    else
    {
        if ( settings.numSmallerComponents )
            *settings.numSmallerComponents = int( lengthRootVec.size() - settings.maxLargeComponents );
        std::partial_sort( lengthRootVec.begin(), lengthRootVec.begin() + settings.maxLargeComponents, lengthRootVec.end(), std::greater() );
        lengthRootVec.resize( settings.maxLargeComponents );
    }

    res.resize( lengthRootVec.size() );
    ParallelFor( res, [&] ( size_t i )