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 itkQuadEdgeMeshFrontIterator_h 19 #define itkQuadEdgeMeshFrontIterator_h 20 21 #include "itkMapContainer.h" 22 23 // ------------------------------------------------------------------------- 24 #define itkQEDefineFrontIteratorMethodsMacro(MeshTypeArg) \ 25 /* Dual definition placed before others because of .NET that cannot */ \ 26 /* cope with definition of FrontIterator (that further hides the */ \ 27 /* definition of the template). */ \ 28 using QEDualType = typename MeshTypeArg::QEDual; \ 29 using QEPrimalType = typename MeshTypeArg::QEPrimal; \ 30 using FrontDualIterator = QuadEdgeMeshFrontIterator< MeshTypeArg, \ 31 QEDualType >; \ 32 using ConstFrontDualIterator = QuadEdgeMeshConstFrontIterator< MeshTypeArg, \ 33 QEDualType >; \ 34 using FrontIterator = QuadEdgeMeshFrontIterator< MeshTypeArg, QEPrimalType >; \ 35 using ConstFrontIterator = QuadEdgeMeshConstFrontIterator< MeshTypeArg, \ 36 QEPrimalType >; \ 37 \ 38 virtual FrontIterator BeginFront(QEPrimalType * seed = (QEPrimalType *)0) \ 39 { \ 40 return ( FrontIterator(this, true, seed) ); \ 41 } \ 42 \ 43 virtual ConstFrontIterator BeginFront(QEPrimalType * seed) const \ 44 { return ( ConstFrontIterator(this, true, seed) ); } \ 45 \ 46 virtual FrontIterator EndFront() \ 47 { \ 48 return ( FrontIterator(this, false) ); \ 49 } \ 50 \ 51 virtual ConstFrontIterator EndFront() const \ 52 { return ( ConstFrontIterator(this, false) ); } \ 53 \ 54 virtual FrontDualIterator BeginDualFront(QEDualType * seed = (QEDualType *)0) \ 55 { \ 56 return ( FrontDualIterator(this, true, seed) ); \ 57 } \ 58 \ 59 virtual ConstFrontDualIterator BeginDualFront(QEDualType * seed) const \ 60 { return ( ConstFrontDualIterator(this, true, seed) ); } \ 61 \ 62 virtual FrontDualIterator EndDualFront() \ 63 { \ 64 return ( FrontDualIterator(this, false) ); \ 65 } \ 66 \ 67 virtual ConstFrontDualIterator EndDualFront() const \ 68 { return ( ConstFrontDualIterator(this, false) ); } 69 70 namespace itk 71 { 72 /** 73 * \class QuadEdgeMeshFrontBaseIterator 74 * 75 * \brief Front iterator on Mesh class 76 * 77 * Like topological and geometrical operators, it iterates on edges. 78 * Unlike them, this iterator is not local, nor cyclic. Starting from a 79 * given seed, it will create a front that propagates on the surface. 80 * Depending on the weight associated which each edge, and on the type of the 81 * seed (primal or dual) it can be used for frint propagation algorithm, 82 * distance tree computation or other Djikstra like algorithms. 83 * \ingroup ITKQuadEdgeMesh 84 */ 85 template< typename TMesh, typename TQE > 86 class ITK_TEMPLATE_EXPORT QuadEdgeMeshFrontBaseIterator 87 { 88 public: 89 // Hierarchy type alias & values. 90 using Self = QuadEdgeMeshFrontBaseIterator; 91 92 // Template types 93 using MeshType = TMesh; 94 using QEType = TQE; 95 96 protected: 97 // Mesh types 98 using CoordRepType = typename MeshType::CoordRepType; 99 // QE types 100 using QEOriginType = typename QEType::OriginRefType; 101 102 /** 103 * \class FrontAtom 104 * 105 * \brief Atomic information associated to each edge of the front. 106 * 107 * Note that when sorting this list, the sorting criteria is the 108 * Cost attribute. 109 * \ingroup ITKQuadEdgeMesh 110 */ 111 class FrontAtom 112 { 113 public: 114 FrontAtom(QEType *e = (QEType *)0, const CoordRepType c = 0): m_Edge(e)115 m_Edge(e), m_Cost(c) 116 {} 117 virtual ~FrontAtom() = default; 118 FrontAtom & operator=(const FrontAtom & r) 119 { m_Edge = r.m_Edge; m_Cost = r.m_Cost; return *this; } 120 bool operator==(const FrontAtom & r) const 121 { return ( m_Edge == r.m_Edge ); } 122 bool operator!=(const FrontAtom & r) const 123 { return ( m_Edge != r.m_Edge ); } 124 bool operator<(const FrontAtom & r) const 125 { return ( m_Cost < r.m_Cost ); } 126 127 public: 128 QEType * m_Edge; 129 CoordRepType m_Cost; 130 }; 131 132 /** The active front is simply a list of edges that can be sorted on 133 * the sort attribute FrontAtom 134 */ 135 using FrontType = std::list< FrontAtom >; 136 using FrontTypeIterator = typename FrontType::iterator; 137 using FrontTypePointer = FrontType *; 138 139 /** Whether an Origin (i.e. a vertex or a face since we either deal with 140 * primal or dual edges) was already visited. 141 */ 142 using IsVisitedContainerType = MapContainer< QEOriginType, bool >; 143 using IsVisitedPointerType = typename IsVisitedContainerType::Pointer; 144 145 public: 146 /** Object creation methods. */ 147 QuadEdgeMeshFrontBaseIterator(MeshType *mesh = (MeshType *)nullptr, 148 bool start = true, 149 QEType *seed = (QEType *)nullptr); 150 virtual ~QuadEdgeMeshFrontBaseIterator(); 151 152 Self & operator=(const Self & r) 153 { 154 if(this != &r) 155 { 156 m_Mesh = r.m_Mesh; 157 m_Start = r.m_Start; 158 m_Seed = r.m_Seed; 159 m_Front = r.m_Front; 160 m_IsPointVisited = r.m_IsPointVisited; 161 m_CurrentEdge = r.m_CurrentEdge; 162 } 163 return ( *this ); 164 } 165 166 // Iteration methods. 167 bool operator==(Self & r) 168 { 169 return ( m_Start == r.m_Start ); 170 } 171 172 bool operator==(const Self & r) const 173 { 174 return ( m_Start == r.m_Start ); 175 } 176 177 bool operator!=(Self & r) 178 { 179 return ( !( this->operator==(r) ) ); 180 } 181 182 bool operator!=(const Self & r) const 183 { 184 return ( !( this->operator==(r) ) ); 185 } 186 187 Self & operator++(); 188 189 Self & operator++(int) { return ( this->operator++() ); } 190 GetMesh()191 MeshType * GetMesh() const { return this->m_Mesh; } 192 193 protected: 194 /** Find a default seed by taking any edge (with proper type) in 195 * the current mesh. 196 */ 197 QEType * FindDefaultSeed(); 198 199 /** The default cost associated to an edge is simply 1. This corresponds 200 * to the "topological metric" i.e. all edges have unit length. 201 */ GetCost(QEType * edge)202 virtual CoordRepType GetCost(QEType *edge){ (void)edge; return ( 1 ); } 203 204 protected: 205 /** Mesh on which we propagate the front */ 206 MeshType *m_Mesh; 207 /** Initial seed of the front */ 208 QEType *m_Seed; 209 /** Whether the iterator is active */ 210 bool m_Start; 211 /** The active front */ 212 FrontTypePointer m_Front; 213 /** The already visited points */ 214 IsVisitedPointerType m_IsPointVisited; 215 /** The current edge at this stage of iteration */ 216 QEType *m_CurrentEdge; 217 }; 218 219 /** 220 * \class QuadEdgeMeshFrontIterator 221 * 222 * \brief Non const quad edge front iterator. 223 * \ingroup ITKQuadEdgeMesh 224 */ 225 template< typename TMesh, typename TQE > 226 class ITK_TEMPLATE_EXPORT QuadEdgeMeshFrontIterator: 227 public QuadEdgeMeshFrontBaseIterator< TMesh, TQE > 228 { 229 public: 230 /** Hierarchy type alias and values. */ 231 using Self = QuadEdgeMeshFrontIterator; 232 using Superclass = QuadEdgeMeshFrontBaseIterator< TMesh, TQE >; 233 using MeshType = typename Superclass::MeshType; 234 using QEType = typename Superclass::QEType; 235 236 public: 237 /** Object creation methods. */ 238 QuadEdgeMeshFrontIterator(MeshType *mesh = (MeshType *)0, 239 bool start = true, 240 QEType *seed = (QEType *)nullptr): Superclass(mesh,start,seed)241 Superclass(mesh, start, seed) {} 242 ~QuadEdgeMeshFrontIterator() override = default; Value()243 QEType * Value() { return ( this->m_CurrentEdge ); } 244 }; 245 246 /** 247 * \class QuadEdgeMeshConstFrontIterator 248 * 249 * \brief Const quad edge mesh front iterator. 250 * \ingroup ITKQuadEdgeMesh 251 */ 252 template< typename TMesh, typename TQE = typename TMesh::QEType > 253 class ITK_TEMPLATE_EXPORT QuadEdgeMeshConstFrontIterator: 254 public QuadEdgeMeshFrontBaseIterator< TMesh, TQE > 255 { 256 public: 257 /** Hierarchy type alias & values. */ 258 using Self = QuadEdgeMeshConstFrontIterator; 259 using Superclass = QuadEdgeMeshFrontBaseIterator< TMesh, TQE >; 260 using QEType = typename Superclass::QEType; 261 using MeshType = typename Superclass::MeshType; 262 using NoConstType = QuadEdgeMeshFrontIterator< MeshType, QEType >; 263 264 public: 265 /** Object creation methods. */ 266 QuadEdgeMeshConstFrontIterator(const MeshType *mesh = (MeshType *)0, 267 bool start = true, 268 QEType *seed = (QEType *)nullptr) 269 { 270 (void)mesh; 271 (void)start; 272 (void)seed; 273 } 274 275 /** \todo do we need here a : Superclass( mesh, start, seed ) { } */ 276 ~QuadEdgeMeshConstFrontIterator() override = default; 277 Self & operator=(const NoConstType & r) 278 { 279 this->m_Mesh = r.GetMesh(); 280 return ( *this ); 281 } 282 Value()283 const QEType * Value() const { return ( this->m_CurrentEdge ); } 284 }; 285 } 286 287 #include "itkQuadEdgeMeshFrontIterator.hxx" 288 289 #endif 290