ITK  5.3.0
Insight Toolkit
itkVoronoiDiagram2DGenerator.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 itkVoronoiDiagram2DGenerator_h
19 #define itkVoronoiDiagram2DGenerator_h
20 
21 #include "itkMeshSource.h"
22 #include "itkVoronoiDiagram2D.h"
23 
24 #include <vector>
25 
26 namespace itk
27 {
49 template <typename TCoordType>
50 class ITK_TEMPLATE_EXPORT VoronoiDiagram2DGenerator : public MeshSource<VoronoiDiagram2D<TCoordType>>
51 {
52 public:
53  ITK_DISALLOW_COPY_AND_MOVE(VoronoiDiagram2DGenerator);
54 
59 
61  itkNewMacro(Self);
62 
65 
70  using OutputType = typename VDMesh::Pointer;
71  using PointType = typename VDMesh::PointType;
72  using SeedsType = typename VDMesh::SeedsType;
73  using EdgeInfo = typename VDMesh::EdgeInfo;
74  using EdgeInfoDQ = typename VDMesh::EdgeInfoDQ;
76  using VoronoiEdge = typename VDMesh::VoronoiEdge;
77 
79  itkGetConstMacro(NumberOfSeeds, unsigned int);
80 
84  void
85  SetSeeds(int num, SeedsIterator begin);
86 
88  void
89  AddSeeds(int num, SeedsIterator begin);
90 
92  void AddOneSeed(PointType);
93 
95  void
96  SortSeeds();
97 
99  void
101  {}
102 
104  void
105  UpdateDiagram();
106 
108  void
109  SetBoundary(PointType vorsize);
110 
111  void
112  SetOrigin(PointType vorsize);
113 
115  void
116  SetRandomSeeds(int num);
117 
119  PointType
120  GetSeed(int SeedID);
121 
122 protected:
124  ~VoronoiDiagram2DGenerator() override = default;
125  void
126  PrintSelf(std::ostream & os, Indent indent) const override;
127 
129  void
130  GenerateData() override;
131 
132 private:
133  unsigned int m_NumberOfSeeds{ 0 };
137 
139  static bool
140  comp(PointType arg1, PointType arg2);
141 
148  class FortuneSite;
149  class FortuneEdge;
151 
152  // All private nested classes must be friend classes to work with SunOS-CC
153  // compiler. If not, the private nested classes will not be able to access
154  // each other.
155  friend class FortuneSite;
156  friend class FortuneEdge;
157  friend class FortuneHalfEdge;
158 
160  {
161  public:
164 
166  : m_Sitenbr(NumericTraits<int>::max())
167  {
168  m_Coord.Fill(NumericTraits<CoordRepType>::max());
169  }
170 
171  ~FortuneSite() = default;
172  };
173 
175  {
176  public:
177  float m_A{ 0.0 }, m_B{ 0.0 }, m_C{ 0.0 }; // explicit line function: Ax + By = C;
178  FortuneSite * m_Ep[2];
179  FortuneSite * m_Reg[2];
180  int m_Edgenbr{ 0 };
181 
182  FortuneEdge() { m_Ep[0] = m_Ep[1] = m_Reg[0] = m_Reg[1] = nullptr; }
183 
184  ~FortuneEdge() = default;
185  };
186 
188  {
189  public:
193  bool m_RorL{ false };
195  double m_Ystar{ 0.0 };
197 
199  : m_Left(nullptr)
200  , m_Right(nullptr)
201  , m_Edge(nullptr)
202  , m_Vert(nullptr)
203  , m_Next(nullptr)
204  {}
205 
207  : m_Left(edge.m_Left)
208  , m_Right(edge.m_Right)
209  , m_Edge(edge.m_Edge)
210  , m_RorL(edge.m_RorL)
211  , m_Vert(edge.m_Vert)
212  , m_Ystar(edge.m_Ystar)
213  , m_Next(edge.m_Next)
214  {}
215 
216  ~FortuneHalfEdge() = default;
217  };
218 
219  double m_Pxmin{ 0.0 };
220  double m_Pxmax{ 0.0 };
221  double m_Pymin{ 0.0 };
222  double m_Pymax{ 0.0 };
223  double m_Deltax{ 0.0 };
224  double m_Deltay{ 0.0 };
225  double m_SqrtNSites{ 0.0 };
226 
227  unsigned int m_PQcount{ 0 };
228  int m_PQmin{ 0 };
229  unsigned int m_PQhashsize{ 0 };
230  unsigned int m_Nedges{ 0 };
231  unsigned int m_Nvert{ 0 };
233  std::vector<FortuneHalfEdge> m_PQHash;
234 
235  unsigned int m_ELhashsize{ 0 };
238  std::vector<FortuneHalfEdge *> m_ELHash;
239 
241  std::vector<FortuneSite> m_SeedSites;
242 
246  bool
247  differentPoint(PointType p1, PointType p2);
248 
249  bool
250  almostsame(CoordRepType p1, CoordRepType p2);
251 
252  unsigned char
253  Pointonbnd(int VertID);
254 
255  void
256  GenerateVDFortune();
257 
258  void
259  ConstructDiagram();
260 
261  void
262  createHalfEdge(FortuneHalfEdge * task, FortuneEdge * e, bool pm);
263 
264  void
265  PQshowMin(PointType * answer);
266 
268  findLeftHE(PointType * p);
269 
271  ELgethash(int b);
272 
277  bool
278  right_of(FortuneHalfEdge * el, PointType * p);
279 
280  FortuneSite *
281  getRightReg(FortuneHalfEdge * he);
282 
283  FortuneSite *
284  getLeftReg(FortuneHalfEdge * he);
285 
286  void
287  bisect(FortuneEdge *, FortuneSite * s1, FortuneSite * s2);
288 
289  void
290  insertEdgeList(FortuneHalfEdge * lbase, FortuneHalfEdge * lnew);
291 
292  void
293  intersect(FortuneSite * newV, FortuneHalfEdge * el1, FortuneHalfEdge * el2);
294 
295  void
296  deletePQ(FortuneHalfEdge * task);
297 
298  void
299  deleteEdgeList(FortuneHalfEdge * task);
300 
301  int
302  PQbucket(FortuneHalfEdge * task);
303 
304  void
305  clip_line(FortuneEdge * task);
306 
307  void
308  insertPQ(FortuneHalfEdge * he, FortuneSite * v, double offset);
309 
310  double
311  dist(FortuneSite * s1, FortuneSite * s2);
312 
314  getPQmin();
315 
316  void
317  makeEndPoint(FortuneEdge * task, bool lr, FortuneSite * ends);
318 };
319 } // end namespace itk
320 
321 #ifndef ITK_MANUAL_INSTANTIATION
322 # include "itkVoronoiDiagram2DGenerator.hxx"
323 #endif
324 
325 #endif
itk::VoronoiDiagram2DGenerator::FortuneHalfEdge::m_Vert
FortuneSite * m_Vert
Definition: itkVoronoiDiagram2DGenerator.h:194
itk::VoronoiDiagram2D
Implements the 2-Dimensional Voronoi Diagram.
Definition: itkVoronoiDiagram2D.h:51
itk::VoronoiDiagram2DGenerator::FortuneHalfEdge::FortuneHalfEdge
FortuneHalfEdge()
Definition: itkVoronoiDiagram2DGenerator.h:198
itk::VoronoiDiagram2DGenerator::FortuneHalfEdge::m_Left
FortuneHalfEdge * m_Left
Definition: itkVoronoiDiagram2DGenerator.h:190
itk::VoronoiDiagram2DGenerator::m_ELleftend
FortuneHalfEdge m_ELleftend
Definition: itkVoronoiDiagram2DGenerator.h:236
itk::VoronoiDiagram2DGenerator::EdgeInfoDQ
typename VDMesh::EdgeInfoDQ EdgeInfoDQ
Definition: itkVoronoiDiagram2DGenerator.h:74
itk::VoronoiDiagram2DGenerator::FortuneHalfEdge::FortuneHalfEdge
FortuneHalfEdge(const FortuneHalfEdge &edge)
Definition: itkVoronoiDiagram2DGenerator.h:206
itk::VoronoiDiagram2DGenerator::FortuneSite::FortuneSite
FortuneSite()
Definition: itkVoronoiDiagram2DGenerator.h:165
itk::VoronoiDiagram2D::CoordRepType
typename MeshTraits::CoordRepType CoordRepType
Definition: itkVoronoiDiagram2D.h:78
itk::GTest::TypedefsAndConstructors::Dimension2::PointType
ImageBaseType::PointType PointType
Definition: itkGTestTypedefsAndConstructors.h:51
itk::VoronoiDiagram2DGenerator::SeedsIterator
typename VDMesh::SeedsIterator SeedsIterator
Definition: itkVoronoiDiagram2DGenerator.h:69
itk::VoronoiDiagram2DGenerator::FortuneSite::m_Coord
PointType m_Coord
Definition: itkVoronoiDiagram2DGenerator.h:162
itk::SmartPointer< Self >
itk::Indent
Control indentation during Print() invocation.
Definition: itkIndent.h:49
itk::VoronoiDiagram2DGenerator::m_ELrightend
FortuneHalfEdge m_ELrightend
Definition: itkVoronoiDiagram2DGenerator.h:237
itk::VoronoiDiagram2D::SeedsType
std::vector< PointType > SeedsType
Definition: itkVoronoiDiagram2D.h:115
itk::LightObject
Light weight base class for most itk classes.
Definition: itkLightObject.h:59
itk::VoronoiDiagram2DGenerator::m_SeedSites
std::vector< FortuneSite > m_SeedSites
Definition: itkVoronoiDiagram2DGenerator.h:241
itk::VoronoiDiagram2DGenerator::FortuneHalfEdge::m_Right
FortuneHalfEdge * m_Right
Definition: itkVoronoiDiagram2DGenerator.h:191
itk::VoronoiDiagram2DGenerator::m_VorBoundary
PointType m_VorBoundary
Definition: itkVoronoiDiagram2DGenerator.h:134
itk::VoronoiDiagram2DGenerator::m_ELHash
std::vector< FortuneHalfEdge * > m_ELHash
Definition: itkVoronoiDiagram2DGenerator.h:238
itk::MeshSource
Base class for all process objects that output mesh data.
Definition: itkMeshSource.h:49
itkVoronoiDiagram2D.h
itk::VoronoiDiagram2DGenerator::FortuneHalfEdge::m_Edge
FortuneEdge * m_Edge
Definition: itkVoronoiDiagram2DGenerator.h:192
itk::VoronoiDiagram2D::EdgeInfoDQ
std::deque< EdgeInfo > EdgeInfoDQ
Definition: itkVoronoiDiagram2D.h:113
itkMeshSource.h
itk::VoronoiDiagram2DGenerator::m_BottomSite
FortuneSite * m_BottomSite
Definition: itkVoronoiDiagram2DGenerator.h:232
itk::VoronoiDiagram2DGenerator::FortuneEdge::FortuneEdge
FortuneEdge()
Definition: itkVoronoiDiagram2DGenerator.h:182
itk::VoronoiDiagram2DGenerator::FortuneHalfEdge
Definition: itkVoronoiDiagram2DGenerator.h:187
itk::VoronoiDiagram2DGenerator::m_OutputVD
OutputType m_OutputVD
Definition: itkVoronoiDiagram2DGenerator.h:135
itk::VoronoiDiagram2DGenerator::FortuneEdge
Definition: itkVoronoiDiagram2DGenerator.h:174
itk::VoronoiDiagram2DGenerator::m_Seeds
SeedsType m_Seeds
Definition: itkVoronoiDiagram2DGenerator.h:136
itk::VoronoiDiagram2DGenerator::FortuneSite
Small data structures for Fortune's Method and some public variables/methods not for external access.
Definition: itkVoronoiDiagram2DGenerator.h:159
itk::VoronoiDiagram2DGenerator::m_DELETED
FortuneEdge m_DELETED
Definition: itkVoronoiDiagram2DGenerator.h:240
itk::VoronoiDiagram2DGenerator::VoronoiEdge
typename VDMesh::VoronoiEdge VoronoiEdge
Definition: itkVoronoiDiagram2DGenerator.h:76
itk::NumericTraits
Define additional traits for native types such as int or float.
Definition: itkNumericTraits.h:58
itk::VoronoiDiagram2DGenerator::PointType
typename VDMesh::PointType PointType
Definition: itkVoronoiDiagram2DGenerator.h:71
itk
The "itk" namespace contains all Insight Segmentation and Registration Toolkit (ITK) classes....
Definition: itkAnnulusOperator.h:24
itk::VoronoiDiagram2DGenerator::GenerateOutputInformation
void GenerateOutputInformation() override
Definition: itkVoronoiDiagram2DGenerator.h:100
itk::VoronoiDiagram2DGenerator::SeedsType
typename VDMesh::SeedsType SeedsType
Definition: itkVoronoiDiagram2DGenerator.h:72
itk::VoronoiDiagram2DGenerator::m_PQHash
std::vector< FortuneHalfEdge > m_PQHash
Definition: itkVoronoiDiagram2DGenerator.h:233
itk::VoronoiDiagram2DGenerator::EdgeInfo
typename VDMesh::EdgeInfo EdgeInfo
Definition: itkVoronoiDiagram2DGenerator.h:73
itk::Math::e
static constexpr double e
Definition: itkMath.h:54
itk::Point
A templated class holding a geometric point in n-Dimensional space.
Definition: itkPoint.h:53
itk::VoronoiDiagram2DGenerator
Implement the Sweep Line Algorithm for the construction of the 2D Voronoi Diagram.
Definition: itkVoronoiDiagram2DGenerator.h:50
itk::VoronoiDiagram2DGenerator::CoordRepType
typename VDMesh::CoordRepType CoordRepType
Definition: itkVoronoiDiagram2DGenerator.h:75
itk::VoronoiDiagram2DGenerator::FortuneHalfEdge::m_Next
FortuneHalfEdge * m_Next
Definition: itkVoronoiDiagram2DGenerator.h:196
itk::VoronoiDiagram2D::SeedsIterator
typename SeedsType::iterator SeedsIterator
Definition: itkVoronoiDiagram2D.h:116
itk::VoronoiDiagram2DGenerator::OutputType
typename VDMesh::Pointer OutputType
Definition: itkVoronoiDiagram2DGenerator.h:70
itk::VoronoiDiagram2DGenerator::FortuneSite::m_Sitenbr
int m_Sitenbr
Definition: itkVoronoiDiagram2DGenerator.h:163
itk::VoronoiDiagram2D::VoronoiEdge
Definition: itkVoronoiDiagram2D.h:164