#include <limits>
// -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-const typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
-TCollisions& fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+const typename
+fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+TCollisions&
+fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
GetCollisions( ) const
{
return( this->m_Collisions );
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
SetCollisions( const TCollisions& collisions )
{
static const unsigned long _inf =
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
ClearSeeds( )
{
this->m_Seeds.clear( );
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
AddSeed( const _TVertex& seed )
{
this->m_Seeds.push_back( seed );
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
-TVertices fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
-GetPath( const _TVertex& a ) const
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+GetPath( typename _TPath::Pointer& path, const _TVertex& a ) const
{
- TVertices path;
+ std::vector< _TVertex > vertices;
_TVertex it = a;
_TVertex p = this->GetParent( it );
while( it != p )
{
- path.push_front( it );
+ vertices.push_back( it );
it = p;
p = this->GetParent( it );
} // elihw
- path.push_front( it );
- return( path );
+ vertices.push_back( it );
+
+ if( path.IsNull( ) )
+ path = _TPath::New( );
+ for( auto v = vertices.begin( ); v != vertices.end( ); ++v )
+ path->AddVertex( *v );
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
-TVertices fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
-GetPath( const _TVertex& a, const _TVertex& b ) const
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+GetPath(
+ typename _TPath::Pointer& path, const _TVertex& a, const _TVertex& b
+ ) const
{
static const unsigned long _inf =
std::numeric_limits< unsigned long >::max( );
- TVertices path;
- TVertices pa = this->GetPath( a );
- TVertices pb = this->GetPath( b );
- if( pa.size( ) > 0 && pb.size( ) > 0 )
+ if( path.IsNull( ) )
+ path = _TPath::New( );
+ typename _TPath::Pointer pa, pb;
+ this->GetPath( pa, a );
+ this->GetPath( pb, b );
+ if( pa->GetSize( ) > 0 && pb->GetSize( ) > 0 )
{
// Find front identifiers
unsigned long ia = _inf, ib = _inf;
unsigned long N = this->m_Seeds.size( );
for( unsigned long i = 0; i < N; ++i )
{
- if( this->m_Seeds[ i ] == pa.front( ) )
+ if( this->m_Seeds[ i ] == pa->GetVertex( pa->GetSize( ) - 1 ) )
ia = i;
- if( this->m_Seeds[ i ] == pb.front( ) )
+ if( this->m_Seeds[ i ] == pb->GetVertex( pb->GetSize( ) - 1 ) )
ib = i;
} // rof
+ // Check if there is a front-jump between given seeds
if( ia != ib )
{
- // Use this->m_FrontPaths from Floyd-Warshall
- if( this->m_FrontPaths[ ia ][ ib ] < _inf )
+ // Compute front path
+ std::vector< long > fpath;
+ fpath.push_back( ia );
+ while( ia != ib )
{
- // Compute front path
- std::vector< long > fpath;
+ ia = this->m_FrontPaths[ ia ][ ib ];
fpath.push_back( ia );
- while( ia != ib )
- {
- ia = this->m_FrontPaths[ ia ][ ib ];
- fpath.push_back( ia );
- } // elihw
+ } // elihw
- // Continue only if both fronts are connected
- unsigned int N = fpath.size( );
- if( N > 0 )
+ // Continue only if both fronts are connected
+ unsigned int N = fpath.size( );
+ if( N > 0 )
+ {
+ // First path: from start vertex to first collision
+ this->GetPath(
+ path, a,
+ this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
+ );
+
+ // Intermediary paths
+ for( unsigned int i = 1; i < N - 1; ++i )
{
- // First path: from start vertex to first collision
- path = this->GetPath(
- a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
+ typename _TPath::Pointer ipath;
+ this->GetPath(
+ ipath,
+ this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
+ this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
);
+ for( long id = 0; id < ipath->GetSize( ); ++id )
+ path->AddVertex( ipath->GetVertex( id ) );
- // Intermediary paths
- for( unsigned int i = 1; i < N - 1; ++i )
- {
- TVertices ipath =
- this->GetPath(
- this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
- this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
- );
- path.insert( path.end( ), ipath.begin( ), ipath.end( ) );
-
- } // rof
-
- // Final path: from last collision to end point
- TVertices lpath =
- this->GetPath(
- this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
- );
- path.insert( path.end( ), lpath.begin( ), lpath.end( ) );
+ } // rof
- } // fi
+ // Final path: from last collision to end point
+ typename _TPath::Pointer lpath;
+ this->GetPath(
+ lpath,
+ this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
+ );
+ for( long id = 0; id < lpath->GetSize( ); ++id )
+ path->AddVertex( lpath->GetVertex( id ) );
} // fi
}
else
{
// Ignore common part: find common ancestor
- auto aIt = pa.begin( );
- auto bIt = pb.begin( );
- while( *aIt == *bIt && aIt != pa.end( ) && bIt != pb.end( ) )
+ long aIt = pa->GetSize( ) - 1;
+ long bIt = pb->GetSize( ) - 1;
+ bool cont = true;
+ while( aIt >= 0 && bIt >= 0 && cont )
{
- ++aIt;
- ++bIt;
+ cont = ( pa->GetVertex( aIt ) == pb->GetVertex( bIt ) );
+ aIt--;
+ bIt--;
} // elihw
+ aIt++;
+ bIt++;
// Glue both parts
- for( --aIt; aIt != pa.end( ); ++aIt )
- path.push_front( *aIt );
- for( ; bIt != pb.end( ); ++bIt )
- path.push_back( *bIt );
+ for( long cIt = 0; cIt <= aIt; ++cIt )
+ path->AddVertex( pa->GetVertex( cIt ) );
+ for( ; bIt >= 0; --bIt )
+ path->AddVertex( pb->GetVertex( bIt ) );
} // fi
} // fi
- return( path );
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
MinimumSpanningTree( )
: Superclass( )
{
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
~MinimumSpanningTree( )
{
}
git://git.creatis.insa-lyon.fr / FrontAlgorithms.git / blobdiff