1 #ifndef __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
2 #define __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
6 // -------------------------------------------------------------------------
7 template< class V, class B >
8 const unsigned long fpa::Base::MinimumSpanningTree< V, B >::INF_VALUE =
9 std::numeric_limits< unsigned long >::max( ) >> 1;
11 // -------------------------------------------------------------------------
12 template< class V, class B >
13 void fpa::Base::MinimumSpanningTree< V, B >::
14 SetCollisions( const TCollisions& collisions )
16 this->m_Collisions = collisions;
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;
23 for( unsigned long i = 0; i < nSeeds; ++i )
25 for( unsigned long j = 0; j < nSeeds; ++j )
27 if( this->m_Collisions[ i ][ j ].second )
31 this->m_FrontPaths[ i ][ j ] = j;
32 this->m_FrontPaths[ j ][ i ] = i;
38 this->m_FrontPaths[ i ][ i ] = i;
41 for( unsigned long k = 0; k < nSeeds; ++k )
43 for( unsigned long i = 0; i < nSeeds; ++i )
45 for( unsigned long j = 0; j < nSeeds; ++j )
47 if( ( dist[ i ][ k ] + dist[ k ][ j ] ) < dist[ i ][ j ] )
49 dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ];
50 this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
62 // -------------------------------------------------------------------------
63 template< class V, class B >
64 std::vector< V > fpa::Base::MinimumSpanningTree< V, B >::
65 GetPath( const V& a, const V& b ) const
67 std::vector< V > path;
68 typename TDecorated::const_iterator aIt = this->Get( ).find( a );
69 typename TDecorated::const_iterator bIt = this->Get( ).find( b );
71 if( aIt == this->Get( ).end( ) || bIt == this->Get( ).end( ) )
74 short fa = aIt->second.second;
75 short fb = bIt->second.second;
79 std::vector< V > ap, bp;
84 typename std::vector< V >::const_reverse_iterator raIt, rbIt;
87 while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
93 if( raIt != ap.rbegin( ) ) --raIt;
94 if( rbIt != bp.rbegin( ) ) --rbIt;
97 typename std::vector< V >::const_iterator iaIt = ap.begin( );
98 for( ; iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
99 path.push_back( *iaIt );
102 for( ; rbIt != bp.rend( ); ++rbIt )
103 path.push_back( *rbIt );
107 // Use this->m_FrontPaths from Floyd-Warshall
108 if( this->m_FrontPaths[ fa ][ fb ] != Self::INF_VALUE )
110 // Compute front path
111 std::vector< long > fpath;
112 fpath.push_back( fa );
115 fa = this->m_FrontPaths[ fa ][ fb ];
116 fpath.push_back( fa );
120 // Continue only if both fronts are connected
121 unsigned int N = fpath.size( );
124 // First path: from start vertex to first collision
125 path = this->GetPath(
126 a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
129 // Intermediary paths
130 for( unsigned int i = 1; i < N - 1; ++i )
132 std::vector< V > ipath =
134 this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
135 this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
137 path.insert( path.end( ), ipath.begin( ), ipath.end( ) );
141 // Final path: from last collision to end point
142 std::vector< V > lpath =
144 this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
146 path.insert( path.end( ), lpath.begin( ), lpath.end( ) );
156 // -------------------------------------------------------------------------
157 template< class V, class B >
159 std::vector< typename I::PointType > fpa::Base::MinimumSpanningTree< V, B >::
161 const V& a, const V& b,
162 const I* image, unsigned int kernel
165 typedef typename I::PointType _P;
167 std::vector< _P > path;
168 std::vector< V > vertices = this->GetPath( a, b );
169 for( unsigned int i = 0; i < vertices.size( ); ++i )
172 image->TransformIndexToPhysicalPoint( vertices[ i ], p );
180 int k = int( kernel ) >> 1;
181 std::vector< _P > lowpass_path;
182 for( unsigned int i = 0; i < path.size( ); ++i )
185 p.Fill( ( typename _P::ValueType )( 0 ) );
187 for( int j = -k; j <= k; ++j )
189 int l = int( i ) + j;
190 if( l >= 0 && l < path.size( ) )
192 p += path[ l ].GetVectorFromOrigin( );
199 for( unsigned int d = 0; d < _P::PointDimension; ++d )
200 p[ d ] /= ( typename _P::ValueType )( c );
201 lowpass_path.push_back( p );
211 // -------------------------------------------------------------------------
212 template< class V, class B >
213 fpa::Base::MinimumSpanningTree< V, B >::
214 MinimumSpanningTree( )
219 // -------------------------------------------------------------------------
220 template< class V, class B >
221 fpa::Base::MinimumSpanningTree< V, B >::
222 ~MinimumSpanningTree( )
226 // -------------------------------------------------------------------------
227 template< class V, class B >
228 void fpa::Base::MinimumSpanningTree< V, B >::
229 _Path( std::vector< V >& path, const V& a ) const
231 typename TDecorated::const_iterator dIt = this->Get( ).find( a );
232 if( dIt != this->Get( ).end( ) )
236 path.push_back( dIt->first );
237 dIt = this->Get( ).find( dIt->second.first );
239 } while( dIt->first != dIt->second.first && dIt != this->Get( ).end( ) );
244 #endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__