ITK  4.1.0
Insight Segmentation and Registration Toolkit
itkVoronoiDiagram2D.h
Go to the documentation of this file.
00001 /*=========================================================================
00002  *
00003  *  Copyright Insight Software Consortium
00004  *
00005  *  Licensed under the Apache License, Version 2.0 (the "License");
00006  *  you may not use this file except in compliance with the License.
00007  *  You may obtain a copy of the License at
00008  *
00009  *         http://www.apache.org/licenses/LICENSE-2.0.txt
00010  *
00011  *  Unless required by applicable law or agreed to in writing, software
00012  *  distributed under the License is distributed on an "AS IS" BASIS,
00013  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  *  See the License for the specific language governing permissions and
00015  *  limitations under the License.
00016  *
00017  *=========================================================================*/
00018 #ifndef __itkVoronoiDiagram2D_h
00019 #define __itkVoronoiDiagram2D_h
00020 
00021 
00022 #include "itkMesh.h"
00023 #include "itkDefaultDynamicMeshTraits.h"
00024 #include "itkPolygonCell.h"
00025 #include <vector>
00026 
00027 #ifndef NULL
00028 #define NULL 0
00029 #endif
00030 
00031 namespace itk
00032 {
00050 template< typename TCoordType >
00051 class ITK_EXPORT VoronoiDiagram2D:
00052   public Mesh< TCoordType, 2,
00053                DefaultDynamicMeshTraits< TCoordType, 2, 2, TCoordType > >
00054 {
00055 public:
00057   typedef VoronoiDiagram2D                                                                Self;
00058   typedef Mesh< TCoordType, 2, DefaultDynamicMeshTraits< TCoordType, 2, 2, TCoordType > > Superclass;
00059   typedef SmartPointer< Self >                                                            Pointer;
00060   typedef SmartPointer< const Self >                                                      ConstPointer;
00061 
00063   itkNewMacro(Self);
00064 
00066   itkTypeMacro(VoronoiDiagram2D, Mesh);
00067 
00069   typedef DefaultDynamicMeshTraits< TCoordType, 2, 2, TCoordType > MeshTraits;
00070 
00072   itkStaticConstMacro(PointDimension, unsigned int,
00073                       MeshTraits::PointDimension);
00074   itkStaticConstMacro(MaxTopologicalDimension, unsigned int,
00075                       MeshTraits::MaxTopologicalDimension);
00077 
00079   typedef typename MeshTraits::PixelType
00080                                           PixelType;
00081   typedef typename MeshTraits::CoordRepType
00082                                           CoordRepType;
00083   typedef typename MeshTraits::InterpolationWeightType
00084                                           InterpolationWeightType;
00085   typedef typename MeshTraits::PointIdentifier
00086                                           PointIdentifier;
00087   typedef typename MeshTraits::CellIdentifier
00088                                           CellIdentifier;
00089   typedef typename MeshTraits::CellFeatureIdentifier
00090                                           CellFeatureIdentifier;
00091   typedef typename MeshTraits::PointType
00092                                           PointType;
00093   typedef typename MeshTraits::PointsContainer
00094                                           PointsContainer;
00095   typedef typename MeshTraits::CellTraits
00096                                           CellTraits;
00097   typedef typename MeshTraits::CellsContainer
00098                                           CellsContainer;
00099   typedef typename MeshTraits::PointCellLinksContainer
00100                                           PointCellLinksContainer;
00101   typedef typename MeshTraits::CellLinksContainer
00102                                           CellLinksContainer;
00103   typedef typename MeshTraits::PointDataContainer
00104                                           PointDataContainer;
00105   typedef typename MeshTraits::CellDataContainer
00106                                           CellDataContainer;
00107   typedef typename MeshTraits::CellAutoPointer
00108                                           genericCellPointer;
00109   typedef BoundingBox< PointIdentifier, itkGetStaticConstMacro(PointDimension), CoordRepType,
00110                        PointsContainer >  BoundingBoxType;
00111   typedef typename PointsContainer::Pointer
00112                                           PointsContainerPointer;
00113   typedef typename CellsContainer::Pointer
00114                                           CellsContainerPointer;
00115   typedef typename CellLinksContainer::Pointer
00116                                           CellLinksContainerPointer;
00117   typedef typename PointDataContainer::Pointer
00118                                           PointDataContainerPointer;
00119   typedef typename CellDataContainer::Pointer
00120                                           CellDataContainerPointer;
00121   typedef typename BoundingBoxType::Pointer
00122                                           BoundingBoxPointer;
00123   typedef typename PointsContainer::ConstIterator
00124                                           PointsContainerConstIterator;
00125   typedef typename PointsContainer::Iterator
00126                                           PointsContainerIterator;
00127   typedef typename CellsContainer::ConstIterator
00128                                           CellsContainerConstIterator;
00129   typedef typename CellsContainer::Iterator
00130                                           CellsContainerIterator;
00131   typedef typename CellLinksContainer::ConstIterator
00132                                           CellLinksContainerIterator;
00133   typedef typename PointDataContainer::ConstIterator
00134                                           PointDataContainerIterator;
00135   typedef typename CellDataContainer::ConstIterator
00136                                           CellDataContainerIterator;
00137   typedef typename PointCellLinksContainer::const_iterator
00138                                           PointCellLinksContainerIterator;
00139 
00140   typedef CellFeatureIdentifier                       CellFeatureCount;
00141   typedef typename Superclass::CellType               CellType;
00142   typedef typename Superclass::CellAutoPointer        CellAutoPointer;
00143   typedef PolygonCell< CellType >                     PolygonCellType;
00144   typedef Point< int, 2 >                             EdgeInfo;
00145   typedef std::deque< EdgeInfo >                      EdgeInfoDQ;
00146   typedef typename CellType::MultiVisitor             CellMultiVisitorType;
00147   typedef std::vector< PointType >                    SeedsType;
00148   typedef typename SeedsType::iterator                SeedsIterator;
00149   typedef LineCell< CellType >                        Edge;
00150   typedef typename Edge::SelfAutoPointer              EdgeAutoPointer;
00151   typedef std::list< PointType >                      PointList;
00152   typedef std::vector< int >                          INTvector;
00153   typedef typename INTvector::iterator                NeighborIdIterator;
00154   typedef PointsContainerIterator                     VertexIterator;
00156   itkGetConstMacro(NumberOfSeeds, unsigned int);
00157 
00160   void SetSeeds(int num, SeedsIterator begin);
00161 
00163   void SetBoundary(PointType vorsize);
00164 
00165   void SetOrigin(PointType vorsize);
00166 
00168   NeighborIdIterator NeighborIdsBegin(int seeds);
00169 
00170   NeighborIdIterator NeighborIdsEnd(int seeds);
00171 
00173   VertexIterator VertexBegin(void);
00174 
00175   VertexIterator VertexEnd(void);
00176 
00178   PointType GetSeed(int SeedID);
00179 
00181   void GetCellId(CellIdentifier cellId, CellAutoPointer &);
00182 
00184   void GetPoint(int pId, PointType *answer);
00185 
00186   class VoronoiEdge
00187   {
00188 public:
00189     PointType m_Left;
00190     PointType m_Right;
00191     int       m_LeftID;
00192     int       m_RightID;
00193     int       m_LineID;
00194     VoronoiEdge(){}
00195     ~VoronoiEdge(){}
00196   };
00197 
00199   typedef typename std::vector< VoronoiEdge >::iterator VoronoiEdgeIterator;
00200 
00202   VoronoiEdgeIterator EdgeBegin(void);
00203 
00204   VoronoiEdgeIterator EdgeEnd(void);
00205 
00207   EdgeInfo GetSeedsIDAroundEdge(VoronoiEdge *task);
00208 
00209 /********************************************************/
00210 
00211   void Reset();
00212 
00213   void InsertCells();
00214 
00215   void AddCellNeighbor(EdgeInfo x)
00216   {
00217     m_CellNeighborsID[x[0]].push_back(x[1]);
00218     m_CellNeighborsID[x[1]].push_back(x[0]);
00219   }
00220 
00221   void ClearRegion(int i)
00222   { m_VoronoiRegions[i]->ClearPoints(); }
00223   void VoronoiRegionAddPointId(int id, int x)
00224   { m_VoronoiRegions[id]->AddPointId(x); }
00225   void BuildEdge(int id)
00226   { m_VoronoiRegions[id]->BuildEdges(); }
00227 
00228   void LineListClear(){ m_LineList.clear(); }
00229   void EdgeListClear(){ m_EdgeList.clear(); }
00230   void VertexListClear()
00231   {
00232     if ( this->m_PointsContainer.IsNull() )
00233       {
00234       this->m_PointsContainer = PointsContainer::New();
00235       }
00236 
00237     this->m_PointsContainer->Initialize();
00238   }
00239 
00240   int LineListSize(){ return static_cast< int >( m_LineList.size() ); }
00241   int EdgeListSize(){ return static_cast< int >( m_EdgeList.size() ); }
00242   int VertexListSize(){ return static_cast< int >(this->m_PointsContainer->Size()); }
00243   void AddLine(EdgeInfo x){ m_LineList.push_back(x); }
00244   void AddEdge(VoronoiEdge x){ m_EdgeList.push_back(x); }
00245   void AddVert(PointType x){ this->m_PointsContainer->InsertElement(this->m_PointsContainer->Size(), x);}
00246   EdgeInfo GetLine(int id){ return m_LineList[id]; }
00247   VoronoiEdge GetEdge(int id){ return m_EdgeList[id]; }
00248   PointType GetVertex(int id){ return this-> m_PointsContainer->ElementAt(id); }
00249   EdgeInfo GetEdgeEnd(int id)
00250   {
00251     EdgeInfo x;
00252 
00253     x[0] = m_EdgeList[id].m_LeftID;
00254     x[1] = m_EdgeList[id].m_RightID;
00255     return x;
00256   }
00257 
00258   int GetEdgeLineID(int id){ return m_EdgeList[id].m_LineID; }
00259 protected:
00260   VoronoiDiagram2D();
00261   ~VoronoiDiagram2D();
00262   virtual void PrintSelf(std::ostream & os, Indent indent) const;
00263 
00264 private:
00265   VoronoiDiagram2D(const Self &); //purposely not implemented
00266   void operator=(const Self &);   //purposely not implemented
00267 
00268   SeedsType                         m_Seeds;
00269   unsigned int                      m_NumberOfSeeds;
00270   std::vector< PolygonCellType * >  m_VoronoiRegions;
00271   PointType                         m_VoronoiBoundary;
00272   PointType                         m_VoronoiBoundaryOrigin;
00273   std::vector< std::vector< int > > m_CellNeighborsID;
00274 
00275   std::vector< EdgeInfo >    m_LineList;
00276   std::vector< VoronoiEdge > m_EdgeList;
00277 }; // end class: VoronoiDiagram2D
00278 } // end namespace itk
00279 
00280 #ifndef ITK_MANUAL_INSTANTIATION
00281 #include "itkVoronoiDiagram2D.hxx"
00282 #endif
00283 
00284 #endif
00285