From c9a6823af5463e7063bf9d2619f4b5e0ad8e785e Mon Sep 17 00:00:00 2001 From: =?utf8?q?Leonardo=20Fl=C3=B3rez-Valencia?= Date: Sat, 15 Oct 2016 12:56:49 -0500 Subject: [PATCH 1/1] Skeleton representation added. --- lib/Instances/cpPlugins_Paths.i | 3 + lib/cpExtensions/DataStructures/Graph.h | 51 +++--- lib/cpExtensions/DataStructures/Graph.hxx | 100 +++++++++--- lib/cpExtensions/DataStructures/Skeleton.h | 56 +++++++ lib/cpExtensions/DataStructures/Skeleton.hxx | 56 +++++++ .../Visualization/SkeletonToPolyData.cxx | 147 ++++++++++++++++++ .../Visualization/SkeletonToPolyData.h | 60 +++++++ 7 files changed, 423 insertions(+), 50 deletions(-) create mode 100644 lib/cpExtensions/DataStructures/Skeleton.h create mode 100644 lib/cpExtensions/DataStructures/Skeleton.hxx create mode 100644 lib/cpExtensions/Visualization/SkeletonToPolyData.cxx create mode 100644 lib/cpExtensions/Visualization/SkeletonToPolyData.h diff --git a/lib/Instances/cpPlugins_Paths.i b/lib/Instances/cpPlugins_Paths.i index 6868f79..a74da61 100644 --- a/lib/Instances/cpPlugins_Paths.i +++ b/lib/Instances/cpPlugins_Paths.i @@ -9,6 +9,8 @@ i cpPlugins_Images.h t cpExtensions/Algorithms/BezierCurveFunction t cpExtensions/DataStructures/PolyLineParametricPath +t cpExtensions/DataStructures/Skeleton +t cpExtensions/DataStructures/Graph t itkPath t itkParametricPath t itkPolyLineParametricPath @@ -27,5 +29,6 @@ c itk::Path< double, itk::ContinuousIndex< double, #process_dims# >, #process_di c itk::ParametricPath< #process_dims# > c itk::PolyLineParametricPath< #process_dims# > c cpExtensions::DataStructures::PolyLineParametricPath< #process_dims# > +c cpExtensions::DataStructures::Skeleton< #process_dims# > ** eof - $RCSfile$ diff --git a/lib/cpExtensions/DataStructures/Graph.h b/lib/cpExtensions/DataStructures/Graph.h index 1f8e939..ed2d6ae 100644 --- a/lib/cpExtensions/DataStructures/Graph.h +++ b/lib/cpExtensions/DataStructures/Graph.h @@ -14,11 +14,11 @@ namespace cpExtensions { /** \brief A generic graph with templated index types. * - * @param V Vertex type. - * @param C Cost type. - * @param I Index type (it should be a strict weak ordering type). + * @param _TVertex Vertex type. + * @param _TCost Cost type. + * @param _TIndex Index type (it should be a strict weak ordering type). */ - template< class V, class C, class I = unsigned long > + template< class _TVertex, class _TCost, class _TIndex = unsigned long, class _TIndexCompare = std::less< _TIndex > > class Graph : public itk::LightObject { @@ -28,15 +28,16 @@ namespace cpExtensions typedef itk::SmartPointer< Self > Pointer; typedef itk::SmartPointer< const Self > ConstPointer; - typedef V TVertex; - typedef C TCost; - typedef I TIndex; + typedef _TVertex TVertex; + typedef _TCost TCost; + typedef _TIndex TIndex; + typedef _TIndexCompare TIndexCompare; // Base types - typedef std::map< TIndex, TVertex > TVertices; - typedef std::vector< TCost > TEdges; - typedef std::map< TIndex, TEdges > TMatrixRow; - typedef std::map< TIndex, TMatrixRow > TMatrix; + typedef std::map< TIndex, TVertex, TIndexCompare > TVertices; + typedef std::vector< TCost > TEdges; + typedef std::map< TIndex, TEdges, TIndexCompare > TMatrixRow; + typedef std::map< TIndex, TMatrixRow, TIndexCompare > TMatrix; public: itkNewMacro( Self ); @@ -108,29 +109,27 @@ namespace cpExtensions /*! \brief Vertex manipulation methods. * Names are self-explanatory. */ - inline bool HasVertexIndex( const I& i ) const + inline bool HasVertexIndex( const TIndex& i ) const { return( this->m_Vertices.find( i ) != this->m_Vertices.end( ) ); } - inline void SetVertex( const I& index, V& vertex ) + inline void SetVertex( const TIndex& index, TVertex& vertex ) { this->m_Vertices[ index ] = vertex; } - inline V& GetVertex( const I& index ) + inline TVertex& GetVertex( const TIndex& index ) { return( this->m_Vertices[ index ] ); } - inline const V& GetVertex( const I& index ) const + inline const TVertex& GetVertex( const TIndex& index ) const { return( this->m_Vertices[ index ] ); } - bool RenameVertex( const I& old_index, const I& new_index ); - void RemoveVertex( const I& index ); + bool RenameVertex( const TIndex& old_index, const TIndex& new_index ); + void RemoveVertex( const TIndex& index ); /*! \brief Edge manipulation methods. * Names are self-explanatory. */ - inline void AddEdge( const I& orig, const I& dest, const C& cost ) + inline void AddEdge( const TIndex& orig, const TIndex& dest, const TCost& cost ) { this->m_Matrix[ orig ][ dest ].push_back( cost ); } - inline TEdges& GetEdges( const I& orig, const I& dest ) - { return( this->m_Matrix[ orig ][ dest ] ); } - inline const TEdges& GetEdges( const I& orig, const I& dest ) const - { return( this->m_Matrix[ orig ][ dest ] ); } - bool HasEdge( const I& orig, const I& dest ) const; - void RemoveEdge( const I& orig, const I& dest, const C& cost ); - void RemoveEdges( const I& orig, const I& dest ); + TEdges& GetEdges( const TIndex& orig, const TIndex& dest ); + const TEdges& GetEdges( const TIndex& orig, const TIndex& dest ) const; + bool HasEdge( const TIndex& orig, const TIndex& dest ) const; + void RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost ); + void RemoveEdges( const TIndex& orig, const TIndex& dest ); /*! \brief Returns graph's sinks. * @@ -138,7 +137,7 @@ namespace cpExtensions * * @return Sinks ordered by their index. */ - std::set< I > GetSinks( ) const; + std::set< TIndex, TIndexCompare > GetSinks( ) const; protected: Graph( ); diff --git a/lib/cpExtensions/DataStructures/Graph.hxx b/lib/cpExtensions/DataStructures/Graph.hxx index e794c45..62c6b75 100644 --- a/lib/cpExtensions/DataStructures/Graph.hxx +++ b/lib/cpExtensions/DataStructures/Graph.hxx @@ -2,8 +2,8 @@ #define __cpExtensions__DataStructures__Graph__hxx__ // ------------------------------------------------------------------------- -template< class V, class C, class I > -void cpExtensions::DataStructures::Graph< V, C, I >:: +template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare > +void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: Clear( ) { this->m_Vertices.clear( ); @@ -11,9 +11,9 @@ Clear( ) } // ------------------------------------------------------------------------- -template< class V, class C, class I > -bool cpExtensions::DataStructures::Graph< V, C, I >:: -RenameVertex( const I& old_index, const I& new_index ) +template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare > +bool cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: +RenameVertex( const TIndex& old_index, const TIndex& new_index ) { auto old_v = this->m_Vertices.find( old_index ); auto new_v = this->m_Vertices.find( new_index ); @@ -71,9 +71,9 @@ RenameVertex( const I& old_index, const I& new_index ) } // ------------------------------------------------------------------------- -template< class V, class C, class I > -void cpExtensions::DataStructures::Graph< V, C, I >:: -RemoveVertex( const I& index ) +template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare > +void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: +RemoveVertex( const TIndex& index ) { auto i = this->m_Vertices.find( index ); if( i != this->m_Vertices.end( ) ) @@ -109,9 +109,60 @@ RemoveVertex( const I& index ) } // ------------------------------------------------------------------------- -template< class V, class C, class I > -bool cpExtensions::DataStructures::Graph< V, C, I >:: -HasEdge( const I& orig, const I& dest ) const +template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare > +typename +cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: +TEdges& +cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: +GetEdges( const TIndex& orig, const TIndex& dest ) +{ + static TEdges null_edges; + auto o = this->m_Matrix.find( orig ); + if( o != this->m_Matrix.find( orig ) ) + { + auto d = o->second.find( dest ); + if( d == o->second.end( ) ) + { + null_edges.clear( ); + return( null_edges ); + } + else + return( d->second ); + } + else + { + null_edges.clear( ); + return( null_edges ); + + } // fi +} + +// ------------------------------------------------------------------------- +template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare > +const typename +cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: +TEdges& +cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: +GetEdges( const TIndex& orig, const TIndex& dest ) const +{ + static const TEdges null_edges; + auto o = this->m_Matrix.find( orig ); + if( o != this->m_Matrix.find( orig ) ) + { + auto d = o->second.find( dest ); + if( d == o->second.end( ) ) + return( null_edges ); + else + return( d->second ); + } + else + return( null_edges ); +} + +// ------------------------------------------------------------------------- +template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare > +bool cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: +HasEdge( const TIndex& orig, const TIndex& dest ) const { auto mIt = this->m_Matrix.find( orig ); if( mIt != this->m_Matrix.end( ) ) @@ -121,9 +172,9 @@ HasEdge( const I& orig, const I& dest ) const } // ------------------------------------------------------------------------- -template< class V, class C, class I > -void cpExtensions::DataStructures::Graph< V, C, I >:: -RemoveEdge( const I& orig, const I& dest, const C& cost ) +template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare > +void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: +RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost ) { auto m = this->m_Matrix.find( orig ); if( m != this->m_Matrix.end( ) ) @@ -158,9 +209,9 @@ RemoveEdge( const I& orig, const I& dest, const C& cost ) } // ------------------------------------------------------------------------- -template< class V, class C, class I > -void cpExtensions::DataStructures::Graph< V, C, I >:: -RemoveEdges( const I& orig, const I& dest ) +template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare > +void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: +RemoveEdges( const TIndex& orig, const TIndex& dest ) { auto m = this->m_Matrix.find( orig ); if( m != this->m_Matrix.end( ) ) @@ -179,11 +230,12 @@ RemoveEdges( const I& orig, const I& dest ) } // ------------------------------------------------------------------------- -template< class V, class C, class I > -std::set< I > cpExtensions::DataStructures::Graph< V, C, I >:: +template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare > +std::set< _TIndex, _TIndexCompare > +cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: GetSinks( ) const { - std::set< I > sinks; + std::set< _TIndex, _TIndexCompare > sinks; auto vIt = this->m_Vertices.begin( ); for( ; vIt != this->m_Vertices.end( ); ++vIt ) @@ -196,16 +248,16 @@ GetSinks( ) const } // ------------------------------------------------------------------------- -template< class V, class C, class I > -cpExtensions::DataStructures::Graph< V, C, I >:: +template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare > +cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: Graph( ) : Superclass( ) { } // ------------------------------------------------------------------------- -template< class V, class C, class I > -cpExtensions::DataStructures::Graph< V, C, I >:: +template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare > +cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >:: ~Graph( ) { } diff --git a/lib/cpExtensions/DataStructures/Skeleton.h b/lib/cpExtensions/DataStructures/Skeleton.h new file mode 100644 index 0000000..f30b601 --- /dev/null +++ b/lib/cpExtensions/DataStructures/Skeleton.h @@ -0,0 +1,56 @@ +#ifndef __cpExtensions__DataStructures__Skeleton__h__ +#define __cpExtensions__DataStructures__Skeleton__h__ + +#include +#include + +namespace cpExtensions +{ + namespace DataStructures + { + /** + */ + template< unsigned int _VDim > + class Skeleton + : public Graph< typename PolyLineParametricPath< _VDim >::TIndex, typename PolyLineParametricPath< _VDim >::Pointer, typename PolyLineParametricPath< _VDim >::TIndex, typename PolyLineParametricPath< _VDim >::TIndex::LexicographicCompare > + { + public: + typedef PolyLineParametricPath< _VDim > TPath; + typedef typename TPath::TIndex TIndex; + typedef typename TIndex::LexicographicCompare TIndexCompare; + typedef typename TPath::Pointer TPathPointer; + + typedef Graph< TIndex, TPathPointer, TIndex, TIndexCompare > Superclass; + typedef Skeleton Self; + typedef itk::SmartPointer< Self > Pointer; + typedef itk::SmartPointer< const Self > ConstPointer; + + public: + itkNewMacro( Self ); + itkTypeMacro( Skeleton, Graph ); + + public: + void AddBranch( TPath* path ); + const TPath* GetBranch( const TIndex& a, const TIndex& b ) const; + + protected: + Skeleton( ); + virtual ~Skeleton( ); + + private: + // Purposely not implemented + Skeleton( const Self& other ); + Self& operator=( const Self& other ); + }; + + } // ecapseman + +} // ecapseman + +#ifndef ITK_MANUAL_INSTANTIATION +# include +#endif // ITK_MANUAL_INSTANTIATION + +#endif // __cpExtensions__DataStructures__Skeleton__h__ + +// eof - $RCSfile$ diff --git a/lib/cpExtensions/DataStructures/Skeleton.hxx b/lib/cpExtensions/DataStructures/Skeleton.hxx new file mode 100644 index 0000000..ff00cb6 --- /dev/null +++ b/lib/cpExtensions/DataStructures/Skeleton.hxx @@ -0,0 +1,56 @@ +#ifndef __cpExtensions__DataStructures__Skeleton__hxx__ +#define __cpExtensions__DataStructures__Skeleton__hxx__ + +// ------------------------------------------------------------------------- +template< unsigned int _VDim > +void cpExtensions::DataStructures::Skeleton< _VDim >:: +AddBranch( TPath* path ) +{ + // Check inputs + if( path == NULL ) + return; + unsigned long size = path->GetSize( ); + if( size == 0 ) + return; + TIndex a = path->GetVertex( 0 ); + TIndex b = path->GetVertex( size - 1 ); + if( this->HasEdge( a, b ) ) + return; + + // Add path + this->AddEdge( a, b, path ); + this->AddEdge( b, a, path ); + // TODO: this->Modified( ); +} + +// ------------------------------------------------------------------------- +template< unsigned int _VDim > +const typename cpExtensions::DataStructures::Skeleton< _VDim >:: +TPath* cpExtensions::DataStructures::Skeleton< _VDim >:: +GetBranch( const TIndex& a, const TIndex& b ) const +{ + static const TPath* null_path = NULL; + if( this->HasEdge( a, b ) ) + return( this->GetEdges( a, b ).front( ) ); + else + return( null_path ); +} + +// ------------------------------------------------------------------------- +template< unsigned int _VDim > +cpExtensions::DataStructures::Skeleton< _VDim >:: +Skeleton( ) + : Superclass( ) +{ +} + +// ------------------------------------------------------------------------- +template< unsigned int _VDim > +cpExtensions::DataStructures::Skeleton< _VDim >:: +~Skeleton( ) +{ +} + +#endif // __cpExtensions__DataStructures__Skeleton__hxx__ + +// eof - $RCSfile$ diff --git a/lib/cpExtensions/Visualization/SkeletonToPolyData.cxx b/lib/cpExtensions/Visualization/SkeletonToPolyData.cxx new file mode 100644 index 0000000..8f5f4db --- /dev/null +++ b/lib/cpExtensions/Visualization/SkeletonToPolyData.cxx @@ -0,0 +1,147 @@ +#include + +#include +#include +#include +#include + +// ------------------------------------------------------------------------- +template< class _TSkeleton > +typename cpExtensions::Visualization::SkeletonToPolyData< _TSkeleton >:: +Self* cpExtensions::Visualization::SkeletonToPolyData< _TSkeleton >:: +New( ) +{ + return( new Self( ) ); +} + +// ------------------------------------------------------------------------- +template< class _TSkeleton > +const typename +cpExtensions::Visualization::SkeletonToPolyData< _TSkeleton >:: +TSkeleton* cpExtensions::Visualization::SkeletonToPolyData< _TSkeleton >:: +GetInput( ) const +{ + return( this->m_Skeleton ); +} + +// ------------------------------------------------------------------------- +template< class _TSkeleton > +void cpExtensions::Visualization::SkeletonToPolyData< _TSkeleton >:: +SetInput( const TSkeleton* sk ) +{ + if( this->m_Skeleton != sk ) + { + this->m_Skeleton = sk; + this->Modified( ); + + } // fi +} + +// ------------------------------------------------------------------------- +template< class _TSkeleton > +cpExtensions::Visualization::SkeletonToPolyData< _TSkeleton >:: +SkeletonToPolyData( ) + : vtkPolyDataAlgorithm( ), + m_Skeleton( NULL ) +{ + this->SetNumberOfInputPorts( 0 ); +} + +// ------------------------------------------------------------------------- +template< class _TSkeleton > +cpExtensions::Visualization::SkeletonToPolyData< _TSkeleton >:: +~SkeletonToPolyData( ) +{ +} + +// ------------------------------------------------------------------------- +template< class _TSkeleton > +int cpExtensions::Visualization::SkeletonToPolyData< _TSkeleton >:: +RequestData( + vtkInformation* information, + vtkInformationVector** input, + vtkInformationVector* output + ) +{ + typedef typename _TSkeleton::TPath _TPath; + static const unsigned int dim = _TPath::PathDimension; + + if( this->m_Skeleton == NULL ) + return( 0 ); + + // Get output + vtkInformation* info = output->GetInformationObject( 0 ); + vtkPolyData* out = vtkPolyData::SafeDownCast( + info->Get( vtkDataObject::DATA_OBJECT( ) ) + ); + + // Prepare data + out->SetPoints( vtkSmartPointer< vtkPoints >::New( ) ); + out->SetVerts( vtkSmartPointer< vtkCellArray >::New( ) ); + out->SetLines( vtkSmartPointer< vtkCellArray >::New( ) ); + out->SetPolys( vtkSmartPointer< vtkCellArray >::New( ) ); + out->SetStrips( vtkSmartPointer< vtkCellArray >::New( ) ); + vtkPoints* points = out->GetPoints( ); + vtkCellArray* lines = out->GetLines( ); + + // Assign all data + auto mIt = this->m_Skeleton->BeginEdgesRows( ); + for( ; mIt != this->m_Skeleton->EndEdgesRows( ); ++mIt ) + { + // TODO: mIt->first; --> this is the row index. <-- + auto rIt = mIt->second.begin( ); + for( ; rIt != mIt->second.end( ); ++rIt ) + { + // TODO: rIt->first; --> this is the column index. + auto eIt = rIt->second.begin( ); + for( ; eIt != rIt->second.end( ); ++eIt ) + { + _TPath* path = *eIt; + for( unsigned long i = 0; i < path->GetSize( ); ++i ) + { + auto pnt = path->GetPoint( i ); + if( dim == 1 ) + points->InsertNextPoint( pnt[ 0 ], 0, 0 ); + else if( dim == 2 ) + points->InsertNextPoint( pnt[ 0 ], pnt[ 1 ], 0 ); + else + points->InsertNextPoint( pnt[ 0 ], pnt[ 1 ], pnt[ 2 ] ); + if( i > 0 ) + { + lines->InsertNextCell( 2 ); + lines->InsertCellPoint( points->GetNumberOfPoints( ) - 1 ); + lines->InsertCellPoint( points->GetNumberOfPoints( ) ); + + } // fi + + } // rof + + } // rof + + } // rof + + } // rof + return( 1 ); +} + +// ------------------------------------------------------------------------- +template< class _TSkeleton > +int cpExtensions::Visualization::SkeletonToPolyData< _TSkeleton >:: +RequestInformation( + vtkInformation* information, + vtkInformationVector** input, + vtkInformationVector* output + ) +{ + return( 1 ); +} + +// ------------------------------------------------------------------------- +#include + +template class cpExtensions::Visualization::SkeletonToPolyData< cpExtensions::DataStructures::Skeleton< 1 > >; +template class cpExtensions::Visualization::SkeletonToPolyData< cpExtensions::DataStructures::Skeleton< 2 > >; +template class cpExtensions::Visualization::SkeletonToPolyData< cpExtensions::DataStructures::Skeleton< 3 > >; +template class cpExtensions::Visualization::SkeletonToPolyData< cpExtensions::DataStructures::Skeleton< 4 > >; + +// eof - $RCSfile$ diff --git a/lib/cpExtensions/Visualization/SkeletonToPolyData.h b/lib/cpExtensions/Visualization/SkeletonToPolyData.h new file mode 100644 index 0000000..1cef407 --- /dev/null +++ b/lib/cpExtensions/Visualization/SkeletonToPolyData.h @@ -0,0 +1,60 @@ +#ifndef __cpExtensions__Visualization__SkeletonToPolyData__h__ +#define __cpExtensions__Visualization__SkeletonToPolyData__h__ + +#include +#include + +namespace cpExtensions +{ + namespace Visualization + { + /** + */ + template< class _TSkeleton > + class cpExtensions_EXPORT SkeletonToPolyData + : public vtkPolyDataAlgorithm + { + public: + typedef SkeletonToPolyData Self; + typedef _TSkeleton TSkeleton; + + public: + vtkTypeMacro( SkeletonToPolyData, vtkPolyDataAlgorithm ); + + public: + static Self* New( ); + + const TSkeleton* GetInput( ) const; + void SetInput( const TSkeleton* sk ); + + protected: + SkeletonToPolyData( ); + virtual ~SkeletonToPolyData( ); + + int RequestData( + vtkInformation* information, + vtkInformationVector** input, + vtkInformationVector* output + ); + int RequestInformation( + vtkInformation* information, + vtkInformationVector** input, + vtkInformationVector* output + ); + + private: + // Purposely not implemented + SkeletonToPolyData( const Self& ); + void operator=( const Self& ); + + protected: + const TSkeleton* m_Skeleton; + }; + + } // ecapseman + +} // ecapseman + +#endif // __cpExtensions__Visualization__SkeletonToPolyData__h__ + +// eof - $RCSfile$ -- 2.47.0