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 itkQuadEdgeMesh_hxx
19 #define itkQuadEdgeMesh_hxx
20 #include "itkQuadEdgeMesh.h"
21 #include <limits>
22 #include <vector>
23
24 namespace itk
25 {
26 template< typename TPixel, unsigned int VDimension, typename TTraits >
27 const typename QuadEdgeMesh< TPixel, VDimension, TTraits >::PointIdentifier
28 QuadEdgeMesh< TPixel, VDimension, TTraits >::m_NoPoint =
29 std::numeric_limits< PointIdentifier >::max();
30
31 template< typename TPixel, unsigned int VDimension, typename TTraits >
32 const typename QuadEdgeMesh< TPixel, VDimension, TTraits >::CellIdentifier
33 QuadEdgeMesh< TPixel, VDimension, TTraits >::m_NoFace =
34 std::numeric_limits< CellIdentifier >::max();
35
36 /**
37 * Restore the mesh to its initial state. Useful for data pipeline updates
38 * without memory re-allocation.
39 */
40 template< typename TPixel, unsigned int VDimension, typename TTraits >
41 void
42 QuadEdgeMesh< TPixel, VDimension, TTraits >
Initialize()43 ::Initialize()
44 {
45 itkDebugMacro("Mesh Initialize method ");
46 Clear();
47 Superclass::Initialize();
48 }
49
50 /**
51 * Clear all this mesh by deleting all contained edges which as
52 * a side effect deletes adjacent faces
53 */
54 template< typename TPixel, unsigned int VDimension, typename TTraits >
55 void
56 QuadEdgeMesh< TPixel, VDimension, TTraits >
Clear()57 ::Clear()
58 {
59 if ( this->GetEdgeCells() )
60 {
61 CellsContainerIterator cellIterator = this->GetEdgeCells()->Begin();
62 while ( !this->GetEdgeCells()->empty() )
63 {
64 auto * edgeToDelete = dynamic_cast< EdgeCellType * >( cellIterator.Value() );
65 this->LightWeightDeleteEdge(edgeToDelete);
66 cellIterator = this->GetEdgeCells()->Begin();
67 }
68 }
69
70 // Clear the points potentialy left behind by LightWeightDeleteEdge():
71 if ( this->GetPoints() )
72 {
73 this->GetPoints()->clear();
74 }
75 this->ClearFreePointAndCellIndexesLists(); // to start at index 0
76 }
77
78 template< typename TPixel, unsigned int VDimension, typename TTraits >
79 void
80 QuadEdgeMesh< TPixel, VDimension, TTraits >
Graft(const DataObject * data)81 ::Graft(const DataObject *data)
82 {
83 this->Superclass::Graft(data);
84 const auto * mesh = dynamic_cast< const Self * >( data );
85
86 if ( !mesh )
87 {
88 // pointer could not be cast back down
89 itkExceptionMacro( << "itk::QuadEdgeMesh::CopyInformation() cannot cast "
90 << typeid( data ).name() << " to "
91 << typeid( Self * ).name() );
92 }
93
94 this->m_FreePointIndexes = mesh->m_FreePointIndexes;
95 this->m_FreeCellIndexes = mesh->m_FreeCellIndexes;
96 this->ClearCellsContainer();
97 this->m_EdgeCellsContainer = mesh->m_EdgeCellsContainer;
98 this->m_NumberOfFaces = mesh->m_NumberOfFaces;
99 this->m_NumberOfEdges = mesh->m_NumberOfEdges;
100 }
101
102 /**
103 * \brief The one and only method to modify the edge connectivity.
104 */
105 template< typename TPixel, unsigned int VDimension, typename TTraits >
106 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::PointIdentifier
107 QuadEdgeMesh< TPixel, VDimension, TTraits >
Splice(QEPrimal * a,QEPrimal * b)108 ::Splice(QEPrimal *a, QEPrimal *b)
109 {
110 bool SplitingOrigin = a->IsInOnextRing(b);
111 PointIdentifier resultingOriginId;
112
113 if ( SplitingOrigin )
114 {
115 // see TODO's entry dated 2006-01-24
116 /* We consider the following situation which depicts the Onext()
117 * ring around the point Origin (which is both a->GetOrigin() and
118 * b->GetOrigin():
119 *
120 * \ /
121 * \ /
122 * e3 e2 counter-clockwise
123 * \ / Onext() order.
124 * \ /
125 * -----b------Org------a----
126 * / \
127 * / \
128 * / \
129 * / \
130 * / \
131 * e5 e6
132 * / \
133 * / \
134 *
135 * The result of this method is then:
136 *
137 * \ /
138 * \ /
139 * e3 e2
140 * \ /
141 * \ /
142 * ----b------newOrg
143 *
144 * Org------a-----
145 * / \
146 * / \
147 * / \
148 * / \
149 * / \
150 * e5 e7
151 * / \
152 * / \
153 */
154
155 // Handle connectivity at QEQuadEdge level:
156 a->Splice(b);
157
158 ////////// Handle the geometrical references:
159 // Make sure the Origin's edge entry doesn't point to an entry edge
160 // that isn't any more in the Onext ring:
161 PointIdentifier orgId = a->GetOrigin();
162 PointType org = this->GetPoint(orgId);
163 org.SetEdge(a);
164 this->SetPoint(orgId, org);
165
166 // Create a newOrigin point by duplicating the geometry of Origin...
167 PointType newOrigin = org;
168 newOrigin.SetEdge(b);
169 PointIdentifier newOriginId = this->AddPoint(newOrigin);
170
171 // ...and inform Onext ring of b that their Origin() have changed:
172 typename QEPrimal::IteratorGeom it;
173 for ( it = b->BeginGeomOnext(); it != b->EndGeomOnext(); it++ )
174 {
175 it.Value()->SetOrigin(newOriginId);
176 }
177 resultingOriginId = newOriginId;
178 }
179 else
180 {
181 // see TODO's entry dated 2006-01-24
182 /* We consider the following situation which depicts the Onext()
183 * rings around the point Origin = a->GetOrigin() and
184 * oldOrigin = b->GetOrigin():
185 *
186 * \ /
187 * \ /
188 * e3 e2
189 * \ /
190 * \ /
191 * ----b------oldOrg
192 *
193 * Org------a-----
194 * / \
195 * / \
196 * / \
197 * / \
198 * / \
199 * e5 e7
200 * / \
201 * / \
202 *
203 *
204 * The result of this method is then:
205 *
206 * \ /
207 * \ /
208 * e3 e2 counter-clockwise
209 * \ / Onext() order.
210 * \ /
211 * -----b------Org------a----
212 * / \
213 * / \
214 * / \
215 * / \
216 * / \
217 * e5 e6
218 * / \
219 * / \
220 *
221 * Note: in this case we must handle the geometry first and
222 * then the connectivity.
223 */
224
225 // Since this is the geometrical version of Splice() we
226 // have additional geometrical information that we should use
227 // to check the correctness of the situation.
228
229 /////////////////////////////////////////////////////////////
230 // First, consider the vertices: Origin and oldOrigin must be different.
231 PointIdentifier oldOriginId = b->GetOrigin();
232 PointIdentifier orgId = a->GetOrigin();
233
234 if ( oldOriginId == orgId )
235 {
236 itkDebugMacro("Trying to fuse the same point!");
237 return ( m_NoPoint );
238 }
239
240 /** \todo Compare the geometry of the two points and accept
241 * splicing when their geometry matches. We could fix
242 * an epsilon threshold distance above which the two points
243 * are considered distinct.
244 * PointType org = this->GetPoint(orgId);
245 */
246 PointType oldOrigin = this->GetPoint(oldOriginId);
247
248
249 /////////////////////////////////////////////////////////////
250 /* We are done with the vertices and we might need to consider the
251 * possible initial adjacent face[s]. We shall accept to proceed
252 * with Splicing if and only if the following conditions are met:
253 * [1] a and b both share the SAME Left face,
254 * [2] a and b and in the same Lnext() ring,
255 * [3] a and b are not too close followers in the Lnext() ring
256 * [this is to avoid to create a face with only two edges which
257 * is equivalent to two different edges adjacent to the same two
258 * vertices].
259 *
260 * V ---<-b---- V
261 * / \
262 * / \
263 * / a.Lnext().Lnext()
264 * / \
265 * / Face \
266 * V V
267 * \ a.Splice(b) /
268 * \ is OK /
269 * \ a.Lnext()
270 * \ /
271 * \ /
272 * V ----a->--- V
273 *
274 * Basically, we accept to proceed with spliting if there is a
275 * single face on the left and this face is at least an hexagone
276 * and the vertices we wish to splice are at least two vertices aside.
277 */
278
279 FaceRefType aLeftFace = a->GetLeft();
280 FaceRefType bLeftFace = b->GetLeft();
281
282 bool MustReconstructFace = false;
283 if ( ( aLeftFace == m_NoFace && bLeftFace != m_NoFace )
284 || ( aLeftFace != m_NoFace && bLeftFace == m_NoFace ) )
285 {
286 itkDebugMacro("Face on one side but not the other. Cancel.");
287 return ( m_NoPoint );
288 }
289
290 if ( aLeftFace != m_NoFace && bLeftFace != m_NoFace )
291 {
292 if ( ( aLeftFace == bLeftFace )
293 && ( a->GetLnext() != b )
294 && ( a->GetLnext()->GetLnext() != b )
295 && ( b->GetLnext() != a )
296 && ( b->GetLnext()->GetLnext() != a )
297 && ( a->IsInLnextRing(b) )
298 && ( b->IsInLnextRing(a) ) )
299 {
300 this->DeleteFace(aLeftFace);
301 MustReconstructFace = true;
302 }
303 else
304 {
305 itkDebugMacro("Face is not at least and hexagon.");
306 return ( m_NoPoint );
307 }
308 }
309
310 // Notice that when aLeftFace == m_NoFace and bLeftFace == m_NoFace
311 // we simply proceed... (with MustReconstructFace initialy set to
312 // false.
313
314 ///////////////////////////////////////////////////////////////
315 // Handle connectivity at QEQuadEdge level:
316 a->Splice(b);
317
318 ///////////////////////////////////////////////////////////////
319 // Back to dealing with the geometrical references. First
320 // make sure the oldOrigin's edge entry won't be used any more:
321 oldOrigin.SetEdge( (QEPrimal *)nullptr );
322 this->SetPoint(oldOriginId, oldOrigin);
323
324 // We need to inform the edges ranging from a->Onext() to b that
325 // their Origin() have changed. Let's over do it (read, be lazy) and
326 // inform the full Onext() ring:
327 typename QEPrimal::IteratorGeom it;
328 for ( it = a->BeginGeomOnext(); it != a->EndGeomOnext(); it++ )
329 {
330 it.Value()->SetOrigin(orgId);
331 }
332 resultingOriginId = oldOriginId;
333
334 ///////////////////////////////////////////////////////////////
335 // Now that we are done with the handling of the geometry of
336 // vertices proceed with the geometry of the faces. When we
337 // are spliting a face (through Splicing) we must construct two
338 // new faces:
339 if ( MustReconstructFace )
340 {
341 this->AddFace(a);
342 this->AddFace(b);
343 }
344 }
345
346 this->Modified();
347 return resultingOriginId;
348 }
349
350 /**
351 */
352 template< typename TPixel, unsigned int VDimension, typename TTraits >
353 void QuadEdgeMesh< TPixel, VDimension, TTraits >
SetCell(CellIdentifier cId,CellAutoPointer & cell)354 ::SetCell(CellIdentifier cId, CellAutoPointer & cell)
355 {
356 (void)cId;
357
358 // NOTE ALEX: should add some checking to be sure everything went fine
359 EdgeCellType * qe;
360 PolygonCellType *pe;
361
362 // The QuadEdgeMeshCellTypes first
363 if ( ( qe = dynamic_cast< EdgeCellType * >( cell.GetPointer() ) ) )
364 {
365 // NOTE ALEX: here
366 this->AddEdge( qe->GetQEGeom()->GetOrigin(),
367 qe->GetQEGeom()->GetDestination() );
368 cell.ReleaseOwnership();
369 delete qe;
370 }
371 else if ( ( pe = dynamic_cast< PolygonCellType * >( cell.GetPointer() ) ) )
372 {
373 PointIdList points;
374 PointIdInternalIterator pit = pe->InternalPointIdsBegin();
375 PointIdInternalIterator pend = pe->InternalPointIdsEnd();
376 while ( pit != pend )
377 {
378 points.push_back(*pit);
379 ++pit;
380 }
381 // NOTE ALEX: here
382 this->AddFaceWithSecurePointList(points);
383 cell.ReleaseOwnership();
384 delete pe;
385 }
386 else // non-QE cell, i.e. original itk cells for example
387 {
388 PointIdentifier numPoint = cell->GetNumberOfPoints();
389 PointIdIterator pointId = cell->PointIdsBegin();
390 PointIdIterator endId = cell->PointIdsEnd();
391 // Edge
392 if ( numPoint == 2 )
393 {
394 if ( ( pointId ) && ( endId ) && ( pointId != endId ) )
395 {
396 PointIdIterator temp = pointId++;
397 // NOTE ALEX: here
398 this->AddEdge(*pointId, *temp);
399 }
400 }
401 // polygons
402 else if ( cell->GetDimension() == 2 )
403 {
404 PointIdList points;
405 while ( pointId != endId )
406 {
407 points.push_back(*pointId);
408 ++pointId;
409 }
410 // NOTE ALEX: here
411 this->AddFace(points);
412 }
413 cell.ReleaseOwnership();
414 delete ( cell.GetPointer() );
415 }
416 }
417
418 /**
419 */
420 template< typename TPixel, unsigned int VDimension, typename TTraits >
421 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::PointIdentifier
422 QuadEdgeMesh< TPixel, VDimension, TTraits >
FindFirstUnusedPointIndex()423 ::FindFirstUnusedPointIndex()
424 {
425 PointIdentifier pid = 0;
426 PointIdentifier maxpid = this->GetNumberOfPoints();
427
428 if ( !m_FreePointIndexes.empty() )
429 {
430 // find the first valid free ID
431 do
432 {
433 pid = m_FreePointIndexes.front();
434 if ( pid < maxpid )
435 {
436 m_FreePointIndexes.pop();
437 return ( pid );
438 }
439 else
440 {
441 m_FreePointIndexes.pop();
442 }
443 }
444 while ( !m_FreePointIndexes.empty() );
445 }
446
447 if ( m_FreePointIndexes.empty() )
448 {
449 pid = this->GetNumberOfPoints();
450 if ( pid != 0 )
451 {
452 PointsContainerConstIterator last = this->GetPoints()->End();
453 last--;
454 pid = last.Index() + 1;
455 }
456 }
457 return ( pid );
458 }
459
460
461 /**
462 * The point container being a map, after deleting a point
463 * it is very likely that one index will be missing.
464 * This method "squeeze" the indexes by relocating the points
465 * and their data from the end of their respective container
466 * to the "empty" locations.
467 */
468 template< typename TPixel, unsigned int VDimension, typename TTraits >
469 void
470 QuadEdgeMesh< TPixel, VDimension, TTraits >
SqueezePointsIds()471 ::SqueezePointsIds()
472 {
473
474 // sanity check
475 if( m_FreePointIndexes.empty() )
476 {
477 return;
478 }
479
480 // Get hold on the last point in the container
481 PointsContainerPointer points = this->GetPoints();
482 PointsContainerConstIterator last = points->End();
483 --last;
484
485 // Check if there is any data
486 PointDataContainerPointer pointData = this->GetPointData();
487 bool HasPointData = ( pointData->Size() != 0 );
488
489 // if there is get hold on the last point's data
490 PointDataContainerIterator lastData = pointData->End();
491 if( HasPointData )
492 {
493 --lastData;
494 }
495
496 // Some Temp var to be used in the while loop
497 PointIdentifier FilledPointID;
498 QEType* EdgeRingEntry;
499 QEType* EdgeRingIter;
500
501 // for all the free indexes and while there is any gap
502 while( ( !m_FreePointIndexes.empty() )
503 && ( last.Index() >= this->GetNumberOfPoints() ) )
504 {
505
506 // duplicate last point into the empty slot and pop the id from freeID list
507 FilledPointID = AddPoint( GetPoint( last.Index( ) ) );
508
509 // same thing for the data if any
510 if( HasPointData )
511 {
512 pointData->SetElement(
513 FilledPointID,
514 pointData->GetElement( lastData.Index( ) )
515 );
516 }
517
518 // make sure that all the edges/faces now refer to the new ID
519 // i.e. enforce the integrity at the QE level now.
520 EdgeRingEntry = GetPoint( last.Index( ) ).GetEdge( );
521 if( EdgeRingEntry )
522 {
523 EdgeRingIter = EdgeRingEntry;
524 do
525 {
526 EdgeRingIter->SetOrigin( FilledPointID );
527 EdgeRingIter = EdgeRingIter->GetOnext( );
528 }
529 while( EdgeRingIter != EdgeRingEntry );
530 }
531
532 // pop the duplicated point from the container, increment iterator
533 points->DeleteIndex( last.Index( ) );
534 last = points->End();
535 --last;
536
537 // same thing for data, if any
538 if( HasPointData )
539 {
540 pointData->DeleteIndex( lastData.Index() );
541 lastData = pointData->End();
542 --lastData;
543 }
544
545 }
546
547 }
548
549 /**
550 */
551 template< typename TPixel, unsigned int VDimension, typename TTraits >
552 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::PointIdentifier
553 QuadEdgeMesh< TPixel, VDimension, TTraits >
AddPoint(const PointType & p)554 ::AddPoint(const PointType & p)
555 {
556 PointIdentifier pid = this->FindFirstUnusedPointIndex();
557
558 this->SetPoint(pid, p);
559 return ( pid );
560 }
561
562 /**
563 */
564 template< typename TPixel, unsigned int VDimension, typename TTraits >
565 void QuadEdgeMesh< TPixel, VDimension, TTraits >
DeletePoint(const PointIdentifier & pid)566 ::DeletePoint(const PointIdentifier & pid)
567 {
568 // We suppose point index is valid
569 // otherwise we should test with
570 // this->GetPoints()->IndexExists( pid );
571 PointType pointToDelete = this->GetPoint( pid);
572
573 // Check that there is no cell that use this point anymore
574 // i.e. that the o-next-ring is empty
575 if( pointToDelete.GetEdge() )
576 {
577 itkDebugMacro("Point is not isolated.");
578 return;
579 }
580
581 // Remove the point from the points container
582 this->GetPoints()->DeleteIndex( pid );
583
584 // Check if there is associated poindata and eventually delete them
585 if( this->GetPointData()->Size() > 0 )
586 {
587 this->GetPointData()->DeleteIndex( pid );
588 }
589
590 // store the delete index to later squeeze the ID list
591 // needed to write files that expect incremental IDs
592 // like vtk
593 m_FreePointIndexes.push( pid );
594 }
595
596 /**
597 */
598 template< typename TPixel, unsigned int VDimension, typename TTraits >
599 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::PointType
600 QuadEdgeMesh< TPixel, VDimension, TTraits >
GetPoint(const PointIdentifier & pid) const601 ::GetPoint(const PointIdentifier & pid) const
602 {
603 return ( this->GetPoints()->GetElement(pid) );
604 }
605
606 /**
607 */
608 template< typename TPixel, unsigned int VDimension, typename TTraits >
609 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::VectorType
610 QuadEdgeMesh< TPixel, VDimension, TTraits >
GetVector(const PointIdentifier & pid) const611 ::GetVector(const PointIdentifier & pid) const
612 {
613 return ( this->GetPoint(pid).GetVectorFromOrigin() );
614 }
615
616 /**
617 */
618 template< typename TPixel, unsigned int VDimension, typename TTraits >
619 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::CellIdentifier
620 QuadEdgeMesh< TPixel, VDimension, TTraits >
FindFirstUnusedCellIndex()621 ::FindFirstUnusedCellIndex()
622 {
623 CellIdentifier cid;
624
625 if ( m_FreeCellIndexes.empty() )
626 {
627 cid = this->GetNumberOfCells();
628
629 if ( cid != 0 )
630 {
631 CellsContainerIterator last = this->GetCells()->End();
632 last--;
633 cid = last.Index() + 1;
634 }
635 }
636 else
637 {
638 cid = m_FreeCellIndexes.front();
639 m_FreeCellIndexes.pop();
640 }
641
642 return ( cid );
643 }
644
645 /**
646 *\brief Construct a new edge ending at points with identifiers given
647 * as arguments.
648 * @param orgPid first endpoint (origin) of the edge to Add.
649 * @param destPid second endpoint (destination) of the edge to Add.
650 * @sa \ref GeometricalQuadEdge::InsertAfterNextBorderEdgeWithUnsetLeft
651 */
652 template< typename TPixel, unsigned int VDimension, typename TTraits >
653 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::QEPrimal *
654 QuadEdgeMesh< TPixel, VDimension, TTraits >
AddEdge(const PointIdentifier & orgPid,const PointIdentifier & destPid)655 ::AddEdge(const PointIdentifier & orgPid, const PointIdentifier & destPid)
656 {
657 // Make sure the points are different
658 if ( orgPid == destPid )
659 {
660 itkDebugMacro("Creating an edge between the same point.");
661 return ( (QEPrimal *)nullptr );
662 }
663
664 // Make sure the points are already in the QuadEdgeMesh container:
665 if ( !( this->GetPoints()->IndexExists(orgPid) )
666 || !( this->GetPoints()->IndexExists(destPid) ) )
667 {
668 itkDebugMacro("One of the points not in the PointSet.");
669 return ( (QEPrimal *)nullptr );
670 }
671
672 // Make sure the edge is not already in the container
673 QEPrimal *e = this->FindEdge(orgPid, destPid);
674 if ( e != (QEPrimal *)nullptr )
675 {
676 itkDebugMacro("Edge already in QuadEdgeMesh.");
677 return e;
678 }
679
680 // Check if the points have room to receive a new edge
681 QEPrimal *eOrigin = this->GetPoint(orgPid).GetEdge();
682
683 if ( eOrigin )
684 {
685 if ( eOrigin->IsOriginInternal() )
686 {
687 itkDebugMacro("No room for a new edge in the Origin() ring.");
688 return ( (QEPrimal *)nullptr );
689 }
690 }
691
692 QEPrimal *eDestination = this->GetPoint(destPid).GetEdge();
693
694 if ( eDestination )
695 {
696 if ( eDestination->IsOriginInternal() )
697 {
698 itkDebugMacro("No room for a new edge in the Destination() ring.");
699 return ( (QEPrimal *)nullptr );
700 }
701 }
702
703 return AddEdgeWithSecurePointList(orgPid, destPid);
704 }
705
706 template< typename TPixel, unsigned int VDimension, typename TTraits >
707 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::QEPrimal *
708 QuadEdgeMesh< TPixel, VDimension, TTraits >
AddEdgeWithSecurePointList(const PointIdentifier & orgPid,const PointIdentifier & destPid)709 ::AddEdgeWithSecurePointList(const PointIdentifier & orgPid, const PointIdentifier & destPid)
710 {
711 PointsContainerPointer points = this->GetPoints();
712
713 PointType& pOrigin = points->ElementAt(orgPid);
714 PointType& pDestination = points->ElementAt(destPid);
715
716 QEPrimal *eOrigin = pOrigin.GetEdge();
717 QEPrimal *eDestination = pDestination.GetEdge();
718
719 // Ok, there's room and the points exist
720 auto * newEdge = new EdgeCellType();
721 QEPrimal * newEdgeGeom = newEdge->GetQEGeom();
722
723 newEdgeGeom->SetOrigin (orgPid);
724 newEdgeGeom->SetDestination(destPid);
725
726 if ( !eOrigin )
727 {
728 pOrigin.SetEdge(newEdgeGeom);
729 }
730 else
731 {
732 eOrigin->InsertAfterNextBorderEdgeWithUnsetLeft(newEdgeGeom);
733 }
734
735 if ( !eDestination )
736 {
737 pDestination.SetEdge( newEdgeGeom->GetSym() );
738 }
739 else
740 {
741 eDestination->InsertAfterNextBorderEdgeWithUnsetLeft(
742 newEdgeGeom->GetSym() );
743 }
744
745 // Add it to the container
746 this->PushOnContainer(newEdge);
747
748 return ( newEdgeGeom );
749 }
750
751 /**
752 */
753 template< typename TPixel, unsigned int VDimension, typename TTraits >
754 void
755 QuadEdgeMesh< TPixel, VDimension, TTraits >
PushOnContainer(EdgeCellType * newEdge)756 ::PushOnContainer(EdgeCellType *newEdge)
757 {
758 CellIdentifier eid = 0;
759
760 if ( !this->GetEdgeCells()->empty() )
761 {
762 CellsContainerConstIterator last = this->GetEdgeCells()->End();
763 --last;
764 eid = last.Index() + 1;
765 }
766 newEdge->SetIdent(eid);
767 CellAutoPointer pEdge;
768 pEdge.TakeOwnership(newEdge);
769 this->SetEdgeCell(eid, pEdge);
770 m_NumberOfEdges++;
771 }
772
773 /**
774 */
775 template< typename TPixel, unsigned int VDimension, typename TTraits >
776 void
777 QuadEdgeMesh< TPixel, VDimension, TTraits >
DeleteEdge(const PointIdentifier & orgPid,const PointIdentifier & destPid)778 ::DeleteEdge(const PointIdentifier & orgPid, const PointIdentifier & destPid)
779 {
780 // Check if the edge exists
781 QEPrimal *e = this->FindEdge(orgPid, destPid);
782
783 if ( e == (QEPrimal *)nullptr )
784 {
785 itkDebugMacro("Edge missing in mesh.");
786 return;
787 }
788
789 this->DeleteEdge(e);
790 }
791
792 /**
793 */
794 template< typename TPixel, unsigned int VDimension, typename TTraits >
795 void
796 QuadEdgeMesh< TPixel, VDimension, TTraits >
DeleteEdge(QEPrimal * e)797 ::DeleteEdge(QEPrimal *e)
798 {
799 const PointIdentifier & orgPid = e->GetOrigin();
800 const PointIdentifier & destPid = e->GetDestination();
801
802 PointsContainerPointer points = this->GetPoints();
803
804 // Check if the Origin point's edge ring entry should be changed
805 PointType& pOrigin = points->ElementAt(orgPid);
806
807 if ( pOrigin.GetEdge() == e )
808 {
809 if ( !e->IsOriginDisconnected() )
810 {
811 pOrigin.SetEdge( e->GetOprev() );
812 }
813 else
814 {
815 pOrigin.SetEdge( (QEPrimal *)nullptr );
816 }
817 }
818
819 // Same for the Destination point
820 PointType& pDestination = points->ElementAt(destPid);
821
822 if ( pDestination.GetEdge() == e->GetSym() )
823 {
824 if ( !e->IsDestinationDisconnected() )
825 {
826 pDestination.SetEdge( e->GetLnext() );
827 }
828 else
829 {
830 pDestination.SetEdge( (QEPrimal *)nullptr );
831 }
832 }
833
834 // This container serves to avoid the MS .net bug when
835 // one wants to delete a map element using a map::iterator.
836 // Normally, if we delete a map element using an iterator,
837 // it should keep the iterator validity but .net doesn't
838 // like it, so we delay the cell deletion to a later loop.
839 using DeleteCellsCont = std::list< CellIdentifier >;
840 DeleteCellsCont cellsToDelete;
841
842 // Delete all references to 'e' in the cell container
843 CellsContainerIterator cit = this->GetCells()->Begin();
844 const CellsContainerIterator cend = this->GetCells()->End();
845
846 while ( cit != cend )
847 {
848 auto * pcell = dynamic_cast< PolygonCellType * >( cit.Value() );
849 bool toDelete = false;
850 if ( pcell != (PolygonCellType *)nullptr )
851 {
852 QEPrimal *edge = pcell->GetEdgeRingEntry();
853 typename QEPrimal::IteratorGeom it = edge->BeginGeomLnext();
854 const typename QEPrimal::IteratorGeom end = edge->EndGeomLnext();
855
856 while ( it != end && !toDelete )
857 {
858 toDelete = ( ( it.Value() == e )
859 || ( it.Value()->GetSym() == e ) );
860 ++it;
861 }
862
863 if ( toDelete )
864 {
865 --m_NumberOfFaces;
866 // handle QE level, i.e. for the polygon, just unset the faces
867 it = edge->BeginGeomLnext();
868 while ( it != end )
869 {
870 it.Value()->UnsetLeft();
871 ++it;
872 }
873 }
874 }
875
876 // if the current face is to be deleted,
877 // put it in the second container
878 // and keep the Id for next cell insertion
879 if ( toDelete )
880 {
881 cellsToDelete.push_back( cit.Index() );
882 m_FreeCellIndexes.push( cit.Index() );
883 }
884 ++cit;
885 }
886
887 // we checked all the cells i nthe container
888 // now delete the elements in the map
889 auto dit = cellsToDelete.begin();
890 const typename DeleteCellsCont::iterator dend = cellsToDelete.end();
891 while ( dit != dend )
892 {
893 const CellType *cellToBeDeleted = this->GetCells()->GetElement(*dit);
894 delete cellToBeDeleted;
895 this->GetCells()->DeleteIndex(*dit);
896 ++dit;
897 }
898
899 // now delete the edge in the edge container
900 CellType *edgeCellToDelete = this->GetEdgeCells()->ElementAt( e->GetIdent() );
901 this->GetEdgeCells()->DeleteIndex( e->GetIdent() );
902 delete edgeCellToDelete;
903 --m_NumberOfEdges;
904
905 // Now, disconnect it and let the garbage collector do the rest
906 this->Modified();
907 }
908
909 /**
910 * Delete the incoming edge and all LOCAL references to this edge.
911 * By local we mean the ones we can reasonably be aware of i.e.
912 * the adjacent faces (that we also delete) and the adjacent points
913 * (when the incoming edge is their Onext ring entry).
914 * This is to be opposed to \ref DeleteEdge that searches for ALL
915 * references to the incoming edge (which is a much heavier process
916 * because one as to make an exhaustive search in the CellContainer).
917 * \note: when deleting the adjacent faces we also handle the
918 * suppression of the references to those faces in the Lnext()
919 * and Rnext() rings.
920 * \warning Nothing is done to remove the potential isolated points
921 * left by this edge deletion (the caller might want to recycle
922 * them). Hence it is the caller's responsibility to manage the
923 * clean-up of adjacent points (when necessary).
924 */
925 template< typename TPixel, unsigned int VDimension, typename TTraits >
926 void
927 QuadEdgeMesh< TPixel, VDimension, TTraits >
LightWeightDeleteEdge(EdgeCellType * edgeCell)928 ::LightWeightDeleteEdge(EdgeCellType *edgeCell)
929 {
930 if ( !edgeCell )
931 {
932 return;
933 }
934
935 QEPrimal *e = edgeCell->GetQEGeom();
936
937 if ( !e )
938 {
939 return;
940 }
941 const PointIdentifier & orgPid = e->GetOrigin();
942 const PointIdentifier & destPid = e->GetDestination();
943
944 PointsContainerPointer points = this->GetPoints();
945
946 if ( orgPid != e->m_NoPoint && destPid != e->m_NoPoint )
947 {
948 // ------------------------------------------------------------------
949 // First make sure the points are not pointing to the edge we are
950 // trying to delete.
951
952 // Check if the Origin point's edge ring entry is the edge we are
953 // trying to delete. When this is the case shift the Origin edge entry
954 // to another edge and when no other edge is available leave it
955 // to nullptr.
956 PointType& pOrigin = points->ElementAt(orgPid);
957
958 if ( pOrigin.GetEdge() == e )
959 {
960 if ( !e->IsOriginDisconnected() )
961 {
962 pOrigin.SetEdge( e->GetOprev() );
963 }
964 else
965 {
966 pOrigin.SetEdge( (QEPrimal *)nullptr );
967 }
968 }
969
970 // Same thing for the Destination point:
971 PointType& pDestination = points->ElementAt(destPid);
972
973 if ( pDestination.GetEdge() == e->GetSym() )
974 {
975 if ( !e->IsDestinationDisconnected() )
976 {
977 pDestination.SetEdge( e->GetLnext() );
978 }
979 else
980 {
981 pDestination.SetEdge( (QEPrimal *)nullptr );
982 }
983 }
984 // ------------------------------------------------------------------
985 // Second we need to destroy the adjacent faces (both GetLeft()
986 // and GetRight() when they exist) because their very definition
987 // makes reference to the edge we are trying to delete:
988 if ( e->IsLeftSet() )
989 {
990 this->DeleteFace( e->GetLeft() );
991 }
992
993 if ( e->IsRightSet() )
994 {
995 this->DeleteFace( e->GetRight() );
996 }
997
998 /////////////////////////////////////////////////////////////////
999 // Third we need to remove from the container the EdgeCell
1000 // representing the edge we are trying to destroy at the itk
1001 // level.
1002 this->GetEdgeCells()->DeleteIndex( edgeCell->GetIdent() );
1003 edgeCell->SetIdent(0);
1004
1005 // Eventually, we disconnect (at the QuadEdge level) the edge we
1006 // are trying to delete and we delete it.
1007 e->Disconnect();
1008 }
1009
1010 --m_NumberOfEdges;
1011 delete edgeCell;
1012 this->Modified();
1013 }
1014
1015 template< typename TPixel, unsigned int VDimension, typename TTraits >
1016 void
1017 QuadEdgeMesh< TPixel, VDimension, TTraits >
LightWeightDeleteEdge(QEPrimal * e)1018 ::LightWeightDeleteEdge(QEPrimal *e)
1019 {
1020 if ( !e )
1021 {
1022 return;
1023 }
1024 const PointIdentifier & orgPid = e->GetOrigin();
1025 if ( orgPid == e->m_NoPoint )
1026 {
1027 // org not set
1028 return;
1029 }
1030
1031 const PointIdentifier & destPid = e->GetDestination();
1032 if ( destPid == e->m_NoPoint )
1033 {
1034 // dest not set
1035 return;
1036 }
1037
1038 CellIdentifier LineIdent = e->GetIdent();
1039 if ( LineIdent != m_NoPoint )
1040 {
1041 auto * edgeCell = dynamic_cast< EdgeCellType * >( this->GetEdgeCells()->GetElement(LineIdent) );
1042 this->LightWeightDeleteEdge(edgeCell);
1043 }
1044 else
1045 {
1046 itkDebugMacro("Edge Not found. LineIdent not set?");
1047 return;
1048 }
1049 }
1050
1051 /**
1052 */
1053 template< typename TPixel, unsigned int VDimension, typename TTraits >
1054 void
1055 QuadEdgeMesh< TPixel, VDimension, TTraits >
DeleteFace(FaceRefType faceToDelete)1056 ::DeleteFace(FaceRefType faceToDelete)
1057 {
1058 CellsContainerPointer cells = this->GetCells();
1059 CellType* c;
1060
1061 if( !cells->GetElementIfIndexExists( faceToDelete, &c ) )
1062 {
1063 itkDebugMacro("No such face in container");
1064 return;
1065 }
1066
1067 auto * cellToDelete = dynamic_cast< PolygonCellType * >( c );
1068 if ( !cellToDelete )
1069 {
1070 itkDebugMacro("This Id does not correspond to a face (should be an edge)");
1071 return;
1072 }
1073
1074 // Iterate on the edges adjacent to face and remove references to
1075 // to this face:
1076 QEPrimal *e = cellToDelete->GetEdgeRingEntry();
1077
1078 if ( faceToDelete != e->GetLeft() )
1079 {
1080 e = e->GetSym();
1081 }
1082
1083 if ( faceToDelete != e->GetLeft() )
1084 {
1085 itkDebugMacro("Neither e nor e->Sym() are the correct face");
1086 return;
1087 }
1088
1089 typename QEPrimal::IteratorGeom it = e->BeginGeomLnext();
1090 const typename QEPrimal::IteratorGeom end = e->EndGeomLnext();
1091
1092 while( it != end )
1093 {
1094 it.Value()->UnsetLeft();
1095 ++it;
1096 }
1097
1098 cells->DeleteIndex(faceToDelete);
1099 delete cellToDelete;
1100
1101 --m_NumberOfFaces;
1102
1103 this->Modified();
1104 }
1105
1106 /**
1107 */
1108 template< typename TPixel, unsigned int VDimension, typename TTraits >
1109 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::QEPrimal *
1110 QuadEdgeMesh< TPixel, VDimension, TTraits >
GetEdge() const1111 ::GetEdge() const
1112 {
1113 if ( this->GetEdgeCells()->empty() )
1114 {
1115 return ( (QEPrimal *)nullptr );
1116 }
1117
1118 const CellsContainer* edgeCells = this->GetEdgeCells();
1119 CellsContainerConstIterator cit = edgeCells->Begin();
1120 auto * e = dynamic_cast< EdgeCellType * >( cit.Value() );
1121
1122 return ( e->GetQEGeom() );
1123 }
1124
1125 /**
1126 */
1127 template< typename TPixel, unsigned int VDimension, typename TTraits >
1128 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::QEPrimal *
1129 QuadEdgeMesh< TPixel, VDimension, TTraits >
GetEdge(const CellIdentifier & eid) const1130 ::GetEdge(const CellIdentifier & eid) const
1131 {
1132 CellType* c;
1133
1134 if( !this->GetEdgeCells()->GetElementIfIndexExists( eid, &c ) )
1135 {
1136 itkDebugMacro("No such edge in container");
1137 return ( (QEPrimal *)nullptr );
1138 }
1139
1140 auto * e = dynamic_cast< EdgeCellType * >( c );
1141 return ( e->GetQEGeom() );
1142 }
1143
1144 /**
1145 */
1146 template< typename TPixel, unsigned int VDimension, typename TTraits >
1147 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::QEPrimal *
1148 QuadEdgeMesh< TPixel, VDimension, TTraits >
FindEdge(const PointIdentifier & pid0) const1149 ::FindEdge(const PointIdentifier & pid0) const
1150 {
1151 PointType p = this->GetPoint(pid0);
1152
1153 return ( p.GetEdge() );
1154 }
1155
1156 /**
1157 */
1158 template< typename TPixel, unsigned int VDimension, typename TTraits >
1159 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::QEPrimal *
1160 QuadEdgeMesh< TPixel, VDimension, TTraits >
FindEdge(const PointIdentifier & pid0,const PointIdentifier & pid1) const1161 ::FindEdge(const PointIdentifier & pid0, const PointIdentifier & pid1) const
1162 {
1163 QEPrimal *initialEdge = this->GetPoint(pid0).GetEdge();
1164
1165 if ( initialEdge )
1166 {
1167 typename QEPrimal::IteratorGeom it = initialEdge->BeginGeomOnext();
1168 typename QEPrimal::IteratorGeom end = initialEdge->EndGeomOnext();
1169 while ( it != end )
1170 {
1171 if ( it.Value()->GetDestination() == pid1 )
1172 {
1173 return ( dynamic_cast< QEPrimal * >( it.Value() ) );
1174 }
1175 ++it;
1176 }
1177 }
1178 return ( static_cast< QEPrimal * >( nullptr ) );
1179 }
1180
1181 /**
1182 */
1183 template< typename TPixel, unsigned int VDimension, typename TTraits >
1184 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::EdgeCellType *
1185 QuadEdgeMesh< TPixel, VDimension, TTraits >
FindEdgeCell(const PointIdentifier & pid0,const PointIdentifier & pid1) const1186 ::FindEdgeCell(const PointIdentifier & pid0, const PointIdentifier & pid1) const
1187 {
1188 auto * result = (EdgeCellType *)nullptr;
1189 QEPrimal * EdgeGeom = FindEdge(pid0, pid1);
1190
1191 if ( EdgeGeom != (QEPrimal *)nullptr )
1192 {
1193 CellIdentifier LineIdent = EdgeGeom->GetIdent();
1194 if ( LineIdent != m_NoPoint )
1195 {
1196 result = dynamic_cast< EdgeCellType * >(
1197 this->GetEdgeCells()->GetElement(LineIdent) );
1198 }
1199 }
1200 return ( result );
1201 }
1202
1203 /**
1204 */
1205 template< typename TPixel, unsigned int VDimension, typename TTraits >
1206 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::QEPrimal *
1207 QuadEdgeMesh< TPixel, VDimension, TTraits >
AddFace(const PointIdList & points)1208 ::AddFace(const PointIdList & points)
1209 {
1210 size_t N = points.size();
1211
1212 #ifndef NDEBUG
1213
1214 // Check that there are no duplicate points
1215 for ( size_t i = 0; i < N; i++ )
1216 {
1217 typename PointIdList::const_iterator itr = points.begin();
1218 typename PointIdList::const_iterator end = points.end();
1219 PointIdentifier count = NumericTraits< PointIdentifier >::ZeroValue();
1220 const PointIdentifier pointId = points[i];
1221 while ( itr != end )
1222 {
1223 if ( *itr == pointId )
1224 {
1225 ++count;
1226 }
1227 ++itr;
1228 }
1229 if ( count != 1 )
1230 {
1231 itkDebugMacro("Point " << i << " is duplicated");
1232 return ( (QEPrimal *)nullptr );
1233 }
1234 }
1235
1236 PointsContainerPointer pointsContainer = this->GetPoints();
1237
1238 // Check that all points exist
1239 for ( size_t i = 0; i < N; i++ )
1240 {
1241 if ( !pointsContainer->IndexExists(points[i]) )
1242 {
1243 itkDebugMacro("Point " << i << " is missing in the mesh");
1244 return (QEPrimal *)nullptr;
1245 }
1246 }
1247 #endif
1248
1249 // Check if existing edges have no face on the left.
1250 for ( size_t i = 0; i < N; i++ )
1251 {
1252 PointIdentifier pid0 = points[i];
1253 PointIdentifier pid1 = points[ ( i + 1 ) % N ];
1254
1255 QEPrimal *edge = this->FindEdge(pid0, pid1);
1256
1257 if ( edge )
1258 {
1259 if ( edge->IsLeftSet() )
1260 {
1261 itkDebugMacro("Edge [" << i << " " << ( ( i + 1 ) % N )
1262 << " has a left face.");
1263 return (QEPrimal *)nullptr;
1264 }
1265 }
1266 }
1267
1268 return AddFaceWithSecurePointList(points);
1269 }
1270
1271 /**
1272 */
1273 template< typename TPixel, unsigned int VDimension, typename TTraits >
1274 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::QEPrimal *
1275 QuadEdgeMesh< TPixel, VDimension, TTraits >
AddFaceWithSecurePointList(const PointIdList & points)1276 ::AddFaceWithSecurePointList(const PointIdList & points)
1277 {
1278 return AddFaceWithSecurePointList(points, true);
1279 }
1280
1281 /**
1282 */
1283 template< typename TPixel, unsigned int VDimension, typename TTraits >
1284 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::QEPrimal *
1285 QuadEdgeMesh< TPixel, VDimension, TTraits >
AddFaceWithSecurePointList(const PointIdList & points,bool CheckEdges)1286 ::AddFaceWithSecurePointList(const PointIdList & points, bool CheckEdges)
1287 {
1288 const auto numberOfPoints = static_cast< PointIdentifier >( points.size() );
1289
1290 using QEList = std::vector< QEPrimal * >;
1291 QEList FaceQEList( numberOfPoints, nullptr );
1292
1293 // Now create edge list and create missing edges if needed.
1294 for ( PointIdentifier i = 0; i < numberOfPoints; i++ )
1295 {
1296 PointIdentifier pid0 = points[i];
1297 PointIdentifier pid1 = points[( i + 1 ) % numberOfPoints];
1298 QEPrimal * edge = this->FindEdge(pid0, pid1);
1299
1300 if ( !edge && CheckEdges )
1301 {
1302 QEPrimal *entry = this->AddEdgeWithSecurePointList(pid0, pid1);
1303 if ( entry == (QEPrimal *)nullptr )
1304 {
1305 return ( entry );
1306 }
1307 FaceQEList[i] = entry;
1308 }
1309 else
1310 {
1311 //FIXME throw exception here if !edge
1312 FaceQEList[i] = edge;
1313 }
1314 }
1315
1316 // Reorder all Onext rings
1317 QEPrimal *e1;
1318 QEPrimal *e0 = FaceQEList.back();
1319
1320 auto fIt = FaceQEList.begin();
1321 auto fEnd = FaceQEList.end();
1322
1323 while( fIt != fEnd )
1324 {
1325 e1 = e0->GetSym();
1326 e0 = *fIt;
1327
1328 e0->ReorderOnextRingBeforeAddFace(e1);
1329 ++fIt;
1330 }
1331
1332 // all edges are ready to receive a face on the left
1333 QEPrimal *entry = FaceQEList.front();
1334
1335 if ( !entry )
1336 {
1337 // FIXME throw exception here instead
1338 itkDebugMacro("entry == nullptr");
1339 return (QEPrimal *)nullptr;
1340 }
1341
1342 this->AddFace(entry);
1343
1344 return ( entry );
1345 }
1346
1347 /**
1348 * We here make the strong assumption that the caller was wise enough
1349 * to build/handle the connectivity at the QE level. This method
1350 * simply creates a new PolygonCell and assigns it as the left face
1351 * of all edges in the Lnext ring of the incoming argument.
1352 */
1353 template< typename TPixel, unsigned int VDimension, typename TTraits >
1354 void
1355 QuadEdgeMesh< TPixel, VDimension, TTraits >
AddFace(QEPrimal * entry)1356 ::AddFace(QEPrimal *entry)
1357 {
1358 // Create the cell and add it to the container
1359 auto * faceCell = new PolygonCellType(entry);
1360 CellIdentifier fid = this->FindFirstUnusedCellIndex();
1361
1362 faceCell->SetIdent(fid);
1363
1364 // Associate the above generated CellIndex as the default FaceRefType
1365 // of the new face [ i.e. use the itk level CellIdentifier as the
1366 // GeometricalQuadEdge::m_Origin of dual edges (edges of type QEDual) ].
1367 typename QEPrimal::IteratorGeom it = entry->BeginGeomLnext();
1368 typename QEPrimal::IteratorGeom end = entry->EndGeomLnext();
1369
1370 while( it != end )
1371 {
1372 it.Value()->SetLeft(fid);
1373 ++it;
1374 }
1375
1376 ++m_NumberOfFaces;
1377 CellAutoPointer face;
1378 face.TakeOwnership(faceCell);
1379 this->Superclass::SetCell(fid, face);
1380 }
1381
1382 /**
1383 * Add a triangle face to this QuadEdgeMesh.
1384 * @param aPid \ref PointIdentifier of first point
1385 * @param bPid \ref PointIdentifier of second point
1386 * @param cPid \ref PointIdentifier of third point
1387 */
1388 template< typename TPixel, unsigned int VDimension, typename TTraits >
1389 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::QEPrimal *
1390 QuadEdgeMesh< TPixel, VDimension, TTraits >
AddFaceTriangle(const PointIdentifier & aPid,const PointIdentifier & bPid,const PointIdentifier & cPid)1391 ::AddFaceTriangle(
1392 const PointIdentifier & aPid,
1393 const PointIdentifier & bPid,
1394 const PointIdentifier & cPid)
1395 {
1396 PointIdList points( 3 );
1397
1398 points[0] = aPid;
1399 points[1] = bPid;
1400 points[2] = cPid;
1401 return this->AddFace(points);
1402 }
1403
1404 /**
1405 */
1406 template< typename TPixel, unsigned int VDimension, typename TTraits >
1407 QuadEdgeMesh< TPixel, VDimension, TTraits >
QuadEdgeMesh()1408 ::QuadEdgeMesh():m_NumberOfFaces(0), m_NumberOfEdges(0)
1409 {
1410 m_EdgeCellsContainer = CellsContainer::New();
1411 }
1412
1413 template< typename TPixel, unsigned int VDimension, typename TTraits >
1414 QuadEdgeMesh< TPixel, VDimension, TTraits >
~QuadEdgeMesh()1415 ::~QuadEdgeMesh()
1416 {
1417 this->ClearCellsContainer();
1418 }
1419
1420 template< typename TPixel, unsigned int VDimension, typename TTraits >
1421 void
1422 QuadEdgeMesh< TPixel, VDimension, TTraits >
ClearCellsContainer()1423 ::ClearCellsContainer()
1424 {
1425 if ( m_EdgeCellsContainer->GetReferenceCount() == 1 )
1426 {
1427 CellsContainerIterator EdgeCell = m_EdgeCellsContainer->Begin();
1428 CellsContainerIterator EdgeEnd = m_EdgeCellsContainer->End();
1429 while ( EdgeCell != EdgeEnd )
1430 {
1431 const CellType *EdgeCellToBeDeleted = EdgeCell->Value();
1432 delete EdgeCellToBeDeleted;
1433 ++EdgeCell;
1434 }
1435 m_EdgeCellsContainer->Initialize();
1436 }
1437 }
1438
1439 /**
1440 */
1441 template< typename TPixel, unsigned int VDimension, typename TTraits >
1442 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::CoordRepType
1443 QuadEdgeMesh< TPixel, VDimension, TTraits >
ComputeEdgeLength(QEPrimal * e)1444 ::ComputeEdgeLength(QEPrimal *e)
1445 {
1446 const PointsContainer *points = this->GetPoints();
1447
1448 const PointType org = points->GetElement( e->GetOrigin() );
1449 const PointType dest = points->GetElement( e->GetDestination() );
1450
1451 return org.EuclideanDistanceTo(dest);
1452 }
1453
1454 /**
1455 * \brief Compute the total number of USED points. This differs from
1456 * \ref Mesh::GetNumberOfPoints() that will return the total number of
1457 * points including the ones that have no entry in the edge ring.
1458 *
1459 * \note This method is an optional utility of the class: its
1460 * understanding is not useful at first contact with the class.
1461 */
1462 template< typename TPixel, unsigned int VDimension, typename TTraits >
1463 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::PointIdentifier
1464 QuadEdgeMesh< TPixel, VDimension, TTraits >
ComputeNumberOfPoints() const1465 ::ComputeNumberOfPoints() const
1466 {
1467 const PointsContainer *points = this->GetPoints();
1468
1469 if ( !points )
1470 {
1471 itkDebugMacro("No point container");
1472 return ( 0 );
1473 }
1474
1475 PointIdentifier numberOfPoints = NumericTraits<PointIdentifier>::ZeroValue();
1476 PointsContainerConstIterator pointIterator = points->Begin();
1477 PointsContainerConstIterator pointEnd = points->End();
1478
1479 while ( pointIterator != pointEnd )
1480 {
1481 if ( pointIterator.Value().GetEdge() )
1482 {
1483 ++numberOfPoints;
1484 }
1485 ++pointIterator;
1486 }
1487
1488 return ( numberOfPoints );
1489 }
1490
1491 /**
1492 * \brief Compute the total number of faces.
1493 *
1494 * \note This method is an optional utility of the class: its
1495 * understanding is not useful at first contact with the class.
1496 */
1497 template< typename TPixel, unsigned int VDimension, typename TTraits >
1498 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::CellIdentifier
1499 QuadEdgeMesh< TPixel, VDimension, TTraits >
ComputeNumberOfFaces() const1500 ::ComputeNumberOfFaces() const
1501 {
1502 CellIdentifier numberOfFaces = NumericTraits<CellIdentifier>::ZeroValue();
1503 CellsContainerConstIterator cellIterator = this->GetCells()->Begin();
1504 CellsContainerConstIterator cellEnd = this->GetCells()->End();
1505
1506 PointIdentifier NumOfPoints;
1507
1508 while ( cellIterator != cellEnd )
1509 {
1510 NumOfPoints = cellIterator.Value()->GetNumberOfPoints();
1511 if ( NumOfPoints > 2 )
1512 {
1513 ++numberOfFaces;
1514 }
1515 ++cellIterator;
1516 }
1517
1518 return ( numberOfFaces );
1519 }
1520
1521 /**
1522 * \brief Compute the total number of edges.
1523 *
1524 * \note This method is an optional utility of the class: it's
1525 * understanding is not useful at first contact with the class.
1526 */
1527 template< typename TPixel, unsigned int VDimension, typename TTraits >
1528 typename QuadEdgeMesh< TPixel, VDimension, TTraits >::CellIdentifier
1529 QuadEdgeMesh< TPixel, VDimension, TTraits >
ComputeNumberOfEdges() const1530 ::ComputeNumberOfEdges() const
1531 {
1532 return static_cast< CellIdentifier >( this->GetEdgeCells()->size() );
1533 }
1534 } // namespace itk
1535
1536 #endif
1537