ITK  4.9.0
Insight Segmentation and Registration Toolkit
itkVoronoiDiagram2DGenerator.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 itkVoronoiDiagram2DGenerator_h
19 #define itkVoronoiDiagram2DGenerator_h
20 
21 #include "itkMeshSource.h"
22 #include "itkVoronoiDiagram2D.h"
23 
24 #include <vector>
25 
26 namespace itk
27 {
45 template< typename TCoordType >
47  public MeshSource< VoronoiDiagram2D< TCoordType > >
48 {
49 public:
54 
56  itkNewMacro(Self);
57 
60 
65  typedef typename VDMesh::Pointer OutputType;
66  typedef typename VDMesh::PointType PointType;
67  typedef typename VDMesh::SeedsType SeedsType;
68  typedef typename VDMesh::EdgeInfo EdgeInfo;
69  typedef typename VDMesh::EdgeInfoDQ EdgeInfoDQ;
71  typedef typename VDMesh::VoronoiEdge VoronoiEdge;
72 
74  itkGetConstMacro(NumberOfSeeds, unsigned int);
75 
81  void SetSeeds(int num, SeedsIterator begin);
82 
84  void AddSeeds(int num, SeedsIterator begin);
85 
87  void AddOneSeed(PointType);
88 
90  void SortSeeds();
91 
93  virtual void GenerateOutputInformation() ITK_OVERRIDE {}
94 
96  void UpdateDiagram();
97 
99  void SetBoundary(PointType vorsize);
100 
101  void SetOrigin(PointType vorsize);
102 
107  void SetRandomSeeds(int num);
108 
110  PointType GetSeed(int SeedID);
111 
112 protected:
115  virtual void PrintSelf(std::ostream & os, Indent indent) const ITK_OVERRIDE;
116 
118  void GenerateData(void) ITK_OVERRIDE;
119 
120 private:
121  VoronoiDiagram2DGenerator(const Self &) ITK_DELETE_FUNCTION;
122  void operator=(const Self &) ITK_DELETE_FUNCTION;
123 
124  unsigned int m_NumberOfSeeds;
128 
130  static bool comp(PointType arg1, PointType arg2);
131 
138  class FortuneSite;
139  class FortuneEdge;
141 
142  // All private nested classes must be friend classes to work with SunOS-CC
143  // compiler. If not, the private nested classes will not be able to access
144  // each other.
145  friend class FortuneSite;
146  friend class FortuneEdge;
147  friend class FortuneHalfEdge;
148 
149  class FortuneSite
150  {
151  public:
154 
156  m_Sitenbr( NumericTraits< int >::max() )
157  {
159  }
160 
162  };
163 
165  {
166  public:
167  float m_A, m_B, m_C; // explicit line function: Ax + By = C;
171 
173  m_A(0.0),
174  m_B(0.0),
175  m_C(0.0),
176  m_Edgenbr(0)
177  {
178  m_Ep[0] = m_Ep[1] = m_Reg[0] = m_Reg[1] = ITK_NULLPTR;
179  }
180 
182  };
183 
185  {
186  public:
190  bool m_RorL;
192  double m_Ystar;
194 
196  m_Left(ITK_NULLPTR),
197  m_Right(ITK_NULLPTR),
198  m_Edge(ITK_NULLPTR),
199  m_RorL(false),
200  m_Vert(ITK_NULLPTR),
201  m_Ystar(0.0),
202  m_Next(ITK_NULLPTR)
203  {}
204 
206  m_Left(edge.m_Left),
207  m_Right(edge.m_Right),
208  m_Edge(edge.m_Edge),
209  m_RorL(edge.m_RorL),
210  m_Vert(edge.m_Vert),
211  m_Ystar(edge.m_Ystar),
212  m_Next(edge.m_Next)
213  {}
214 
216  };
217 
218  double m_Pxmin;
219  double m_Pxmax;
220  double m_Pymin;
221  double m_Pymax;
222  double m_Deltax;
223  double m_Deltay;
224  double m_SqrtNSites;
225 
226  unsigned int m_PQcount;
227  int m_PQmin;
228  unsigned int m_PQhashsize;
229  unsigned int m_Nedges;
230  unsigned int m_Nvert;
232  std::vector< FortuneHalfEdge > m_PQHash;
233 
234  unsigned int m_ELhashsize;
237  std::vector< FortuneHalfEdge * > m_ELHash;
238 
240  std::vector< FortuneSite > m_SeedSites;
241 
245  bool differentPoint(PointType p1, PointType p2);
246 
247  bool almostsame(CoordRepType p1, CoordRepType p2);
248 
249  unsigned char Pointonbnd(int VertID);
250 
251  void GenerateVDFortune();
252 
253  void ConstructDiagram();
254 
255  void createHalfEdge(FortuneHalfEdge *task, FortuneEdge *e, bool pm);
256 
257  void PQshowMin(PointType *task);
258 
260 
261  FortuneHalfEdge * ELgethash(int b);
262 
267  bool right_of(FortuneHalfEdge *el, PointType *p);
268 
270 
272 
273  void bisect(FortuneEdge *, FortuneSite *s1, FortuneSite *s2);
274 
275  void insertEdgeList(FortuneHalfEdge *lbase, FortuneHalfEdge *lnew);
276 
277  void intersect(FortuneSite *task, FortuneHalfEdge *el1, FortuneHalfEdge *el2);
278 
279  void deletePQ(FortuneHalfEdge *task);
280 
281  void deleteEdgeList(FortuneHalfEdge *task);
282 
283  int PQbucket(FortuneHalfEdge *task);
284 
285  void clip_line(FortuneEdge *task);
286 
287  void insertPQ(FortuneHalfEdge *he, FortuneSite *v, double offset);
288 
289  double dist(FortuneSite *s1, FortuneSite *s2);
290 
292 
293  void makeEndPoint(FortuneEdge *task, bool lr, FortuneSite *ends);
294 };
295 } // end namespace itk
296 
297 #ifndef ITK_MANUAL_INSTANTIATION
298 #include "itkVoronoiDiagram2DGenerator.hxx"
299 #endif
300 
301 #endif
std::vector< FortuneHalfEdge * > m_ELHash
bool right_of(FortuneHalfEdge *el, PointType *p)
void makeEndPoint(FortuneEdge *task, bool lr, FortuneSite *ends)
FortuneHalfEdge * getPQmin()
Light weight base class for most itk classes.
void createHalfEdge(FortuneHalfEdge *task, FortuneEdge *e, bool pm)
void SetSeeds(int num, SeedsIterator begin)
void clip_line(FortuneEdge *task)
void bisect(FortuneEdge *, FortuneSite *s1, FortuneSite *s2)
bool differentPoint(PointType p1, PointType p2)
static bool comp(PointType arg1, PointType arg2)
SeedsType::iterator SeedsIterator
unsigned char Pointonbnd(int VertID)
Implements the 2-Dimensional Voronoi Diagram.
std::vector< FortuneHalfEdge > m_PQHash
static const double e
The base of the natural logarithm or Euler&#39;s number
Definition: itkMath.h:47
MeshTraits::CoordRepType CoordRepType
void insertEdgeList(FortuneHalfEdge *lbase, FortuneHalfEdge *lnew)
void Fill(const ValueType &)
Base class for all process objects that output mesh data.
Definition: itkMeshSource.h:49
double dist(FortuneSite *s1, FortuneSite *s2)
MeshSource< VoronoiDiagram2D< TCoordType > > Superclass
void GenerateData(void) override
FortuneHalfEdge * ELgethash(int b)
void insertPQ(FortuneHalfEdge *he, FortuneSite *v, double offset)
virtual void PrintSelf(std::ostream &os, Indent indent) const override
void intersect(FortuneSite *task, FortuneHalfEdge *el1, FortuneHalfEdge *el2)
void PQshowMin(PointType *task)
Small data structures for Fortune&#39;s Method and some public variables/methods not for external access...
FortuneSite * getLeftReg(FortuneHalfEdge *he)
void deleteEdgeList(FortuneHalfEdge *task)
FortuneHalfEdge * findLeftHE(PointType *p)
Implement the Sweep Line Algorithm for the construction of the 2D Voronoi Diagram.
Control indentation during Print() invocation.
Definition: itkIndent.h:49
void SetBoundary(PointType vorsize)
int PQbucket(FortuneHalfEdge *task)
FortuneSite * getRightReg(FortuneHalfEdge *he)
virtual void GenerateOutputInformation() override
void SetOrigin(PointType vorsize)
Define additional traits for native types such as int or float.
std::vector< PointType > SeedsType
PointType GetSeed(int SeedID)
void deletePQ(FortuneHalfEdge *task)
void AddSeeds(int num, SeedsIterator begin)
A templated class holding a geometric point in n-Dimensional space.
Definition: itkPoint.h:52
std::deque< EdgeInfo > EdgeInfoDQ
VoronoiDiagram2D< TCoordType > VoronoidDiagramType
bool almostsame(CoordRepType p1, CoordRepType p2)