ITK  4.13.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 >
46 class ITK_TEMPLATE_EXPORT VoronoiDiagram2DGenerator:
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 
79  void SetSeeds(int num, SeedsIterator begin);
80 
82  void AddSeeds(int num, SeedsIterator begin);
83 
85  void AddOneSeed(PointType);
86 
88  void SortSeeds();
89 
91  virtual void GenerateOutputInformation() ITK_OVERRIDE {}
92 
94  void UpdateDiagram();
95 
97  void SetBoundary(PointType vorsize);
98 
99  void SetOrigin(PointType vorsize);
100 
102  void SetRandomSeeds(int num);
103 
105  PointType GetSeed(int SeedID);
106 
107 protected:
109  ~VoronoiDiagram2DGenerator() ITK_OVERRIDE;
110  virtual void PrintSelf(std::ostream & os, Indent indent) const ITK_OVERRIDE;
111 
113  void GenerateData(void) ITK_OVERRIDE;
114 
115 private:
116  ITK_DISALLOW_COPY_AND_ASSIGN(VoronoiDiagram2DGenerator);
117 
118  unsigned int m_NumberOfSeeds;
119  PointType m_VorBoundary;
120  OutputType m_OutputVD;
121  SeedsType m_Seeds;
122 
124  static bool comp(PointType arg1, PointType arg2);
125 
132  class FortuneSite;
133  class FortuneEdge;
135 
136  // All private nested classes must be friend classes to work with SunOS-CC
137  // compiler. If not, the private nested classes will not be able to access
138  // each other.
139  friend class FortuneSite;
140  friend class FortuneEdge;
141  friend class FortuneHalfEdge;
142 
143  class FortuneSite
144  {
145  public:
148 
150  m_Sitenbr( NumericTraits< int >::max() )
151  {
153  }
154 
156  };
157 
159  {
160  public:
161  float m_A, m_B, m_C; // explicit line function: Ax + By = C;
162  FortuneSite *m_Ep[2];
163  FortuneSite *m_Reg[2];
165 
167  m_A(0.0),
168  m_B(0.0),
169  m_C(0.0),
170  m_Edgenbr(0)
171  {
172  m_Ep[0] = m_Ep[1] = m_Reg[0] = m_Reg[1] = ITK_NULLPTR;
173  }
174 
176  };
177 
179  {
180  public:
184  bool m_RorL;
186  double m_Ystar;
188 
190  m_Left(ITK_NULLPTR),
191  m_Right(ITK_NULLPTR),
192  m_Edge(ITK_NULLPTR),
193  m_RorL(false),
194  m_Vert(ITK_NULLPTR),
195  m_Ystar(0.0),
196  m_Next(ITK_NULLPTR)
197  {}
198 
200  m_Left(edge.m_Left),
201  m_Right(edge.m_Right),
202  m_Edge(edge.m_Edge),
203  m_RorL(edge.m_RorL),
204  m_Vert(edge.m_Vert),
205  m_Ystar(edge.m_Ystar),
206  m_Next(edge.m_Next)
207  {}
208 
210  };
211 
212  double m_Pxmin;
213  double m_Pxmax;
214  double m_Pymin;
215  double m_Pymax;
216  double m_Deltax;
217  double m_Deltay;
218  double m_SqrtNSites;
219 
220  unsigned int m_PQcount;
221  int m_PQmin;
222  unsigned int m_PQhashsize;
223  unsigned int m_Nedges;
224  unsigned int m_Nvert;
226  std::vector< FortuneHalfEdge > m_PQHash;
227 
228  unsigned int m_ELhashsize;
231  std::vector< FortuneHalfEdge * > m_ELHash;
232 
234  std::vector< FortuneSite > m_SeedSites;
235 
239  bool differentPoint(PointType p1, PointType p2);
240 
241  bool almostsame(CoordRepType p1, CoordRepType p2);
242 
243  unsigned char Pointonbnd(int VertID);
244 
245  void GenerateVDFortune();
246 
247  void ConstructDiagram();
248 
249  void createHalfEdge(FortuneHalfEdge *task, FortuneEdge *e, bool pm);
250 
251  void PQshowMin(PointType *task);
252 
253  FortuneHalfEdge * findLeftHE(PointType *p);
254 
255  FortuneHalfEdge * ELgethash(int b);
256 
261  bool right_of(FortuneHalfEdge *el, PointType *p);
262 
263  FortuneSite * getRightReg(FortuneHalfEdge *he);
264 
265  FortuneSite * getLeftReg(FortuneHalfEdge *he);
266 
267  void bisect(FortuneEdge *, FortuneSite *s1, FortuneSite *s2);
268 
269  void insertEdgeList(FortuneHalfEdge *lbase, FortuneHalfEdge *lnew);
270 
271  void intersect(FortuneSite *task, FortuneHalfEdge *el1, FortuneHalfEdge *el2);
272 
273  void deletePQ(FortuneHalfEdge *task);
274 
275  void deleteEdgeList(FortuneHalfEdge *task);
276 
277  int PQbucket(FortuneHalfEdge *task);
278 
279  void clip_line(FortuneEdge *task);
280 
281  void insertPQ(FortuneHalfEdge *he, FortuneSite *v, double offset);
282 
283  double dist(FortuneSite *s1, FortuneSite *s2);
284 
285  FortuneHalfEdge * getPQmin();
286 
287  void makeEndPoint(FortuneEdge *task, bool lr, FortuneSite *ends);
288 };
289 } // end namespace itk
290 
291 #ifndef ITK_MANUAL_INSTANTIATION
292 #include "itkVoronoiDiagram2DGenerator.hxx"
293 #endif
294 
295 #endif
std::vector< FortuneHalfEdge * > m_ELHash
Light weight base class for most itk classes.
SeedsType::iterator SeedsIterator
Implements the 2-Dimensional Voronoi Diagram.
std::vector< FortuneHalfEdge > m_PQHash
MeshTraits::CoordRepType CoordRepType
void Fill(const ValueType &)
Base class for all process objects that output mesh data.
Definition: itkMeshSource.h:49
MeshSource< VoronoiDiagram2D< TCoordType > > Superclass
Small data structures for Fortune&#39;s Method and some public variables/methods not for external access...
Implement the Sweep Line Algorithm for the construction of the 2D Voronoi Diagram.
Control indentation during Print() invocation.
Definition: itkIndent.h:49
virtual void GenerateOutputInformation() override
Define additional traits for native types such as int or float.
std::vector< PointType > SeedsType
static ITK_CONSTEXPR_VAR double e
The base of the natural logarithm or Euler&#39;s number
Definition: itkMath.h:56
A templated class holding a geometric point in n-Dimensional space.
Definition: itkPoint.h:52
std::deque< EdgeInfo > EdgeInfoDQ
VoronoiDiagram2D< TCoordType > VoronoidDiagramType