1 #ifndef __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
2 #define __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
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;
11 // -------------------------------------------------------------------------
12 template< class V, class C, class B >
13 void fpa::Base::MinimumSpanningTree< V, C, 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 C, class B >
64 void fpa::Base::MinimumSpanningTree< V, C, B >::
65 GetPath( std::vector< V >& path, const V& a, const V& b ) const
67 typename TDecorated::const_iterator aIt = this->Get( ).find( a );
68 typename TDecorated::const_iterator bIt = this->Get( ).find( b );
70 if( aIt == this->Get( ).end( ) || bIt == this->Get( ).end( ) )
73 short fa = aIt->second.second;
74 short fb = bIt->second.second;
78 std::vector< V > ap, bp;
83 typename std::vector< V >::const_reverse_iterator raIt, rbIt;
86 while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
92 if( raIt != ap.rbegin( ) ) --raIt;
93 if( rbIt != bp.rbegin( ) ) --rbIt;
96 typename std::vector< V >::const_iterator iaIt = ap.begin( );
97 for( ; iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
98 path.push_back( *iaIt );
101 for( ; rbIt != bp.rend( ); ++rbIt )
102 path.push_back( *rbIt );
106 // Use this->m_FrontPaths from Floyd-Warshall
107 if( this->m_FrontPaths[ fa ][ fb ] != Self::INF_VALUE )
109 // Compute front path
110 std::vector< long > fpath;
111 fpath.push_back( fa );
114 fa = this->m_FrontPaths[ fa ][ fb ];
115 fpath.push_back( fa );
119 // Continue only if both fronts are connected
120 unsigned int N = fpath.size( );
123 // First path: from start vertex to first collision
125 path, a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
128 // Intermediary paths
129 for( unsigned int i = 1; i < N - 1; ++i )
133 this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
134 this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
139 // Final path: from last collision to end point
142 this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
152 // -------------------------------------------------------------------------
153 template< class V, class C, class B >
154 template< class I, class P >
155 void fpa::Base::MinimumSpanningTree< V, C, B >::
157 std::vector< P >& path, const V& a, const V& b,
158 const I* image, unsigned int kernel
161 std::vector< V > vertices;
162 this->GetPath( vertices, a, b );
164 for( unsigned int i = 0; i < vertices.size( ); ++i )
167 image->TransformIndexToPhysicalPoint( vertices[ i ], p );
175 int k = int( kernel ) >> 1;
176 std::vector< P > lowpass_path;
177 for( unsigned int i = 0; i < path.size( ); ++i )
180 p.Fill( ( typename P::ValueType )( 0 ) );
182 for( int j = -k; j <= k; ++j )
184 int l = int( i ) + j;
185 if( l >= 0 && l < path.size( ) )
187 p += path[ l ].GetVectorFromOrigin( );
194 for( unsigned int d = 0; d < P::PointDimension; ++d )
195 p[ d ] /= ( typename P::ValueType )( c );
196 lowpass_path.push_back( p );
205 // -------------------------------------------------------------------------
206 template< class V, class C, class B >
207 fpa::Base::MinimumSpanningTree< V, C, B >::
208 MinimumSpanningTree( )
213 // -------------------------------------------------------------------------
214 template< class V, class C, class B >
215 fpa::Base::MinimumSpanningTree< V, C, B >::
216 ~MinimumSpanningTree( )
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
225 typename TDecorated::const_iterator dIt = this->Get( ).find( a );
226 if( dIt != this->Get( ).end( ) )
230 path.push_back( dIt->first );
231 dIt = this->Get( ).find( dIt->second.first );
233 } while( dIt->first != dIt->second.first && dIt != this->Get( ).end( ) );
235 if( dIt != this->Get( ).end( ) )
236 path.push_back( dIt->first );
241 #endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__