Main Page   Groups   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Concepts

itkVoronoiDiagram2DGenerator.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itkVoronoiDiagram2DGenerator.h,v $
00005   Language:  C++
00006   Date:      $Date: 2009-04-23 03:53:37 $
00007   Version:   $Revision: 1.18 $
00008 
00009   Copyright (c) Insight Software Consortium. All rights reserved.
00010   See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
00011 
00012      This software is distributed WITHOUT ANY WARRANTY; without even 
00013      the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
00014      PURPOSE.  See the above copyright notices for more information.
00015 
00016 =========================================================================*/
00017 #ifndef __itkVoronoiDiagram2DGenerator_h
00018 #define __itkVoronoiDiagram2DGenerator_h
00019 
00020 #include "itkCellInterface.h"
00021 #include "itkLineCell.h"
00022 #include "itkMeshSource.h"
00023 #include "itkDefaultDynamicMeshTraits.h"
00024 #include "itkPolygonCell.h"
00025 #include "itkVoronoiDiagram2D.h"
00026 
00027 #include <vector>
00028 
00029 #ifndef NULL
00030 #define NULL 0 
00031 #endif
00032 
00033 namespace itk
00034 {
00052 template <typename TCoordType>
00053 class ITK_EXPORT VoronoiDiagram2DGenerator:
00054     public MeshSource <VoronoiDiagram2D<TCoordType> >
00055 {
00056 public:
00057   typedef VoronoiDiagram2DGenerator                  Self;
00058   typedef MeshSource <VoronoiDiagram2D<TCoordType> > Superclass;
00059   typedef SmartPointer<Self>                         Pointer;
00060   typedef SmartPointer<const Self>                   ConstPointer;
00061 
00063   itkNewMacro(Self);
00064 
00066   itkTypeMacro(VoronoiDiagram2DGenerator, MeshSource);
00067 
00069   typedef VoronoiDiagram2D<TCoordType>   VDMesh;
00070   typedef typename VDMesh::SeedsIterator SeedsIterator;
00071   typedef typename VDMesh::Pointer       OutputType;
00072   typedef typename VDMesh::PointType     PointType;
00073   typedef typename VDMesh::SeedsType     SeedsType;
00074   typedef typename VDMesh::EdgeInfo      EdgeInfo;
00075   typedef typename VDMesh::EdgeInfoDQ    EdgeInfoDQ;
00076   typedef typename VDMesh::CoordRepType  CoordRepType;
00077   typedef typename VDMesh::VoronoiEdge   VoronoiEdge;
00078 
00080   itkGetConstMacro(NumberOfSeeds,unsigned int);
00081 
00084   void SetSeeds (int num, SeedsIterator begin);
00085 
00087   void AddSeeds(int num,SeedsIterator begin);
00088   void AddOneSeed(PointType);
00090 
00092   void SortSeeds(void);
00093 
00095   virtual void GenerateOutputInformation() {}
00096 
00098   void UpdateDiagram(void);
00099 
00101   void SetBoundary(PointType vorsize);
00102   void SetOrigin(PointType vorsize);
00104 
00106   void SetRandomSeeds(int num);
00107 
00109   PointType GetSeed(int SeedID);
00110 
00111 protected:
00112   VoronoiDiagram2DGenerator();
00113   ~VoronoiDiagram2DGenerator();
00114   virtual void PrintSelf(std::ostream& os, Indent indent) const;
00115 
00117   void GenerateData(void);
00118 
00119 private:
00120   VoronoiDiagram2DGenerator(const Self&); //purposely not implemented
00121   void operator=(const Self&); //purposely not implemented
00122   
00123   unsigned int m_NumberOfSeeds;
00124   PointType    m_VorBoundary;
00125   OutputType   m_OutputVD;
00126   SeedsType    m_Seeds;
00127 
00128   static bool comp(PointType arg1,PointType arg2);
00132   class FortuneSite
00133     {
00134     public:
00135       PointType m_Coord;
00136       int       m_Sitenbr;
00137       FortuneSite() : m_Sitenbr(NumericTraits<int>::max()) { m_Coord.Fill(NumericTraits<CoordRepType>::max()); }
00138       ~FortuneSite(){}
00139     };
00140 
00141   class FortuneEdge
00142     {
00143     public:
00144       float        m_A, m_B, m_C;  // explicit line function: Ax + By = C;
00145       FortuneSite *m_Ep[2];
00146       FortuneSite *m_Reg[2];
00147       int          m_Edgenbr;
00148       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; }
00149       ~FortuneEdge(){}
00150     };
00151 
00152   class FortuneHalfEdge
00153     {
00154     public:
00155       FortuneHalfEdge  *m_Left;
00156       FortuneHalfEdge  *m_Right;
00157       FortuneEdge      *m_Edge;
00158       bool              m_RorL;
00159       FortuneSite      *m_Vert;
00160       double            m_Ystar;
00161       FortuneHalfEdge  *m_Next;
00162       FortuneHalfEdge() : m_Left(0), m_Right(0), m_Edge(0), m_RorL( false ), m_Vert(0), m_Ystar(0.0), m_Next(0) {}
00163       FortuneHalfEdge(const FortuneHalfEdge &edge) : m_Left(edge.m_Left),
00164                                                      m_Right(edge.m_Right),
00165                                                      m_Edge(edge.m_Edge),
00166                                                      m_RorL( edge.m_RorL ),
00167                                                      m_Vert( edge.m_Vert ),
00168                                                      m_Ystar( edge.m_Ystar ),
00169                                                      m_Next( edge.m_Next ) {}
00170       ~FortuneHalfEdge(){}
00171     };
00172 
00173   double m_Pxmin;
00174   double m_Pxmax;
00175   double m_Pymin;
00176   double m_Pymax;
00177   double m_Deltax;
00178   double m_Deltay;
00179   double m_SqrtNSites;
00180 
00181   unsigned int                 m_PQcount;
00182   int                          m_PQmin;
00183   unsigned int                 m_PQhashsize;
00184   unsigned int                 m_Nedges;
00185   unsigned int                 m_Nvert;
00186   FortuneSite                 *m_BottomSite;
00187   std::vector<FortuneHalfEdge> m_PQHash;
00188 
00189   unsigned int                   m_ELhashsize;
00190   FortuneHalfEdge                m_ELleftend;
00191   FortuneHalfEdge                m_ELrightend;
00192   std::vector<FortuneHalfEdge *> m_ELHash;
00193 
00194   FortuneEdge              m_DELETED;
00195   std::vector<FortuneSite> m_SeedSites;
00196   
00197   bool differentPoint(PointType p1,PointType p2);
00198   bool almostsame(CoordRepType p1,CoordRepType p2);
00199   unsigned char Pointonbnd(int VertID);
00200 
00201   void GenerateVDFortune(void);
00202   void ConstructDiagram(void);
00203 
00204   void createHalfEdge(FortuneHalfEdge *task, FortuneEdge *e,bool pm);
00205   void PQshowMin(PointType *task);
00206   FortuneHalfEdge *findLeftHE(PointType *p);
00207   FortuneHalfEdge *ELgethash(int b);
00208   bool right_of(FortuneHalfEdge *el, PointType *p);
00209   FortuneSite *getRightReg(FortuneHalfEdge *he);
00210   FortuneSite *getLeftReg(FortuneHalfEdge *he);
00211   void bisect(FortuneEdge *, FortuneSite *s1,FortuneSite *s2);
00212   void insertEdgeList(FortuneHalfEdge *lbase, FortuneHalfEdge *lnew);
00213   void intersect(FortuneSite *task,FortuneHalfEdge *el1,FortuneHalfEdge *el2);
00214   void deletePQ(FortuneHalfEdge *task);
00215   void deleteEdgeList(FortuneHalfEdge *task);
00216   int PQbucket(FortuneHalfEdge *task);
00217   void clip_line(FortuneEdge *task);
00218   void insertPQ(FortuneHalfEdge *he, FortuneSite *v, double offset);
00219   double dist(FortuneSite *s1,FortuneSite *s2);
00220   FortuneHalfEdge *getPQmin(void);
00221   void makeEndPoint(FortuneEdge *task, bool lr, FortuneSite *ends);
00222 };
00223 
00224 } // end namespace itk
00225 
00226 #ifndef ITK_MANUAL_INSTANTIATION
00227 #include "itkVoronoiDiagram2DGenerator.txx"
00228 #endif
00229 
00230 #endif
00231 

Generated at Tue Sep 15 05:24:57 2009 for ITK by doxygen 1.5.8 written by Dimitri van Heesch, © 1997-2000