ITK  5.0.0
Insight Segmentation and Registration Toolkit
itkVoronoiDiagram2D.h
Go to the documentation of this file.
1 /*=========================================================================
2  *
3  * Copyright Insight Software Consortium
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0.txt
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  *
17  *=========================================================================*/
18 #ifndef itkVoronoiDiagram2D_h
19 #define itkVoronoiDiagram2D_h
20 
21 
22 #include "itkMesh.h"
24 #include "itkPolygonCell.h"
25 #include <vector>
26 
27 namespace itk
28 {
46 template< typename TCoordType >
47 class ITK_TEMPLATE_EXPORT VoronoiDiagram2D:
48  public Mesh< TCoordType, 2,
49  DefaultDynamicMeshTraits< TCoordType, 2, 2, TCoordType > >
50 {
51 public:
52  ITK_DISALLOW_COPY_AND_ASSIGN(VoronoiDiagram2D);
53 
59 
61  itkNewMacro(Self);
62 
64  itkTypeMacro(VoronoiDiagram2D, Mesh);
65 
68 
70  static constexpr unsigned int PointDimension = MeshTraits::PointDimension;
71  static constexpr unsigned int MaxTopologicalDimension = MeshTraits::MaxTopologicalDimension;
72 
74  using PixelType = typename MeshTraits::PixelType;
80  using PointType = typename MeshTraits::PointType;
89  using BoundingBoxType = BoundingBox< PointIdentifier, Self::PointDimension, CoordRepType,
91  using PointsContainerPointer = typename PointsContainer::Pointer;
92  using CellsContainerPointer = typename CellsContainer::Pointer;
93  using CellLinksContainerPointer = typename CellLinksContainer::Pointer;
94  using PointDataContainerPointer = typename PointDataContainer::Pointer;
95  using CellDataContainerPointer = typename CellDataContainer::Pointer;
97  using PointsContainerConstIterator = typename PointsContainer::ConstIterator;
98  using PointsContainerIterator = typename PointsContainer::Iterator;
99  using CellsContainerConstIterator = typename CellsContainer::ConstIterator;
100  using CellsContainerIterator = typename CellsContainer::Iterator;
101  using CellLinksContainerIterator = typename CellLinksContainer::ConstIterator;
102  using PointDataContainerIterator = typename PointDataContainer::ConstIterator;
103  using CellDataContainerIterator = typename CellDataContainer::ConstIterator;
104  using PointCellLinksContainerIterator = typename PointCellLinksContainer::const_iterator;
105 
107  using CellType = typename Superclass::CellType;
108  using CellAutoPointer = typename Superclass::CellAutoPointer;
111  using EdgeInfoDQ = std::deque< EdgeInfo >;
112  using CellMultiVisitorType = typename CellType::MultiVisitor;
113  using SeedsType = std::vector< PointType >;
114  using SeedsIterator = typename SeedsType::iterator;
116  using EdgeAutoPointer = typename Edge::SelfAutoPointer;
117  using PointList = std::list< PointType >;
118  using INTvector = std::vector< int >;
119  using NeighborIdIterator = typename INTvector::iterator;
122  itkGetConstMacro(NumberOfSeeds, unsigned int);
123 
126  void SetSeeds(int num, SeedsIterator begin);
127 
129  void SetBoundary(PointType vorsize);
130 
131  void SetOrigin(PointType vorsize);
132 
134  NeighborIdIterator NeighborIdsBegin(int seeds);
135 
136  NeighborIdIterator NeighborIdsEnd(int seeds);
137 
139  VertexIterator VertexBegin();
140 
141  VertexIterator VertexEnd();
142 
144  PointType GetSeed(int SeedID);
145 
147  void GetCellId(CellIdentifier cellId, CellAutoPointer &);
148 
150  void GetPoint(int pId, PointType *answer);
151 
153  {
154 public:
157  int m_LeftID;
159  int m_LineID;
160  VoronoiEdge()= default;
161  ~VoronoiEdge()= default;
162  };
163 
165  using VoronoiEdgeIterator = typename std::vector< VoronoiEdge >::iterator;
166 
168  VoronoiEdgeIterator EdgeBegin();
169 
170  VoronoiEdgeIterator EdgeEnd();
171 
173  EdgeInfo GetSeedsIDAroundEdge(VoronoiEdge *task);
174 
175 /********************************************************/
176 
177  void Reset();
178 
179  void InsertCells();
180 
182  {
183  m_CellNeighborsID[x[0]].push_back(x[1]);
184  m_CellNeighborsID[x[1]].push_back(x[0]);
185  }
186 
187  void ClearRegion(int i)
188  {
189  m_VoronoiRegions[i]->ClearPoints();
190  }
191 
192  void VoronoiRegionAddPointId(int id, int x)
193  {
194  m_VoronoiRegions[id]->AddPointId(x);
195  }
196 
197  void BuildEdge(int id)
198  {
199  m_VoronoiRegions[id]->BuildEdges();
200  }
201 
203  {
204  m_LineList.clear();
205  }
206 
208  {
209  m_EdgeList.clear();
210  }
211 
213  {
214  if ( this->m_PointsContainer.IsNull() )
215  {
216  this->m_PointsContainer = PointsContainer::New();
217  }
218 
219  this->m_PointsContainer->Initialize();
220  }
221 
223  {
224  return static_cast< int >( m_LineList.size() );
225  }
226 
228  {
229  return static_cast< int >( m_EdgeList.size() );
230  }
231 
233  {
234  return static_cast< int >(this->m_PointsContainer->Size());
235  }
236 
238  {
239  m_LineList.push_back(x);
240  }
241 
243  {
244  m_EdgeList.push_back(x);
245  }
246 
248  {
249  this->m_PointsContainer->InsertElement(this->m_PointsContainer->Size(), x);
250  }
251 
253  {
254  return m_LineList[id];
255  }
256 
258  {
259  return m_EdgeList[id];
260  }
261 
263  {
264  return this-> m_PointsContainer->ElementAt(id);
265  }
266 
268  {
269  EdgeInfo x;
270 
271  x[0] = m_EdgeList[id].m_LeftID;
272  x[1] = m_EdgeList[id].m_RightID;
273  return x;
274  }
275 
276  int GetEdgeLineID(int id)
277  {
278  return m_EdgeList[id].m_LineID;
279  }
280 
281 protected:
283  ~VoronoiDiagram2D() override = default;
284  void PrintSelf(std::ostream & os, Indent indent) const override;
285 
286 private:
288  unsigned int m_NumberOfSeeds;
289  std::vector< PolygonCellType * > m_VoronoiRegions;
292  std::vector< std::vector< int > > m_CellNeighborsID;
293 
294  std::vector< EdgeInfo > m_LineList;
295  std::vector< VoronoiEdge > m_EdgeList;
296 };
297 
298 } // end namespace itk
299 
300 #ifndef ITK_MANUAL_INSTANTIATION
301 #include "itkVoronoiDiagram2D.hxx"
302 #endif
303 
304 #endif
typename MeshTraits::PointDataContainer PointDataContainer
typename CellType::CellAutoPointer CellAutoPointer
typename PointsContainer::Pointer PointsContainerPointer
typename MeshTraits::CellIdentifier CellIdentifier
typename MeshTraits::PixelType PixelType
typename CellType::MultiVisitor CellMultiVisitorType
Represents a line segment for a Mesh.
Definition: itkLineCell.h:42
typename PointDataContainer::ConstIterator PointDataContainerIterator
typename Edge::SelfAutoPointer EdgeAutoPointer
typename CellsContainer::ConstIterator CellsContainerConstIterator
typename MeshTraits::CellLinksContainer CellLinksContainer
A wrapper of the STL &quot;map&quot; container.
typename Superclass::CellType CellType
typename CellLinksContainer::ConstIterator CellLinksContainerIterator
std::vector< PointType > SeedsType
typename Superclass::CellAutoPointer CellAutoPointer
void VoronoiRegionAddPointId(int id, int x)
Implements the 2-Dimensional Voronoi Diagram.
typename CellLinksContainer::Pointer CellLinksContainerPointer
Implements the N-dimensional mesh structure.
Definition: itkMesh.h:108
std::deque< EdgeInfo > EdgeInfoDQ
EdgeInfo GetEdgeEnd(int id)
typename CellDataContainer::Pointer CellDataContainerPointer
typename MeshTraits::InterpolationWeightType InterpolationWeightType
typename PointDataContainer::Pointer PointDataContainerPointer
std::vector< int > INTvector
std::set< CellIdentifier > PointCellLinksContainer
void AddEdge(VoronoiEdge x)
typename MeshTraits::PointsContainer PointsContainer
typename MeshTraits::CellAutoPointer genericCellPointer
PointsContainerIterator VertexIterator
typename MeshTraits::CellFeatureIdentifier CellFeatureIdentifier
typename MeshTraits::CellTraits CellTraits
std::vector< VoronoiEdge > m_EdgeList
std::vector< std::vector< int > > m_CellNeighborsID
void AddVert(PointType x)
Represents a polygon in a Mesh.
std::list< PointType > PointList
typename PointsContainer::ConstIterator PointsContainerConstIterator
typename MeshTraits::PointIdentifier PointIdentifier
CellFeatureIdentifier CellFeatureCount
void AddCellNeighbor(EdgeInfo x)
typename MeshTraits::PointCellLinksContainer PointCellLinksContainer
typename MeshTraits::CellsContainer CellsContainer
typename PointCellLinksContainer::const_iterator PointCellLinksContainerIterator
typename MeshTraits::CoordRepType CoordRepType
Control indentation during Print() invocation.
Definition: itkIndent.h:49
typename BoundingBoxType::Pointer BoundingBoxPointer
typename MeshTraits::CellDataContainer CellDataContainer
typename CellDataContainer::ConstIterator CellDataContainerIterator
A simple structure that holds type information for a mesh and its cells.
VoronoiEdge GetEdge(int id)
typename std::vector< VoronoiEdge >::iterator VoronoiEdgeIterator
Base class for most ITK classes.
Definition: itkObject.h:60
typename INTvector::iterator NeighborIdIterator
typename MeshTraits::PointType PointType
A templated class holding a geometric point in n-Dimensional space.
Definition: itkPoint.h:52
typename CellsContainer::Pointer CellsContainerPointer
std::vector< PolygonCellType * > m_VoronoiRegions
Base class for all data objects in ITK.
typename SeedsType::iterator SeedsIterator
Represent and compute information about bounding boxes.
std::vector< EdgeInfo > m_LineList
typename PointsContainer::Iterator PointsContainerIterator
typename CellsContainer::Iterator CellsContainerIterator
PointType GetVertex(int id)