1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
/*=========================================================================
Program: Insight Segmentation & Registration Toolkit
Module: $RCSfile: itkVoronoiDiagram2D.h,v $
Language: C++
Date: $Date: 2003-09-10 14:28:40 $
Version: $Revision: 1.18 $
Copyright (c) Insight Software Consortium. All rights reserved.
See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
This software is distributed WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the above copyright notices for more information.
=========================================================================*/
#ifndef __itkVoronoiDiagram2D_h
#define __itkVoronoiDiagram2D_h
#if defined(_MSC_VER)
#pragma warning ( disable : 4786 )
#endif
#include "itkCellInterface.h"
#include "itkLineCell.h"
#include "itkMesh.h"
#include "itkDefaultDynamicMeshTraits.h"
#include "itkPolygonCell.h"
#include <vector>
#ifndef NULL
#define NULL 0
#endif
namespace itk
{
/** \class VoronoiDiagram2D
* \brief Implements the 2-Dimensional Voronoi Diagram.
*
* Given a set of seed points, the Voronoi Diagram partitions the plane into
* regions, each region is a collection of all pixels that is closest to one
* particular seed point than to other seed points.
* VoronoiDiagram2D is a mesh structure for storing the Voronoi Diagram,
* can be Generated by itkVoronoiDiagram2DGenerator.
*
* Template parameters for VoronoiDiagram2D:
*
* TCoordType = The type associated with the coordniation of the seeds and
* the resulting vertices.
*
* \ingroup MeshObjects
*/
template <typename TCoordType>
class ITK_EXPORT VoronoiDiagram2D:
public Mesh <TCoordType, 2,
DefaultDynamicMeshTraits<TCoordType, 2, 2, TCoordType> >
{
public:
/** Standard class typedefs. */
typedef VoronoiDiagram2D Self;
typedef Mesh <TCoordType, 2,
DefaultDynamicMeshTraits<TCoordType, 2, 2, TCoordType> >
Superclass;
typedef SmartPointer<Self> Pointer;
typedef SmartPointer<const Self> ConstPointer;
/** Method for creation through the object factory. */
itkNewMacro(Self);
/** Standard part of every itk Object. */
itkTypeMacro(VoronoiDiagram2D, Mesh);
/** Define the mesh traits. */
typedef DefaultDynamicMeshTraits<TCoordType, 2, 2, TCoordType> MeshTraits;
/** Dimensions of the points and topology. */
itkStaticConstMacro(PointDimension, unsigned int,
MeshTraits::PointDimension);
itkStaticConstMacro(MaxTopologicalDimension, unsigned int,
MeshTraits::MaxTopologicalDimension);
/** Typedefs from itkMesh */
typedef typename MeshTraits::PixelType PixelType;
typedef typename MeshTraits::CoordRepType CoordRepType;
typedef typename MeshTraits::InterpolationWeightType InterpolationWeightType;
typedef typename MeshTraits::PointIdentifier PointIdentifier;
typedef typename MeshTraits::CellIdentifier CellIdentifier;
typedef typename MeshTraits::CellFeatureIdentifier CellFeatureIdentifier;
typedef typename MeshTraits::PointType PointType;
typedef typename MeshTraits::PointsContainer PointsContainer;
typedef typename MeshTraits::CellTraits CellTraits;
typedef typename MeshTraits::CellsContainer CellsContainer;
typedef typename MeshTraits::PointCellLinksContainer PointCellLinksContainer;
typedef typename MeshTraits::CellLinksContainer CellLinksContainer;
typedef typename MeshTraits::PointDataContainer PointDataContainer;
typedef typename MeshTraits::CellDataContainer CellDataContainer;
typedef typename MeshTraits::CellAutoPointer genericCellPointer;
typedef PointLocator<PointIdentifier,itkGetStaticConstMacro(PointDimension),
CoordRepType,PointsContainer> PointLocatorType;
typedef BoundingBox<PointIdentifier,itkGetStaticConstMacro(PointDimension),
CoordRepType,PointsContainer> BoundingBoxType;
typedef typename PointsContainer::Pointer PointsContainerPointer;
typedef typename CellsContainer::Pointer CellsContainerPointer;
typedef typename CellLinksContainer::Pointer CellLinksContainerPointer;
typedef typename PointDataContainer::Pointer PointDataContainerPointer;
typedef typename CellDataContainer::Pointer CellDataContainerPointer;
typedef typename PointLocatorType::Pointer PointLocatorPointer;
typedef typename BoundingBoxType::Pointer BoundingBoxPointer;
typedef typename
PointsContainer::ConstIterator PointsContainerConstIterator;
typedef typename
PointsContainer::Iterator PointsContainerIterator;
typedef typename
CellsContainer::ConstIterator CellsContainerConstIterator;
typedef typename
CellsContainer::Iterator CellsContainerIterator;
typedef typename
CellLinksContainer::ConstIterator CellLinksContainerIterator;
typedef typename
PointDataContainer::ConstIterator PointDataContainerIterator;
typedef typename
CellDataContainer::ConstIterator CellDataContainerIterator;
typedef typename
PointCellLinksContainer::const_iterator PointCellLinksContainerIterator;
typedef CellFeatureIdentifier CellFeatureCount;
typedef CellInterface<PixelType,CellTraits> CellInterfaceType;
typedef PolygonCell<CellInterfaceType> CellType;
typedef typename CellType::CellAutoPointer CellAutoPointer;
typedef Point<int,2> EdgeInfo;
typedef std::deque<EdgeInfo> EdgeInfoDQ;
typedef typename CellType::MultiVisitor CellMultiVisitorType;
typedef std::vector<PointType> SeedsType;
typedef typename SeedsType::iterator SeedsIterator;
typedef LineCell <CellInterfaceType> Edge;
typedef typename Edge::SelfAutoPointer EdgeAutoPointer;
typedef std::list<PointType> PointList;
typedef std::vector<int> INTvector;
typedef typename INTvector::iterator NeighborIdIterator;
typedef typename std::vector<PointType>::iterator VertexIterator;
/** Get the number of Voronoi seeds. */
itkGetMacro(NumberOfSeeds,unsigned int);
/** Input the seeds information, will overwrite if seeds already
* exists. */
void SetSeeds (int num, SeedsIterator begin);
/** The boundary that encloses the whole Voronoi diagram. */
void SetBoundary(PointType vorsize);
void SetOrigin(PointType vorsize);
/** Iterators for the neighborhood cells around the given cell. */
NeighborIdIterator NeighborIdsBegin(int seeds);
NeighborIdIterator NeighborIdsEnd(int seeds);
/** Iterators for all the vertices of the voronoi diagram. */
VertexIterator VertexBegin(void);
VertexIterator VertexEnd(void);
/** Return the given indexed seed. */
PointType GetSeed(int SeedID);
/** Return the required cell pointer. */
void GetCellId(CellIdentifier cellId, CellAutoPointer &);
/** Return the given vertex of the voronoi diagram. */
void GetPoint(int pId,PointType *answer);
class VoronoiEdge{
public:
PointType m_Left;
PointType m_Right;
int m_LeftID;
int m_RightID;
int m_LineID;
VoronoiEdge(){};
~VoronoiEdge(){};
};
/** The iterator for Voronoi edges, */
typedef typename std::vector<VoronoiEdge>::iterator VoronoiEdgeIterator;
/** The Iterator of all the edges for the Voronoi diagram. */
VoronoiEdgeIterator EdgeBegin(void);
VoronoiEdgeIterator EdgeEnd(void);
/** Find the two seed point that around the given edge. */
EdgeInfo GetSeedsIDAroundEdge(VoronoiEdge *task);
/********************************************************/
void Reset();
void InsertCells();
void AddCellNeighbor(EdgeInfo x){
m_CellNeighborsID[x[0]].push_back(x[1]);
m_CellNeighborsID[x[1]].push_back(x[0]);};
void ClearRegion(int i){ m_VoronoiRegions[i]->ClearPoints();};
void VoronoiRegionAddPointId(int id, int x){m_VoronoiRegions[id]->AddPointId(x);};
void BuildEdge(int id){ m_VoronoiRegions[id]->BuildEdges();};
void LineListClear(){ f_LineList.clear();};
void EdgeListClear(){ f_EdgeList.clear();};
void VertexListClear(){ f_VertexList.clear();};
int LineListSize(){ return static_cast<int>( f_LineList.size() );};
int EdgeListSize(){ return static_cast<int>( f_EdgeList.size() );};
int VertexListSize(){ return static_cast<int>( f_VertexList.size() );};
void AddLine(EdgeInfo x){ f_LineList.push_back(x);};
void AddEdge(VoronoiEdge x){ f_EdgeList.push_back(x);};
void AddVert(PointType x){ f_VertexList.push_back(x);};
EdgeInfo GetLine(int id){ return f_LineList[id];};
VoronoiEdge GetEdge(int id){ return f_EdgeList[id];};
PointType GetVertex(int id){ return f_VertexList[id];};
EdgeInfo GetEdgeEnd(int id){
EdgeInfo x;
x[0]=f_EdgeList[id].m_LeftID;
x[1]=f_EdgeList[id].m_RightID;
return x;
}
int GetEdgeLineID(int id){ return f_EdgeList[id].m_LineID; };
protected:
VoronoiDiagram2D();
~VoronoiDiagram2D();
virtual void PrintSelf(std::ostream& os, Indent indent) const;
private:
VoronoiDiagram2D(const Self&); //purposely not implemented
void operator=(const Self&); //purposely not implemented
SeedsType m_Seeds;
unsigned int m_NumberOfSeeds;
std::vector<CellType *> m_VoronoiRegions;
PointType m_VoronoiBoundary;
PointType m_VoronoiBoundaryOrigin;
std::vector< std::vector<int> > m_CellNeighborsID;
std::vector< EdgeInfo > f_LineList;
std::vector< PointType > f_VertexList;
std::vector< VoronoiEdge > f_EdgeList;
}; // end class: VoronoiDiagram2D
} // end namespace itk
#ifndef ITK_MANUAL_INSTANTIATION
#include "itkVoronoiDiagram2D.txx"
#endif
#endif
|
