#include <limits>
// -------------------------------------------------------------------------
-template< class V, class B >
-const unsigned long fpa::Base::MinimumSpanningTree< V, B >::INF_VALUE =
- std::numeric_limits< unsigned long >::max( ) >> 1;
-
+template< class _TSuperclass, class _TVertex >
+const unsigned long fpa::Base::
+MinimumSpanningTree< _TSuperclass, _TVertex >::INF_VALUE =
+ std::numeric_limits< unsigned long >::max( );
+
// -------------------------------------------------------------------------
-template< class V, class B >
-void fpa::Base::MinimumSpanningTree< V, B >::
+template< class _TSuperclass, class _TVertex >
+void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
SetCollisions( const TCollisions& collisions )
{
+ // Prepare a front graph
this->m_Collisions = collisions;
-
- // Prepare fronts graph using Floyd-Warshall
unsigned long nSeeds = this->m_Collisions.size( );
_TMatrix dist( nSeeds, _TRow( nSeeds, Self::INF_VALUE ) );
this->m_FrontPaths = dist;
-
for( unsigned long i = 0; i < nSeeds; ++i )
{
for( unsigned long j = 0; j < nSeeds; ++j )
this->m_FrontPaths[ i ][ i ] = i;
} // rof
+
+ // Use Floyd-Warshall to compute all possible paths
for( unsigned long k = 0; k < nSeeds; ++k )
{
for( unsigned long i = 0; i < nSeeds; ++i )
}
// -------------------------------------------------------------------------
-template< class V, class B >
-std::vector< V > fpa::Base::MinimumSpanningTree< V, B >::
-GetPath( const V& a, const V& b ) const
+template< class _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TVertices fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetPath( const TVertex& a ) const
{
- std::vector< V > path;
- typename TDecorated::const_iterator aIt = this->Get( ).find( a );
- typename TDecorated::const_iterator bIt = this->Get( ).find( b );
+ TVertices path;
+ if( this->_HasVertex( a ) )
+ this->_Path( path, a );
+ return( path );
+}
- if( aIt == this->Get( ).end( ) || bIt == this->Get( ).end( ) )
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TVertices fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetPath( const TVertex& a, const TVertex& b ) const
+{
+ TVertices path;
+
+ // Check existence
+ if( !this->_HasVertex( a ) || !this->_HasVertex( b ) )
return( path );
- short fa = aIt->second.second;
- short fb = bIt->second.second;
+ // Get front ids
+ short fa = this->_FrontId( a );
+ short fb = this->_FrontId( b );
if( fa == fb )
{
- std::vector< V > ap, bp;
+ // Get paths
+ TVertices ap, bp;
this->_Path( ap, a );
this->_Path( bp, b );
- // Ignore common part
- typename std::vector< V >::const_reverse_iterator raIt, rbIt;
- raIt = ap.rbegin( );
- rbIt = bp.rbegin( );
+ // Ignore common part: find common ancestor
+ auto raIt = ap.rbegin( );
+ auto rbIt = bp.rbegin( );
while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
{
++raIt;
if( rbIt != bp.rbegin( ) ) --rbIt;
// Add part from a
- typename std::vector< V >::const_iterator iaIt = ap.begin( );
- for( ; iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
+ for( auto iaIt = ap.begin( ); iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
path.push_back( *iaIt );
// Add part from b
else
{
// Use this->m_FrontPaths from Floyd-Warshall
- if( this->m_FrontPaths[ fa ][ fb ] != Self::INF_VALUE )
+ if( this->m_FrontPaths[ fa ][ fb ] < Self::INF_VALUE )
{
// Compute front path
std::vector< long > fpath;
// Continue only if both fronts are connected
unsigned int N = fpath.size( );
- if( 0 < N )
+ if( N > 0 )
{
// First path: from start vertex to first collision
path = this->GetPath(
// Intermediary paths
for( unsigned int i = 1; i < N - 1; ++i )
{
- std::vector< V > ipath =
+ TVertices ipath =
this->GetPath(
this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
} // rof
// Final path: from last collision to end point
- std::vector< V > lpath =
+ TVertices lpath =
this->GetPath(
this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
);
}
// -------------------------------------------------------------------------
-template< class V, class B >
-template< class I >
-std::vector< typename I::PointType > fpa::Base::MinimumSpanningTree< V, B >::
-GetPathFromImage(
- const V& a, const V& b,
- const I* image, unsigned int kernel
- ) const
+template< class _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TPoints fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetEuclideanPath( const TVertex& a ) const
{
- typedef typename I::PointType _P;
-
- std::vector< _P > path;
- std::vector< V > vertices = this->GetPath( a, b );
- for( unsigned int i = 0; i < vertices.size( ); ++i )
- {
- _P p;
- image->TransformIndexToPhysicalPoint( vertices[ i ], p );
- path.push_back( p );
-
- } // rof
-
- // Lowpass filter
- if( kernel > 0 )
- {
- int k = int( kernel ) >> 1;
- std::vector< _P > lowpass_path;
- for( unsigned int i = 0; i < path.size( ); ++i )
- {
- _P p;
- p.Fill( ( typename _P::ValueType )( 0 ) );
- unsigned int c = 0;
- for( int j = -k; j <= k; ++j )
- {
- int l = int( i ) + j;
- if( l >= 0 && l < path.size( ) )
- {
- p += path[ l ].GetVectorFromOrigin( );
- c++;
-
- } // fi
-
- } // rof
- if( c > 0 )
- for( unsigned int d = 0; d < _P::PointDimension; ++d )
- p[ d ] /= ( typename _P::ValueType )( c );
- lowpass_path.push_back( p );
-
- } // rof
-
- path = lowpass_path;
+ TPoints points;
+ return( points );
+}
- } // fi
- return( path );
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TPoints fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetEuclideanPath( const TVertex& a, const TVertex& b ) const
+{
+ TPoints points;
+ return( points );
}
// -------------------------------------------------------------------------
-template< class V, class B >
-fpa::Base::MinimumSpanningTree< V, B >::
-MinimumSpanningTree( )
- : Superclass( )
+template< class _TSuperclass, class _TVertex >
+bool fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+IsDefinedInEuclideanSpace( ) const
{
+ return( false );
}
// -------------------------------------------------------------------------
-template< class V, class B >
-fpa::Base::MinimumSpanningTree< V, B >::
-~MinimumSpanningTree( )
+template< class _TSuperclass, class _TVertex >
+void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+SetNode(
+ const TVertex& v, const TVertex& p,
+ const short& fid, const double& cost
+ )
{
+ typedef typename TNodeQueue::value_type _TNodeQueueValue;
+ if( this->m_FillNodeQueue )
+ this->m_NodeQueue.insert( _TNodeQueueValue( cost, v ) );
}
// -------------------------------------------------------------------------
-template< class V, class B >
-void fpa::Base::MinimumSpanningTree< V, B >::
-_Path( std::vector< V >& path, const V& a ) const
+template< class _TSuperclass, class _TVertex >
+void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+Clear( )
{
- typename TDecorated::const_iterator dIt = this->Get( ).find( a );
- if( dIt != this->Get( ).end( ) )
- {
- do
- {
- path.push_back( dIt->first );
- dIt = this->Get( ).find( dIt->second.first );
+ this->m_NodeQueue.clear( );
+}
- } while( dIt->first != dIt->second.first && dIt != this->Get( ).end( ) );
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+MinimumSpanningTree( )
+ : Superclass( ),
+ m_FillNodeQueue( false )
+{
+}
- } // fi
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+~MinimumSpanningTree( )
+{
}
#endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
git://git.creatis.insa-lyon.fr / FrontAlgorithms.git / blobdiff