ITK  4.3.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 #ifndef NULL
27 #define NULL 0
28 #endif
29 
30 namespace itk
31 {
50 template< typename TCoordType >
51 class ITK_EXPORT VoronoiDiagram2DGenerator:
52  public MeshSource< VoronoiDiagram2D< TCoordType > >
53 {
54 public:
59 
61  itkNewMacro(Self);
62 
65 
69  typedef typename VDMesh::Pointer OutputType;
70  typedef typename VDMesh::PointType PointType;
71  typedef typename VDMesh::SeedsType SeedsType;
72  typedef typename VDMesh::EdgeInfo EdgeInfo;
73  typedef typename VDMesh::EdgeInfoDQ EdgeInfoDQ;
75  typedef typename VDMesh::VoronoiEdge VoronoiEdge;
76 
78  itkGetConstMacro(NumberOfSeeds, unsigned int);
79 
82  void SetSeeds(int num, SeedsIterator begin);
83 
85  void AddSeeds(int num, SeedsIterator begin);
86 
87  void AddOneSeed(PointType);
88 
90  void SortSeeds(void);
91 
93  virtual void GenerateOutputInformation() {}
94 
96  void UpdateDiagram(void);
97 
99  void SetBoundary(PointType vorsize);
100 
101  void SetOrigin(PointType vorsize);
102 
104  void SetRandomSeeds(int num);
105 
107  PointType GetSeed(int SeedID);
108 
109 protected:
112  virtual void PrintSelf(std::ostream & os, Indent indent) const;
113 
115  void GenerateData(void);
116 
117 private:
118  VoronoiDiagram2DGenerator(const Self &); //purposely not implemented
119  void operator=(const Self &); //purposely not implemented
120 
121  unsigned int m_NumberOfSeeds;
125 
126  static bool comp(PointType arg1, PointType arg2);
127 
133  class FortuneSite;
134  class FortuneEdge;
136 
139  friend class FortuneSite;
140  friend class FortuneEdge;
141  friend class FortuneHalfEdge;
142 
144  {
145 public:
148  FortuneSite():m_Sitenbr( NumericTraits< int >::max() ) { m_Coord.Fill( NumericTraits< CoordRepType >::max() ); }
150  };
151 
153  {
154 public:
155  float m_A, m_B, m_C; // explicit line function: Ax + By = C;
156  FortuneSite *m_Ep[2];
157  FortuneSite *m_Reg[2];
159  FortuneEdge():m_A(0.0), m_B(0.0), m_C(0.0) { m_Ep[0] = m_Ep[1] = m_Reg[0] = m_Reg[1] = 0; }
161  };
162 
164  {
165 public:
169  bool m_RorL;
171  double m_Ystar;
173  FortuneHalfEdge():m_Left(0), m_Right(0), m_Edge(0), m_RorL(false), m_Vert(0), m_Ystar(0.0), m_Next(0) {}
174  FortuneHalfEdge(const FortuneHalfEdge & edge):m_Left(edge.m_Left),
175  m_Right(edge.m_Right),
176  m_Edge(edge.m_Edge),
177  m_RorL(edge.m_RorL),
178  m_Vert(edge.m_Vert),
179  m_Ystar(edge.m_Ystar),
180  m_Next(edge.m_Next) {}
182  };
183 
184  double m_Pxmin;
185  double m_Pxmax;
186  double m_Pymin;
187  double m_Pymax;
188  double m_Deltax;
189  double m_Deltay;
190  double m_SqrtNSites;
191 
192  unsigned int m_PQcount;
193  int m_PQmin;
194  unsigned int m_PQhashsize;
195  unsigned int m_Nedges;
196  unsigned int m_Nvert;
198  std::vector< FortuneHalfEdge > m_PQHash;
199 
200  unsigned int m_ELhashsize;
203  std::vector< FortuneHalfEdge * > m_ELHash;
204 
206  std::vector< FortuneSite > m_SeedSites;
207 
208  bool differentPoint(PointType p1, PointType p2);
209 
210  bool almostsame(CoordRepType p1, CoordRepType p2);
211 
212  unsigned char Pointonbnd(int VertID);
213 
214  void GenerateVDFortune(void);
215 
216  void ConstructDiagram(void);
217 
218  void createHalfEdge(FortuneHalfEdge *task, FortuneEdge *e, bool pm);
219 
220  void PQshowMin(PointType *task);
221 
222  FortuneHalfEdge * findLeftHE(PointType *p);
223 
224  FortuneHalfEdge * ELgethash(int b);
225 
226  bool right_of(FortuneHalfEdge *el, PointType *p);
227 
228  FortuneSite * getRightReg(FortuneHalfEdge *he);
229 
230  FortuneSite * getLeftReg(FortuneHalfEdge *he);
231 
232  void bisect(FortuneEdge *, FortuneSite *s1, FortuneSite *s2);
233 
234  void insertEdgeList(FortuneHalfEdge *lbase, FortuneHalfEdge *lnew);
235 
236  void intersect(FortuneSite *task, FortuneHalfEdge *el1, FortuneHalfEdge *el2);
237 
238  void deletePQ(FortuneHalfEdge *task);
239 
240  void deleteEdgeList(FortuneHalfEdge *task);
241 
242  int PQbucket(FortuneHalfEdge *task);
243 
244  void clip_line(FortuneEdge *task);
245 
246  void insertPQ(FortuneHalfEdge *he, FortuneSite *v, double offset);
247 
248  double dist(FortuneSite *s1, FortuneSite *s2);
249 
250  FortuneHalfEdge * getPQmin(void);
251 
252  void makeEndPoint(FortuneEdge *task, bool lr, FortuneSite *ends);
253 };
254 } // end namespace itk
255 
256 #ifndef ITK_MANUAL_INSTANTIATION
257 #include "itkVoronoiDiagram2DGenerator.hxx"
258 #endif
259 
260 #endif
261