ITK  5.3.0
Insight Toolkit
itkVoronoiDiagram2D.h
Go to the documentation of this file.
1 /*=========================================================================
2  *
3  * Copyright NumFOCUS
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 {
50 template <typename TCoordType>
51 class ITK_TEMPLATE_EXPORT VoronoiDiagram2D
52  : public Mesh<TCoordType, 2, DefaultDynamicMeshTraits<TCoordType, 2, 2, TCoordType>>
53 {
54 public:
55  ITK_DISALLOW_COPY_AND_MOVE(VoronoiDiagram2D);
56 
62 
64  itkNewMacro(Self);
65 
67  itkTypeMacro(VoronoiDiagram2D, Mesh);
68 
71 
73  static constexpr unsigned int PointDimension = MeshTraits::PointDimension;
74  static constexpr unsigned int MaxTopologicalDimension = MeshTraits::MaxTopologicalDimension;
75 
77  using PixelType = typename MeshTraits::PixelType;
83  using PointType = typename MeshTraits::PointType;
93  using PointsContainerPointer = typename PointsContainer::Pointer;
94  using CellsContainerPointer = typename CellsContainer::Pointer;
95  using CellLinksContainerPointer = typename CellLinksContainer::Pointer;
96  using PointDataContainerPointer = typename PointDataContainer::Pointer;
97  using CellDataContainerPointer = typename CellDataContainer::Pointer;
99  using PointsContainerConstIterator = typename PointsContainer::ConstIterator;
100  using PointsContainerIterator = typename PointsContainer::Iterator;
101  using CellsContainerConstIterator = typename CellsContainer::ConstIterator;
102  using CellsContainerIterator = typename CellsContainer::Iterator;
103  using CellLinksContainerIterator = typename CellLinksContainer::ConstIterator;
104  using PointDataContainerIterator = typename PointDataContainer::ConstIterator;
105  using CellDataContainerIterator = typename CellDataContainer::ConstIterator;
106  using PointCellLinksContainerIterator = typename PointCellLinksContainer::const_iterator;
107 
109  using typename Superclass::CellType;
110  using typename Superclass::CellAutoPointer;
113  using EdgeInfoDQ = std::deque<EdgeInfo>;
115  using SeedsType = std::vector<PointType>;
116  using SeedsIterator = typename SeedsType::iterator;
118  using EdgeAutoPointer = typename Edge::SelfAutoPointer;
119  using PointList = std::list<PointType>;
120  using INTvector = std::vector<int>;
121  using NeighborIdIterator = typename INTvector::iterator;
124  itkGetConstMacro(NumberOfSeeds, unsigned int);
125 
128  void
129  SetSeeds(int num, SeedsIterator begin);
130 
132  void
133  SetBoundary(PointType vorsize);
134 
135  void
136  SetOrigin(PointType vorsize);
137 
140  NeighborIdsBegin(int seeds);
141 
143  NeighborIdsEnd(int seeds);
144 
147  VertexBegin();
148 
150  VertexEnd();
151 
153  PointType
154  GetSeed(int SeedID);
155 
157  void
158  GetCellId(CellIdentifier cellId, CellAutoPointer &);
159 
161  void
162  GetPoint(int pId, PointType * answer);
163 
165  {
166  public:
169  int m_LeftID;
171  int m_LineID;
172  VoronoiEdge() = default;
173  ~VoronoiEdge() = default;
174  };
175 
177  using VoronoiEdgeIterator = typename std::vector<VoronoiEdge>::iterator;
178 
181  EdgeBegin();
182 
184  EdgeEnd();
185 
187  EdgeInfo
188  GetSeedsIDAroundEdge(VoronoiEdge * task);
189 
190 /********************************************************/
191 
192  void
193  Reset();
194 
195  void
196  InsertCells();
197 
198  void
200  {
201  m_CellNeighborsID[x[0]].push_back(x[1]);
202  m_CellNeighborsID[x[1]].push_back(x[0]);
203  }
204 
205  void
206  ClearRegion(int i)
207  {
208  m_VoronoiRegions[i]->ClearPoints();
209  }
210 
211  void
212  VoronoiRegionAddPointId(int id, int x)
213  {
214  m_VoronoiRegions[id]->AddPointId(x);
215  }
216 
217  void
218  BuildEdge(int id)
219  {
220  m_VoronoiRegions[id]->BuildEdges();
221  }
222 
223  void
225  {
226  m_LineList.clear();
227  }
228 
229  void
231  {
232  m_EdgeList.clear();
233  }
234 
235  void
237  {
238  if (this->m_PointsContainer.IsNull())
239  {
240  this->m_PointsContainer = PointsContainer::New();
241  }
242 
243  this->m_PointsContainer->Initialize();
244  }
245 
246  int
248  {
249  return static_cast<int>(m_LineList.size());
250  }
251 
252  int
254  {
255  return static_cast<int>(m_EdgeList.size());
256  }
257 
258  int
260  {
261  return static_cast<int>(this->m_PointsContainer->Size());
262  }
263 
264  void
266  {
267  m_LineList.push_back(x);
268  }
269 
270  void
272  {
273  m_EdgeList.push_back(x);
274  }
275 
276  void
278  {
279  this->m_PointsContainer->InsertElement(this->m_PointsContainer->Size(), x);
280  }
281 
282  EdgeInfo
283  GetLine(int id)
284  {
285  return m_LineList[id];
286  }
287 
288  VoronoiEdge
289  GetEdge(int id)
290  {
291  return m_EdgeList[id];
292  }
293 
294  PointType
295  GetVertex(int id)
296  {
297  return this->m_PointsContainer->ElementAt(id);
298  }
299 
300  EdgeInfo
301  GetEdgeEnd(int id)
302  {
303  EdgeInfo x;
304 
305  x[0] = m_EdgeList[id].m_LeftID;
306  x[1] = m_EdgeList[id].m_RightID;
307  return x;
308  }
309 
310  int
312  {
313  return m_EdgeList[id].m_LineID;
314  }
315 
316 protected:
318  ~VoronoiDiagram2D() override = default;
319  void
320  PrintSelf(std::ostream & os, Indent indent) const override;
321 
322 private:
324  unsigned int m_NumberOfSeeds;
325  std::vector<PolygonCellType *> m_VoronoiRegions;
328  std::vector<std::vector<int>> m_CellNeighborsID;
329 
330  std::vector<EdgeInfo> m_LineList;
331  std::vector<VoronoiEdge> m_EdgeList;
332 };
333 
334 } // end namespace itk
335 
336 #ifndef ITK_MANUAL_INSTANTIATION
337 # include "itkVoronoiDiagram2D.hxx"
338 #endif
339 
340 #endif
itk::VoronoiDiagram2D::AddCellNeighbor
void AddCellNeighbor(EdgeInfo x)
Definition: itkVoronoiDiagram2D.h:199
itk::VoronoiDiagram2D::PointsContainerConstIterator
typename PointsContainer::ConstIterator PointsContainerConstIterator
Definition: itkVoronoiDiagram2D.h:99
itk::VoronoiDiagram2D::VoronoiEdge::m_LineID
int m_LineID
Definition: itkVoronoiDiagram2D.h:171
itk::VoronoiDiagram2D::CellDataContainer
typename MeshTraits::CellDataContainer CellDataContainer
Definition: itkVoronoiDiagram2D.h:90
itk::VoronoiDiagram2D::VoronoiEdge::m_Right
PointType m_Right
Definition: itkVoronoiDiagram2D.h:168
itk::VoronoiDiagram2D
Implements the 2-Dimensional Voronoi Diagram.
Definition: itkVoronoiDiagram2D.h:51
itk::VoronoiDiagram2D::m_NumberOfSeeds
unsigned int m_NumberOfSeeds
Definition: itkVoronoiDiagram2D.h:324
itk::DefaultDynamicMeshTraits::InterpolationWeightType
TInterpolationWeight InterpolationWeightType
Definition: itkDefaultDynamicMeshTraits.h:73
itk::VoronoiDiagram2D::AddEdge
void AddEdge(VoronoiEdge x)
Definition: itkVoronoiDiagram2D.h:271
itk::DefaultDynamicMeshTraits::CellTraits
itkMakeCellTraitsMacro CellTraits
Definition: itkDefaultDynamicMeshTraits.h:109
itk::VoronoiDiagram2D::GetVertex
PointType GetVertex(int id)
Definition: itkVoronoiDiagram2D.h:295
itk::VoronoiDiagram2D::INTvector
std::vector< int > INTvector
Definition: itkVoronoiDiagram2D.h:120
itk::VoronoiDiagram2D::CellLinksContainerPointer
typename CellLinksContainer::Pointer CellLinksContainerPointer
Definition: itkVoronoiDiagram2D.h:95
itk::DefaultDynamicMeshTraits::PointIdentifier
IdentifierType PointIdentifier
Definition: itkDefaultDynamicMeshTraits.h:81
itk::VoronoiDiagram2D::CoordRepType
typename MeshTraits::CoordRepType CoordRepType
Definition: itkVoronoiDiagram2D.h:78
itk::GTest::TypedefsAndConstructors::Dimension2::PointType
ImageBaseType::PointType PointType
Definition: itkGTestTypedefsAndConstructors.h:51
itk::VoronoiDiagram2D::PointCellLinksContainer
typename MeshTraits::PointCellLinksContainer PointCellLinksContainer
Definition: itkVoronoiDiagram2D.h:87
itk::VoronoiDiagram2D::EdgeListClear
void EdgeListClear()
Definition: itkVoronoiDiagram2D.h:230
itk::VoronoiDiagram2D::PointsContainerPointer
typename PointsContainer::Pointer PointsContainerPointer
Definition: itkVoronoiDiagram2D.h:93
itk::VoronoiDiagram2D::PointList
std::list< PointType > PointList
Definition: itkVoronoiDiagram2D.h:119
itk::VoronoiDiagram2D::CellsContainerPointer
typename CellsContainer::Pointer CellsContainerPointer
Definition: itkVoronoiDiagram2D.h:94
itk::VoronoiDiagram2D::m_VoronoiBoundary
PointType m_VoronoiBoundary
Definition: itkVoronoiDiagram2D.h:326
itk::VoronoiDiagram2D::CellDataContainerPointer
typename CellDataContainer::Pointer CellDataContainerPointer
Definition: itkVoronoiDiagram2D.h:97
itk::VoronoiDiagram2D::VoronoiEdge::m_Left
PointType m_Left
Definition: itkVoronoiDiagram2D.h:167
itk::VoronoiDiagram2D::LineListSize
int LineListSize()
Definition: itkVoronoiDiagram2D.h:247
itk::PolygonCell
Represents a polygon in a Mesh.
Definition: itkPolygonCell.h:53
itk::VoronoiDiagram2D::LineListClear
void LineListClear()
Definition: itkVoronoiDiagram2D.h:224
itk::SmartPointer< Self >
itk::Indent
Control indentation during Print() invocation.
Definition: itkIndent.h:49
itk::DefaultDynamicMeshTraits::CoordRepType
TCoordRep CoordRepType
Definition: itkDefaultDynamicMeshTraits.h:72
itk::VoronoiDiagram2D::CellsContainer
typename MeshTraits::CellsContainer CellsContainer
Definition: itkVoronoiDiagram2D.h:86
itk::VoronoiDiagram2D::SeedsType
std::vector< PointType > SeedsType
Definition: itkVoronoiDiagram2D.h:115
itk::VoronoiDiagram2D::VoronoiRegionAddPointId
void VoronoiRegionAddPointId(int id, int x)
Definition: itkVoronoiDiagram2D.h:212
itk::VoronoiDiagram2D::BoundingBoxPointer
typename BoundingBoxType::Pointer BoundingBoxPointer
Definition: itkVoronoiDiagram2D.h:98
itk::CellInterface::MultiVisitor
A visitor that can visit different cell types in a mesh. CellInterfaceVisitor instances can be regist...
Definition: itkCellInterface.h:155
itk::VoronoiDiagram2D::PointDataContainerPointer
typename PointDataContainer::Pointer PointDataContainerPointer
Definition: itkVoronoiDiagram2D.h:96
itk::VoronoiDiagram2D::AddVert
void AddVert(PointType x)
Definition: itkVoronoiDiagram2D.h:277
itk::MapContainer
A wrapper of the STL "map" container.
Definition: itkMapContainer.h:45
itk::Mesh< TCoordType, 2, DefaultDynamicMeshTraits< TCoordType, 2, 2, TCoordType > >::CellAutoPointer
typename CellType::CellAutoPointer CellAutoPointer
Definition: itkMesh.h:203
itk::VoronoiDiagram2D::CellFeatureIdentifier
typename MeshTraits::CellFeatureIdentifier CellFeatureIdentifier
Definition: itkVoronoiDiagram2D.h:82
itkDefaultDynamicMeshTraits.h
itk::VoronoiDiagram2D::CellDataContainerIterator
typename CellDataContainer::ConstIterator CellDataContainerIterator
Definition: itkVoronoiDiagram2D.h:105
itk::VoronoiDiagram2D::PointCellLinksContainerIterator
typename PointCellLinksContainer::const_iterator PointCellLinksContainerIterator
Definition: itkVoronoiDiagram2D.h:106
itk::VoronoiDiagram2D::EdgeInfoDQ
std::deque< EdgeInfo > EdgeInfoDQ
Definition: itkVoronoiDiagram2D.h:113
itk::VoronoiDiagram2D::m_VoronoiBoundaryOrigin
PointType m_VoronoiBoundaryOrigin
Definition: itkVoronoiDiagram2D.h:327
itk::VoronoiDiagram2D::CellLinksContainerIterator
typename CellLinksContainer::ConstIterator CellLinksContainerIterator
Definition: itkVoronoiDiagram2D.h:103
itk::VoronoiDiagram2D::GetEdge
VoronoiEdge GetEdge(int id)
Definition: itkVoronoiDiagram2D.h:289
itk::VoronoiDiagram2D::ClearRegion
void ClearRegion(int i)
Definition: itkVoronoiDiagram2D.h:206
itkMesh.h
itk::VoronoiDiagram2D::VoronoiEdgeIterator
typename std::vector< VoronoiEdge >::iterator VoronoiEdgeIterator
Definition: itkVoronoiDiagram2D.h:177
itk::VoronoiDiagram2D::PointsContainer
typename MeshTraits::PointsContainer PointsContainer
Definition: itkVoronoiDiagram2D.h:84
itk::VoronoiDiagram2D::VertexListClear
void VertexListClear()
Definition: itkVoronoiDiagram2D.h:236
itk::VoronoiDiagram2D::m_EdgeList
std::vector< VoronoiEdge > m_EdgeList
Definition: itkVoronoiDiagram2D.h:331
itk::VoronoiDiagram2D::CellMultiVisitorType
typename CellType::MultiVisitor CellMultiVisitorType
Definition: itkVoronoiDiagram2D.h:114
itk::VoronoiDiagram2D::VertexIterator
PointsContainerIterator VertexIterator
Definition: itkVoronoiDiagram2D.h:122
itk::VoronoiDiagram2D::EdgeListSize
int EdgeListSize()
Definition: itkVoronoiDiagram2D.h:253
itk::VoronoiDiagram2D::m_CellNeighborsID
std::vector< std::vector< int > > m_CellNeighborsID
Definition: itkVoronoiDiagram2D.h:328
itk::VoronoiDiagram2D::GetLine
EdgeInfo GetLine(int id)
Definition: itkVoronoiDiagram2D.h:283
itk::VoronoiDiagram2D::CellsContainerIterator
typename CellsContainer::Iterator CellsContainerIterator
Definition: itkVoronoiDiagram2D.h:102
itk::VoronoiDiagram2D::VoronoiEdge::m_RightID
int m_RightID
Definition: itkVoronoiDiagram2D.h:170
itk::VoronoiDiagram2D::CellFeatureCount
CellFeatureIdentifier CellFeatureCount
Definition: itkVoronoiDiagram2D.h:108
itk::VoronoiDiagram2D::PointType
typename MeshTraits::PointType PointType
Definition: itkVoronoiDiagram2D.h:83
itk::VoronoiDiagram2D::CellsContainerConstIterator
typename CellsContainer::ConstIterator CellsContainerConstIterator
Definition: itkVoronoiDiagram2D.h:101
itk::LineCell
Represents a line segment for a Mesh.
Definition: itkLineCell.h:42
itk::DefaultDynamicMeshTraits::PixelType
TPixelType PixelType
Definition: itkDefaultDynamicMeshTraits.h:70
itk::VoronoiDiagram2D::InterpolationWeightType
typename MeshTraits::InterpolationWeightType InterpolationWeightType
Definition: itkVoronoiDiagram2D.h:79
itk::VoronoiDiagram2D::EdgeAutoPointer
typename Edge::SelfAutoPointer EdgeAutoPointer
Definition: itkVoronoiDiagram2D.h:118
itk::VoronoiDiagram2D::genericCellPointer
typename MeshTraits::CellAutoPointer genericCellPointer
Definition: itkVoronoiDiagram2D.h:91
itk::VoronoiDiagram2D::VertexListSize
int VertexListSize()
Definition: itkVoronoiDiagram2D.h:259
itk
The "itk" namespace contains all Insight Segmentation and Registration Toolkit (ITK) classes....
Definition: itkAnnulusOperator.h:24
itk::VoronoiDiagram2D::PointDataContainer
typename MeshTraits::PointDataContainer PointDataContainer
Definition: itkVoronoiDiagram2D.h:89
itk::VoronoiDiagram2D::CellTraits
typename MeshTraits::CellTraits CellTraits
Definition: itkVoronoiDiagram2D.h:85
itk::Mesh
Implements the N-dimensional mesh structure.
Definition: itkMesh.h:114
itk::VoronoiDiagram2D::PointDataContainerIterator
typename PointDataContainer::ConstIterator PointDataContainerIterator
Definition: itkVoronoiDiagram2D.h:104
itk::VoronoiDiagram2D::GetEdgeEnd
EdgeInfo GetEdgeEnd(int id)
Definition: itkVoronoiDiagram2D.h:301
itkPolygonCell.h
itk::VoronoiDiagram2D::m_LineList
std::vector< EdgeInfo > m_LineList
Definition: itkVoronoiDiagram2D.h:330
itk::VoronoiDiagram2D::m_Seeds
SeedsType m_Seeds
Definition: itkVoronoiDiagram2D.h:323
itk::VoronoiDiagram2D::AddLine
void AddLine(EdgeInfo x)
Definition: itkVoronoiDiagram2D.h:265
itk::VoronoiDiagram2D::VoronoiEdge::m_LeftID
int m_LeftID
Definition: itkVoronoiDiagram2D.h:169
itk::Object
Base class for most ITK classes.
Definition: itkObject.h:62
itk::DefaultDynamicMeshTraits::CellIdentifier
IdentifierType CellIdentifier
Definition: itkDefaultDynamicMeshTraits.h:85
itk::VoronoiDiagram2D::CellLinksContainer
typename MeshTraits::CellLinksContainer CellLinksContainer
Definition: itkVoronoiDiagram2D.h:88
itk::VoronoiDiagram2D::CellIdentifier
typename MeshTraits::CellIdentifier CellIdentifier
Definition: itkVoronoiDiagram2D.h:81
itk::Point
A templated class holding a geometric point in n-Dimensional space.
Definition: itkPoint.h:53
itk::DefaultDynamicMeshTraits::CellAutoPointer
typename CellType::CellAutoPointer CellAutoPointer
Definition: itkDefaultDynamicMeshTraits.h:114
itk::VoronoiDiagram2D::PointsContainerIterator
typename PointsContainer::Iterator PointsContainerIterator
Definition: itkVoronoiDiagram2D.h:100
itk::VoronoiDiagram2D::BuildEdge
void BuildEdge(int id)
Definition: itkVoronoiDiagram2D.h:218
itk::DefaultDynamicMeshTraits::PointCellLinksContainer
std::set< CellIdentifier > PointCellLinksContainer
Definition: itkDefaultDynamicMeshTraits.h:122
itk::BoundingBox
Represent and compute information about bounding boxes.
Definition: itkBoundingBox.h:70
itk::VoronoiDiagram2D::NeighborIdIterator
typename INTvector::iterator NeighborIdIterator
Definition: itkVoronoiDiagram2D.h:121
itk::VoronoiDiagram2D::m_VoronoiRegions
std::vector< PolygonCellType * > m_VoronoiRegions
Definition: itkVoronoiDiagram2D.h:325
itk::VoronoiDiagram2D::PixelType
typename MeshTraits::PixelType PixelType
Definition: itkVoronoiDiagram2D.h:77
itk::VoronoiDiagram2D::SeedsIterator
typename SeedsType::iterator SeedsIterator
Definition: itkVoronoiDiagram2D.h:116
itk::DefaultDynamicMeshTraits
A simple structure that holds type information for a mesh and its cells.
Definition: itkDefaultDynamicMeshTraits.h:63
itk::VoronoiDiagram2D::GetEdgeLineID
int GetEdgeLineID(int id)
Definition: itkVoronoiDiagram2D.h:311
itk::DataObject
Base class for all data objects in ITK.
Definition: itkDataObject.h:293
itk::DefaultDynamicMeshTraits::CellFeatureIdentifier
IdentifierType CellFeatureIdentifier
Definition: itkDefaultDynamicMeshTraits.h:90
itk::VoronoiDiagram2D::PointIdentifier
typename MeshTraits::PointIdentifier PointIdentifier
Definition: itkVoronoiDiagram2D.h:80
itk::VoronoiDiagram2D::VoronoiEdge
Definition: itkVoronoiDiagram2D.h:164