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