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: 2003/09/10 14:28:40 $
00007   Version:   $Revision: 1.16 $
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   itkGetMacro(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);
00131   class FortuneSite{
00132   public:
00133     PointType m_Coord;
00134     int m_Sitenbr;
00135     FortuneSite() : m_Sitenbr(NumericTraits<int>::max()) { m_Coord.Fill(NumericTraits<CoordRepType>::max()); };
00136     ~FortuneSite(){};
00137   };
00139 
00140   class FortuneEdge{
00141   public:
00142     float m_A, m_B, m_C;  // explicit line function: Ax + By = C;
00143     FortuneSite *m_Ep[2];
00144     FortuneSite *m_Reg[2];
00145     int m_Edgenbr;
00146     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; };
00147     ~FortuneEdge(){};
00148   };
00149 
00150   class FortuneHalfEdge{
00151   public:
00152     FortuneHalfEdge *m_Left;
00153     FortuneHalfEdge *m_Right;
00154     FortuneEdge *m_Edge;
00155     bool m_RorL;
00156     FortuneSite *m_Vert;
00157     double m_Ystar;
00158     FortuneHalfEdge *m_Next;
00159     FortuneHalfEdge() : m_Left(0), m_Right(0), m_Edge(0), m_RorL( false ), m_Vert(0), m_Ystar(0.0), m_Next(0) {};
00160     FortuneHalfEdge(const FortuneHalfEdge &edge) : m_Left(edge.m_Left), m_Right(edge.m_Right), m_Edge(edge.m_Edge), m_RorL( edge.m_RorL ), m_Vert( edge.m_Vert ), m_Ystar( edge.m_Ystar ), m_Next( edge.m_Next ) {};
00161     ~FortuneHalfEdge(){};
00162   };
00163 
00164   double m_Pxmin;
00165   double m_Pxmax;
00166   double m_Pymin;
00167   double m_Pymax;
00168   double m_Deltax;
00169   double m_Deltay;
00170   double m_SqrtNSites;
00171   unsigned int m_PQcount;
00172   int m_PQmin;
00173   unsigned int m_PQhashsize;
00174   unsigned int m_Nedges;
00175   unsigned int m_Nvert;
00176   FortuneSite *m_BottomSite;
00177   std::vector<FortuneHalfEdge> m_PQHash;
00178   unsigned int m_ELhashsize;
00179   FortuneHalfEdge m_ELleftend;
00180   FortuneHalfEdge m_ELrightend;
00181   std::vector<FortuneHalfEdge *> m_ELHash;
00182   FortuneEdge m_DELETED;
00183   std::vector<FortuneSite> m_SeedSites;
00184   
00185   bool differentPoint(PointType p1,PointType p2);
00186   bool almostsame(CoordRepType p1,CoordRepType p2);
00187   unsigned char Pointonbnd(int VertID);
00188 
00189   void GenerateVDFortune(void);
00190   void ConstructDiagram(void);
00191 
00192   void createHalfEdge(FortuneHalfEdge *task, FortuneEdge *e,bool pm);
00193   void PQshowMin(PointType *task);
00194   FortuneHalfEdge *findLeftHE(PointType *p);
00195   FortuneHalfEdge *ELgethash(int b);
00196   bool right_of(FortuneHalfEdge *el, PointType *p);
00197   FortuneSite *getRightReg(FortuneHalfEdge *he);
00198   FortuneSite *getLeftReg(FortuneHalfEdge *he);
00199   void bisect(FortuneEdge *, FortuneSite *s1,FortuneSite *s2);
00200   void insertEdgeList(FortuneHalfEdge *lbase, FortuneHalfEdge *lnew);
00201   void intersect(FortuneSite *task,FortuneHalfEdge *el1,FortuneHalfEdge *el2);
00202   void deletePQ(FortuneHalfEdge *task);
00203   void deleteEdgeList(FortuneHalfEdge *task);
00204   int PQbucket(FortuneHalfEdge *task);
00205   void clip_line(FortuneEdge *task);
00206   void insertPQ(FortuneHalfEdge *he, FortuneSite *v, double offset);
00207   double dist(FortuneSite *s1,FortuneSite *s2);
00208   FortuneHalfEdge *getPQmin(void);
00209   void makeEndPoint(FortuneEdge *task, bool lr, FortuneSite *ends);
00210 };
00211 
00212 } // end namespace itk
00213 
00214 #ifndef ITK_MANUAL_INSTANTIATION
00215 #include "itkVoronoiDiagram2DGenerator.txx"
00216 #endif
00217 
00218 #endif
00219 
00220 
00221 

Generated at Sun Sep 23 14:40:13 2007 for ITK by doxygen 1.5.1 written by Dimitri van Heesch, © 1997-2000