Function getLargestComponent

source/MRMesh/MRPolylineComponents.cpp:216–270

template <typename V>
UndirectedEdgeBitSet getLargestComponent( const Polyline<V>& polyline, float minLength, int* numSmallerComponents )
{
    MR_TIMER;

    auto& topology = polyline.topology;
    auto unionFindStruct = getUnionFindStructure( topology );

    UndirectedEdgeBitSet region( topology.lastNotLoneUndirectedEdge() + 1 );
    for ( auto e : undirectedEdges( topology ) )
        region.set( e );

    UndirectedEdgeBitSet maxLengthComponent;
    const auto& allRoots = unionFindStruct.roots();
    auto [uniqueRootsMap, k] = getUniqueRootIds( allRoots, region );
    if ( k <= 0 )
    {
        if ( numSmallerComponents )
            *numSmallerComponents = 0;
        return maxLengthComponent;
    }

    auto maxLength = std::numeric_limits<float>::lowest();
    int maxI = 0;
    std::vector<float> lengths( k, 0.f );
    for ( auto e : region )
    {
        auto index = uniqueRootsMap[e];
        auto& length = lengths[index];
        length += polyline.edgeLength( EdgeId( e ) );
        if ( length > maxLength )
        {
            maxI = index;
            maxLength = length;
        }
    }

    if ( maxLength < minLength )
    {
        if ( numSmallerComponents )
            *numSmallerComponents = k;
        return maxLengthComponent;
    }
    if ( numSmallerComponents )
        *numSmallerComponents = k - 1;

    maxLengthComponent.resize( topology.lastNotLoneUndirectedEdge() + 1 );
    for ( auto e : region )
    {
        auto index = uniqueRootsMap[e];
        if ( index != maxI )
            continue;
        maxLengthComponent.set( e );
    }
    return maxLengthComponent;
}

template MRMESH_API UndirectedEdgeBitSet getLargestComponent<Vector2f>( const Polyline2& polyline, float minLength, int* numSmallerComponents );
template MRMESH_API UndirectedEdgeBitSet getLargestComponent<Vector3f>( const Polyline3& polyline, float minLength, int* numSmallerComponents );