lib/fpa/Base/MinimumSpanningTree.hxx

   1 #ifndef __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
   2 #define __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
   3
   4 #include <limits>
   5
   6 // -------------------------------------------------------------------------
   7 template< class V, class C, class B >
   8 const unsigned long fpa::Base::MinimumSpanningTree< V, C, B >::INF_VALUE =
   9   std::numeric_limits< unsigned long >::max( ) >> 1;
  10
  11 // -------------------------------------------------------------------------
  12 template< class V, class C, class B >
  13 void fpa::Base::MinimumSpanningTree< V, C, B >::
  14 SetCollisions( const TCollisions& collisions )
  15 {
  16   this->m_Collisions = collisions;
  17
  18   // Prepare fronts graph using Floyd-Warshall
  19   unsigned long nSeeds = this->m_Collisions.size( );
  20   _TMatrix dist( nSeeds, _TRow( nSeeds, Self::INF_VALUE ) );
  21   this->m_FrontPaths = dist;
  22
  23   for( unsigned long i = 0; i < nSeeds; ++i )
  24   {
  25     for( unsigned long j = 0; j < nSeeds; ++j )
  26     {
  27       if( this->m_Collisions[ i ][ j ].second )
  28       {
  29         dist[ i ][ j ] = 1;
  30         dist[ j ][ i ] = 1;
  31         this->m_FrontPaths[ i ][ j ] = j;
  32         this->m_FrontPaths[ j ][ i ] = i;
  33
  34       } // fi
  35
  36     } // rof
  37     dist[ i ][ i ] = 0;
  38     this->m_FrontPaths[ i ][ i ] = i;
  39
  40   } // rof
  41   for( unsigned long k = 0; k < nSeeds; ++k )
  42   {
  43     for( unsigned long i = 0; i < nSeeds; ++i )
  44     {
  45       for( unsigned long j = 0; j < nSeeds; ++j )
  46       {
  47         if( ( dist[ i ][ k ] + dist[ k ][ j ] ) < dist[ i ][ j ] )
  48         {
  49           dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ];
  50           this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
  51
  52         } // fi
  53
  54       } // rof
  55
  56     } // rof
  57
  58   } // rof
  59   this->Modified( );
  60 }
  61
  62 // -------------------------------------------------------------------------
  63 template< class V, class C, class B >
  64 void fpa::Base::MinimumSpanningTree< V, C, B >::
  65 GetPath( std::vector< V >& path, const V& a, const V& b ) const
  66 {
  67   typename TDecorated::const_iterator aIt = this->Get( ).find( a );
  68   typename TDecorated::const_iterator bIt = this->Get( ).find( b );
  69
  70   if( aIt == this->Get( ).end( ) || bIt == this->Get( ).end( ) )
  71     return;
  72
  73   short fa = aIt->second.second;
  74   short fb = bIt->second.second;
  75
  76   if( fa == fb )
  77   {
  78     std::vector< V > ap, bp;
  79     this->_Path( ap, a );
  80     this->_Path( bp, b );
  81
  82     // Ignore common part
  83     typename std::vector< V >::const_reverse_iterator raIt, rbIt;
  84     raIt = ap.rbegin( );
  85     rbIt = bp.rbegin( );
  86     while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
  87     {
  88       ++raIt;
  89       ++rbIt;
  90
  91     } // elihw
  92     if( raIt != ap.rbegin( ) ) --raIt;
  93     if( rbIt != bp.rbegin( ) ) --rbIt;
  94
  95     // Add part from a
  96     typename std::vector< V >::const_iterator iaIt = ap.begin( );
  97     for( ; iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
  98       path.push_back( *iaIt );
  99
 100     // Add part from b
 101     for( ; rbIt != bp.rend( ); ++rbIt )
 102       path.push_back( *rbIt );
 103   }
 104   else
 105   {
 106     // Use this->m_FrontPaths from Floyd-Warshall
 107     if( this->m_FrontPaths[ fa ][ fb ] != Self::INF_VALUE )
 108     {
 109       // Compute front path
 110       std::vector< long > fpath;
 111       fpath.push_back( fa );
 112       while( fa != fb )
 113       {
 114         fa = this->m_FrontPaths[ fa ][ fb ];
 115         fpath.push_back( fa );
 116
 117       } // elihw
 118
 119       // Continue only if both fronts are connected
 120       unsigned int N = fpath.size( );
 121       if( 0 < N )
 122       {
 123         // First path: from start vertex to first collision
 124         this->GetPath(
 125           path, a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
 126           );
 127
 128         // Intermediary paths
 129         for( unsigned int i = 1; i < N - 1; ++i )
 130         {
 131           this->GetPath(
 132             path,
 133             this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
 134             this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
 135             );
 136
 137         } // rof
 138
 139         // Final path: from last collision to end point
 140         this->GetPath(
 141           path,
 142           this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
 143           );
 144
 145       } // fi
 146
 147     } // fi
 148
 149   } // fi
 150 }
 151
 152 // -------------------------------------------------------------------------
 153 template< class V, class C, class B >
 154 template< class I, class P >
 155 void fpa::Base::MinimumSpanningTree< V, C, B >::
 156 GetPathFromImage(
 157   std::vector< P >& path, const V& a, const V& b,
 158   const I* image, unsigned int kernel
 159   ) const
 160 {
 161   std::vector< V > vertices;
 162   this->GetPath( vertices, a, b );
 163   path.clear( );
 164   for( unsigned int i = 0; i < vertices.size( ); ++i )
 165   {
 166     P p;
 167     image->TransformIndexToPhysicalPoint( vertices[ i ], p );
 168     path.push_back( p );
 169
 170   } // rof
 171
 172   // Lowpass filter
 173   if( kernel > 0 )
 174   {
 175     int k = int( kernel ) >> 1;
 176     std::vector< P > lowpass_path;
 177     for( unsigned int i = 0; i < path.size( ); ++i )
 178     {
 179       P p;
 180       p.Fill( ( typename P::ValueType )( 0 ) );
 181       unsigned int c = 0;
 182       for( int j = -k; j <= k; ++j )
 183       {
 184         int l = int( i ) + j;
 185         if( l >= 0 && l < path.size( ) )
 186         {
 187           p += path[ l ].GetVectorFromOrigin( );
 188           c++;
 189
 190         } // fi
 191
 192       } // rof
 193       if( c > 0 )
 194         for( unsigned int d = 0; d < P::PointDimension; ++d )
 195           p[ d ] /= ( typename P::ValueType )( c );
 196       lowpass_path.push_back( p );
 197
 198     } // rof
 199
 200     path = lowpass_path;
 201
 202   } // fi
 203 }
 204
 205 // -------------------------------------------------------------------------
 206 template< class V, class C, class B >
 207 fpa::Base::MinimumSpanningTree< V, C, B >::
 208 MinimumSpanningTree( )
 209   : Superclass( )
 210 {
 211 }
 212
 213 // -------------------------------------------------------------------------
 214 template< class V, class C, class B >
 215 fpa::Base::MinimumSpanningTree< V, C, B >::
 216 ~MinimumSpanningTree( )
 217 {
 218 }
 219
 220 // -------------------------------------------------------------------------
 221 template< class V, class C, class B >
 222 void fpa::Base::MinimumSpanningTree< V, C, B >::
 223 _Path( std::vector< V >& path, const V& a ) const
 224 {
 225   typename TDecorated::const_iterator dIt = this->Get( ).find( a );
 226   if( dIt != this->Get( ).end( ) )
 227   {
 228     do
 229     {
 230       path.push_back( dIt->first );
 231       dIt = this->Get( ).find( dIt->second.first );
 232
 233     } while( dIt->first != dIt->second.first && dIt != this->Get( ).end( ) );
 234
 235     if( dIt != this->Get( ).end( ) )
 236       path.push_back( dIt->first );
 237
 238   } // fi
 239 }
 240
 241 #endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
 242
 243 // eof - $RCSfile$