1 // =========================================================================
2 // @author Leonardo Florez Valencia
3 // @email florez-l@javeriana.edu.co
4 // =========================================================================
6 #ifndef __fpa__Base__Dijkstra__hxx__
7 #define __fpa__Base__Dijkstra__hxx__
9 // -------------------------------------------------------------------------
10 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
12 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
13 TMST* fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
14 GetMinimumSpanningTree( )
17 dynamic_cast< TMST* >(
18 this->itk::ProcessObject::GetOutput( this->m_MSTIndex )
23 // -------------------------------------------------------------------------
24 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
26 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
27 TMST* fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
28 GetMinimumSpanningTree( ) const
31 dynamic_cast< const TMST* >(
32 this->itk::ProcessObject::GetOutput( this->m_MSTIndex )
37 // -------------------------------------------------------------------------
38 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
40 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
42 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
43 GetIntensityFunctor( ) const
45 return( this->m_IntensityFunctor );
48 // -------------------------------------------------------------------------
49 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
51 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
53 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
54 GetVertexFunctor( ) const
56 return( this->m_VertexFunctor );
59 // -------------------------------------------------------------------------
60 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
61 void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
62 SetFunctor( TIntensityFunctor* functor )
64 if( this->m_IntensityFunctor.GetPointer( ) != functor )
66 this->m_IntensityFunctor = functor;
72 // -------------------------------------------------------------------------
73 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
74 void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
75 SetFunctor( TVertexFunctor* functor )
77 if( this->m_VertexFunctor.GetPointer( ) != functor )
79 this->m_VertexFunctor = functor;
85 // -------------------------------------------------------------------------
86 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
87 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
90 _TMarksInterface( this ),
91 _TSeedsInterface( this )
93 this->m_MSTIndex = this->GetNumberOfRequiredOutputs( );
94 this->SetNumberOfRequiredOutputs( this->m_MSTIndex + 1 );
95 this->itk::ProcessObject::SetNthOutput( this->m_MSTIndex, TMST::New( ) );
98 // -------------------------------------------------------------------------
99 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
100 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
105 // -------------------------------------------------------------------------
106 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
107 void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
111 this->_ConfigureOutputs( TOutputValue( 0 ) );
112 this->_InitMarks( this->GetNumberOfSeeds( ) );
113 TMST* mst = this->GetMinimumSpanningTree( );
116 std::vector< _TNode > q;
117 unsigned long frontId = 1;
118 for( TVertex seed: this->GetSeeds( ) )
119 q.push_back( _TNode( seed, seed, frontId++ ) );
122 while( q.size( ) > 0 )
124 // Get next candidate
125 std::pop_heap( q.begin( ), q.end( ) );
126 _TNode node = q.back( );
128 if( this->_IsMarked( node.Vertex ) )
130 this->_Mark( node.Vertex, node.FrontId );
132 // Ok, pixel lays inside region
133 this->_SetOutputValue( node.Vertex, node.Cost );
134 mst->SetParent( node.Vertex, node.Parent );
137 TVertices neighbors = this->_GetNeighbors( node.Vertex );
138 for( TVertex neigh: neighbors )
140 if( this->_IsMarked( neigh ) )
142 // Invoke stop at collisions
143 unsigned long nColl = this->_Collisions( node.Vertex, neigh );
145 this->StopAtOneFront( ) &&
146 this->GetNumberOfSeeds( ) > 1 &&
155 this->m_VertexFunctor->Evaluate( neigh, node.Vertex );
156 if( this->m_IntensityFunctor.IsNotNull( ) )
157 ncost = this->m_IntensityFunctor->Evaluate( ncost );
159 // This algorithm only supports positive values
160 if( ncost >= TOutputValue( 0 ) )
163 _TNode nn( neigh, node.Vertex, node.FrontId );
164 nn.Cost = node.Cost + ncost;
166 std::push_heap( q.begin( ), q.end( ) );
177 // Complete data into minimum spanning tree
179 mst->SetCollisions( this->m_Collisions );
180 for( TVertex seed: this->GetSeeds( ) )
181 mst->AddSeed( seed );
184 #endif // __fpa__Base__Dijkstra__hxx__