map2.hpp 28.7 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1
2
3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2012, IGG Team, LSIIT, University of Strasbourg           *
Pierre Kraemer's avatar
Pierre Kraemer committed
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
*                                                                              *
* This library is free software; you can redistribute it and/or modify it      *
* under the terms of the GNU Lesser General Public License as published by the *
* Free Software Foundation; either version 2.1 of the License, or (at your     *
* option) any later version.                                                   *
*                                                                              *
* This library is distributed in the hope that it will be useful, but WITHOUT  *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License  *
* for more details.                                                            *
*                                                                              *
* You should have received a copy of the GNU Lesser General Public License     *
* along with this library; if not, write to the Free Software Foundation,      *
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.           *
*                                                                              *
20
* Web site: http://cgogn.unistra.fr/                                           *
Pierre Kraemer's avatar
Pierre Kraemer committed
21
22
23
24
25
26
27
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

namespace CGoGN
{

Pierre Kraemer's avatar
Pierre Kraemer committed
28
29
template <typename MAP_IMPL>
inline void Map2<MAP_IMPL>::init()
Pierre Kraemer's avatar
Pierre Kraemer committed
30
{
Pierre Kraemer's avatar
Pierre Kraemer committed
31
	MAP_IMPL::addInvolution() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
32
33
}

Pierre Kraemer's avatar
Pierre Kraemer committed
34
35
template <typename MAP_IMPL>
inline Map2<MAP_IMPL>::Map2() : Map1<MAP_IMPL>()
36
37
38
39
{
	init() ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
40
41
template <typename MAP_IMPL>
inline std::string Map2<MAP_IMPL>::mapTypeName() const
Pierre Kraemer's avatar
Pierre Kraemer committed
42
43
44
45
{
	return "Map2" ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
46
47
template <typename MAP_IMPL>
inline unsigned int Map2<MAP_IMPL>::dimension() const
Pierre Kraemer's avatar
Pierre Kraemer committed
48
49
50
51
{
	return 2 ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
52
53
template <typename MAP_IMPL>
inline void Map2<MAP_IMPL>::clear(bool removeAttrib)
54
{
55
	ParentMap::clear(removeAttrib) ;
Sylvain Thery's avatar
Sylvain Thery committed
56
57
	if (removeAttrib)
		init() ;
58
59
}

Pierre Kraemer's avatar
Pierre Kraemer committed
60
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
61
inline unsigned int Map2<MAP_IMPL>::getNbInvolutions() const
Sylvain Thery's avatar
Sylvain Thery committed
62
{
Pierre Kraemer's avatar
Pierre Kraemer committed
63
64
65
66
67
68
69
	return 1 + ParentMap::getNbInvolutions();
}

template <typename MAP_IMPL>
inline unsigned int Map2<MAP_IMPL>::getNbPermutations() const
{
	return ParentMap::getNbPermutations();
Sylvain Thery's avatar
Sylvain Thery committed
70
71
}

Pierre Kraemer's avatar
Pierre Kraemer committed
72
73
74
75
/*! @name Basic Topological Operators
 * Access and Modification
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
76
77
template <typename MAP_IMPL>
inline Dart Map2<MAP_IMPL>::phi2(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
78
{
Pierre Kraemer's avatar
Pierre Kraemer committed
79
	return MAP_IMPL::template getInvolution<0>(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
80
81
}

Pierre Kraemer's avatar
Pierre Kraemer committed
82
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
83
template <int N>
Pierre Kraemer's avatar
Pierre Kraemer committed
84
inline Dart Map2<MAP_IMPL>::phi(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
85
86
87
88
89
90
{
	assert( (N > 0) || !"negative parameters not allowed in template multi-phi");
	if (N < 10)
	{
		switch(N)
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
91
			case 1 : return this->phi1(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
92
93
94
95
96
97
			case 2 : return phi2(d) ;
			default : assert(!"Wrong multi-phi relation value") ; return d ;
		}
	}
	switch(N%10)
	{
98
		case 1 : return this->phi1(phi<N/10>(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
99
100
101
102
103
		case 2 : return phi2(phi<N/10>(d)) ;
		default : assert(!"Wrong multi-phi relation value") ; return d ;
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
104
105
template <typename MAP_IMPL>
inline Dart Map2<MAP_IMPL>::alpha0(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
106
107
108
109
{
	return phi2(d) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
110
111
template <typename MAP_IMPL>
inline Dart Map2<MAP_IMPL>::alpha1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
112
{
113
	return phi2(this->phi_1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
114
115
}

Pierre Kraemer's avatar
Pierre Kraemer committed
116
117
template <typename MAP_IMPL>
inline Dart Map2<MAP_IMPL>::alpha_1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
118
{
119
	return this->phi1(phi2(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
120
121
}

Pierre Kraemer's avatar
Pierre Kraemer committed
122
123
template <typename MAP_IMPL>
inline Dart Map2<MAP_IMPL>::phi2_1(Dart d) const
124
{
125
	return phi2(this->phi_1(d)) ;
126
127
}

Pierre Kraemer's avatar
Pierre Kraemer committed
128
129
template <typename MAP_IMPL>
inline Dart Map2<MAP_IMPL>::phi12(Dart d) const
130
{
Pierre Kraemer's avatar
Pierre Kraemer committed
131
	return this->phi1(phi2(d)) ;
132
133
}

Pierre Kraemer's avatar
Pierre Kraemer committed
134
135
template <typename MAP_IMPL>
inline void Map2<MAP_IMPL>::phi2sew(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
136
{
Pierre Kraemer's avatar
Pierre Kraemer committed
137
	MAP_IMPL::template involutionSew<0>(d,e);
Pierre Kraemer's avatar
Pierre Kraemer committed
138
139
}

Pierre Kraemer's avatar
Pierre Kraemer committed
140
141
template <typename MAP_IMPL>
inline void Map2<MAP_IMPL>::phi2unsew(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
142
{
Pierre Kraemer's avatar
Pierre Kraemer committed
143
	MAP_IMPL::template involutionUnsew<0>(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
144
145
}

146
147
148
149
/*! @name Generator and Deletor
 *  To generate or delete faces in a 2-map
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
150
151
template <typename MAP_IMPL>
Dart Map2<MAP_IMPL>::newPolyLine(unsigned int nbEdges)
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
{
	Dart d = ParentMap::newCycle(2*nbEdges);
	{
		Dart it1 = d;
		Dart it2 = this->phi_1(d);
		for(unsigned int i = 0; i < nbEdges ; ++i)
		{
			phi2sew(it1, it2);
			it1 = this->phi1(it1);
			it2 = this->phi_1(it2);
		}
	}
	return d;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
167
168
template <typename MAP_IMPL>
Dart Map2<MAP_IMPL>::newFace(unsigned int nbEdges, bool withBoundary)
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
{
	Dart d = ParentMap::newCycle(nbEdges);
	if (withBoundary)
	{
		Dart e = newBoundaryCycle(nbEdges);

		Dart it = d;
		do
		{
			phi2sew(it, e);
			it = this->phi1(it);
			e = this->phi_1(e);
		} while (it != d);
	}
	return d;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
186
template <typename MAP_IMPL>
187
void Map2<MAP_IMPL>::deleteFace(Dart d)
188
{
Pierre Kraemer's avatar
Pierre Kraemer committed
189
	assert(!this->template isBoundaryMarked<2>(d)) ;
190

191
192
193
	Dart it = d ;
	do
	{
194
195
		if(!isBoundaryEdge(it))
			unsewFaces(it) ;
196
197
		it = this->phi1(it) ;
	} while(it != d) ;
198
199
200
	Dart dd = phi2(d) ;
	ParentMap::deleteCycle(d) ;
	ParentMap::deleteCycle(dd) ;
201
202
}

Pierre Kraemer's avatar
Pierre Kraemer committed
203
204
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::deleteCC(Dart d)
205
{
206
	DartMarkerNoUnmark<MAP_IMPL> mark(*this);
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

	std::vector<Dart> visited;
	visited.reserve(1024) ;
	visited.push_back(d);
	mark.mark(d) ;

	for(unsigned int i = 0; i < visited.size(); ++i)
	{
		Dart d1 = this->phi1(visited[i]) ;
		if(!mark.isMarked(d1))
		{
			visited.push_back(d1) ;
			mark.mark(d1);
		}
		Dart d2 = phi2(visited[i]) ;
		if(!mark.isMarked(d2))
		{
			visited.push_back(d2) ;
			mark.mark(d2);
		}
	}

	for(std::vector<Dart>::iterator it = visited.begin(); it != visited.end(); ++it)
		this->deleteDart(*it) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
233
234
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::fillHole(Dart d)
235
236
{
	assert(isBoundaryEdge(d)) ;
237
238
	if(!this->template isBoundaryMarked<2>(d))
		d = phi2(d) ;
239
	this->template boundaryUnmarkOrbit<2,FACE>(d) ;
240
241
}

Pierre Kraemer's avatar
Pierre Kraemer committed
242
243
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::createHole(Dart d)
244
245
{
	assert(!isBoundaryEdge(d)) ;
246
	this->template boundaryMarkOrbit<2,FACE>(d) ;
247
248
249
250
251
252
}

/*! @name Topological Operators
 *  Topological operations on 2-maps
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
253
254
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::splitVertex(Dart d, Dart e)
255
256
257
258
259
260
261
262
263
{
	assert(sameVertex(d, e)) ;
	Dart d2 = phi2(d) ; assert(d != d2) ;
	Dart e2 = phi2(e) ; assert(e != e2) ;
	Dart nd = ParentMap::cutEdge(d2) ;	// Cut the edge of dd (make a new half edge)
	Dart ne = ParentMap::cutEdge(e2) ;	// Cut the edge of ee (make a new half edge)
	phi2sew(nd, ne) ;					// Sew the two faces along the new edge
}

Pierre Kraemer's avatar
Pierre Kraemer committed
264
265
template <typename MAP_IMPL>
Dart Map2<MAP_IMPL>::deleteVertex(Dart d)
266
267
268
269
270
271
272
273
274
275
276
277
{
	//TODO utile ?
	if(isBoundaryVertex(d))
		return NIL ;

	Dart res = NIL ;
	Dart vit = d ;
	do
	{
		if(res == NIL && this->phi1(this->phi1(d)) != d)
			res = this->phi1(d) ;

278
		Dart f = this->phi_1(phi2(vit)) ;
279
280
281
282
283
284
285
286
		this->phi1sew(vit, f) ;

		vit = phi2(this->phi_1(vit)) ;
	} while(vit != d) ;
	ParentMap::deleteCycle(d) ;
	return res ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
287
288
template <typename MAP_IMPL>
Dart Map2<MAP_IMPL>::cutEdge(Dart d)
289
290
291
292
293
294
295
296
297
298
{
	Dart e = phi2(d);
	phi2unsew(d);						// remove old phi2 links
	Dart nd = ParentMap::cutEdge(d);	// Cut the 1-edge of d
	Dart ne = ParentMap::cutEdge(e);	// Cut the 1-edge of phi2(d)
	phi2sew(d, ne);						// Correct the phi2 links
	phi2sew(e, nd);
	return nd;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
299
300
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::uncutEdge(Dart d)
301
302
303
304
305
306
307
308
309
310
311
312
313
314
{
	if(vertexDegree(this->phi1(d)) == 2)
	{
		Dart e = phi2(this->phi1(d)) ;
		phi2unsew(e) ;
		phi2unsew(d) ;
		ParentMap::uncutEdge(d) ;
		ParentMap::uncutEdge(e) ;
		phi2sew(d, e) ;
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
315
316
template <typename MAP_IMPL>
Dart Map2<MAP_IMPL>::collapseEdge(Dart d, bool delDegenerateFaces)
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
{
	Dart resV = NIL ;

	Dart e = phi2(d);
	phi2unsew(d);	// Unlink the opposite edges

	Dart f = this->phi1(e) ;
	Dart h = phi2(this->phi_1(e));

	if (h != e)
		resV = h;

	if (f != e && delDegenerateFaces)
	{
		ParentMap::collapseEdge(e) ;	// Collapse edge e
		collapseDegeneratedFace(f) ;	// and collapse its face if degenerated
	}
	else
		ParentMap::collapseEdge(e) ;	// Just collapse edge e

	f = this->phi1(d) ;
	if(resV == NIL)
	{
		h = phi2(this->phi_1(d));
		if (h != d)
			resV = h;
	}

	if (f != d && delDegenerateFaces)
	{
		ParentMap::collapseEdge(d) ;	// Collapse edge d
		collapseDegeneratedFace(f) ;	// and collapse its face if degenerated
	}
	else
		ParentMap::collapseEdge(d) ;	// Just collapse edge d

	return resV ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
356
357
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::flipEdge(Dart d)
358
{
359
	if (!isBoundaryEdge(d)) // cannot flip a boundary edge
360
361
362
363
364
365
366
367
368
369
370
371
	{
		Dart e = phi2(d);
		Dart dNext = this->phi1(d);
		Dart eNext = this->phi1(e);
		Dart dPrev = this->phi_1(d);
		Dart ePrev = this->phi_1(e);
		this->phi1sew(d, ePrev);	// Detach the two
		this->phi1sew(e, dPrev);	// vertices of the edge
		this->phi1sew(d, dNext);	// Insert the edge in its
		this->phi1sew(e, eNext);	// new vertices after flip
		return true ;
	}
372
	return false ;
373
374
}

Pierre Kraemer's avatar
Pierre Kraemer committed
375
376
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::flipBackEdge(Dart d)
377
{
378
	if (!isBoundaryEdge(d)) // cannot flip a boundary edge
379
380
381
382
	{
		Dart e = phi2(d);
		Dart dPrev = this->phi_1(d);
		Dart ePrev = this->phi_1(e);
383
384
		this->phi1sew(d, ePrev);				// Detach the two
		this->phi1sew(e, dPrev);				// vertices of the edge
385
386
387
388
		this->phi1sew(e, this->phi_1(dPrev));	// Insert the edge in its
		this->phi1sew(d, this->phi_1(ePrev));	// new vertices after flip
		return true ;
	}
389
	return false ;
390
391
}

Pierre Kraemer's avatar
Pierre Kraemer committed
392
393
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::swapEdges(Dart d, Dart e)
394
{
395
	assert(!isBoundaryEdge(d) && !isBoundaryEdge(e));
396
397
398
399
400
401
402
403
404
405
406

	Dart d2 = phi2(d);
	Dart e2 = phi2(e);

	phi2unsew(d);
	phi2unsew(e) ;

	phi2sew(d, e);
	phi2sew(d2, e2);
}

Pierre Kraemer's avatar
Pierre Kraemer committed
407
408
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::insertEdgeInVertex(Dart d, Dart e)
409
410
411
{
	assert(!sameVertex(d,e));
	assert(phi2(e) == this->phi_1(e));
412
	this->phi1sew(this->phi_1(d), this->phi_1(e));
413
414
}

Pierre Kraemer's avatar
Pierre Kraemer committed
415
416
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::removeEdgeFromVertex(Dart d)
417
418
419
420
421
422
423
424
425
{
	if (!isBoundaryEdge(d))
	{
		this->phi1sew(this->phi_1(d), phi2(d)) ;
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
426
427
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::sewFaces(Dart d, Dart e, bool withBoundary)
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
{
	// if sewing with fixed points
	if (!withBoundary)
	{
		assert(phi2(d) == d && phi2(e) == e) ;
		phi2sew(d, e) ;
		return ;
	}

	assert(isBoundaryEdge(d) && isBoundaryEdge(e)) ;

	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;

	phi2unsew(d) ;	// unsew faces from boundary
	phi2unsew(e) ;

	if (ee != this->phi_1(dd))
		this->phi1sew(ee, this->phi_1(dd)) ;	// remove the boundary edge
	if (dd != this->phi_1(ee))
		this->phi1sew(dd, this->phi_1(ee)) ;	// and properly close incident boundaries
	ParentMap::deleteCycle(dd) ;

	phi2sew(d, e) ; // sew the faces
}

Pierre Kraemer's avatar
Pierre Kraemer committed
454
455
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::unsewFaces(Dart d, bool withBoundary)
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
{
	if (!withBoundary)
	{
		phi2unsew(d) ;
		return ;
	}

	assert(!Map2::isBoundaryEdge(d)) ;

	Dart dd = phi2(d) ;

	Dart e = newBoundaryCycle(2) ;
	Dart ee = this->phi1(e) ;

	Dart f = findBoundaryEdgeOfVertex(d) ;
	Dart ff = findBoundaryEdgeOfVertex(dd) ;

	if(f != NIL)
		this->phi1sew(e, this->phi_1(f)) ;

	if(ff != NIL)
		this->phi1sew(ee, this->phi_1(ff)) ;

	phi2unsew(d) ;

	phi2sew(d, e) ;		// sew faces
	phi2sew(dd, ee) ;	// to the boundary
}

Pierre Kraemer's avatar
Pierre Kraemer committed
485
486
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::collapseDegeneratedFace(Dart d)
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
{
	Dart e = this->phi1(d) ;		// Check if the face is degenerated
	if (this->phi1(e) == d)			// Yes: it contains one or two edge(s)
	{
		Dart d2 = phi2(d) ;			// Check opposite edges
		Dart e2 = phi2(e) ;
		phi2unsew(d) ;
		if(d != e)
		{
			phi2unsew(e) ;
			phi2sew(d2, e2) ;
		}
		else
		{
			this->phi1sew(d2, this->phi_1(d2)) ;
			ParentMap::deleteCycle(d2) ;
		}
		ParentMap::deleteCycle(d) ;
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
510
511
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::splitFace(Dart d, Dart e)
512
{
Pierre Kraemer's avatar
Pierre Kraemer committed
513
	assert(d != e && Map2<MAP_IMPL>::sameFace(d, e)) ;
514
515
516
517
518
519
	Dart dd = ParentMap::cutEdge(this->phi_1(d)) ;
	Dart ee = ParentMap::cutEdge(this->phi_1(e)) ;
	ParentMap::splitCycle(dd, ee) ;
	phi2sew(dd, ee);
}

Pierre Kraemer's avatar
Pierre Kraemer committed
520
521
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::mergeFaces(Dart d)
522
523
524
525
526
527
528
529
530
531
532
533
534
{
	if (!isBoundaryEdge(d))
	{
		Dart e = phi2(d) ;
		phi2unsew(d) ;
		ParentMap::mergeCycles(d, this->phi1(e)) ;
		ParentMap::splitCycle(e, this->phi1(d)) ;
		ParentMap::deleteCycle(d) ;
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
535
536
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::extractTrianglePair(Dart d)
537
538
539
{
	Dart e = phi2(d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
540
	assert(!isFaceIncidentToBoundary(d) && !isFaceIncidentToBoundary(e)) ;
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
	assert(faceDegree(d) == 3 && faceDegree(e) == 3) ;

	Dart d1 = phi2(this->phi1(d)) ;
	Dart d2 = phi2(this->phi_1(d)) ;
	phi2unsew(d1) ;
	phi2unsew(d2) ;
	phi2sew(d1, d2) ;

	Dart e1 = phi2(this->phi1(e)) ;
	Dart e2 = phi2(this->phi_1(e)) ;
	phi2unsew(e1) ;
	phi2unsew(e2) ;
	phi2sew(e1, e2) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
556
557
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::insertTrianglePair(Dart d, Dart v1, Dart v2)
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
{
	Dart e = phi2(d) ;

	assert(v1 != v2 && sameOrientedVertex(v1, v2)) ;
	assert(faceDegree(d) == 3 && faceDegree(phi2(d)) == 3) ;

	Dart vv1 = phi2(v1) ;
	phi2unsew(v1) ;
	phi2sew(this->phi_1(d), v1) ;
	phi2sew(this->phi1(d), vv1) ;

	Dart vv2 = phi2(v2) ;
	phi2unsew(v2) ;
	phi2sew(this->phi_1(e), v2) ;
	phi2sew(this->phi1(e), vv2) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
575
576
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::mergeVolumes(Dart d, Dart e, bool deleteFace)
577
{
Pierre Kraemer's avatar
Pierre Kraemer committed
578
	assert(!this->template isBoundaryMarked<2>(d) && !this->template isBoundaryMarked<2>(e)) ;
579

Pierre Kraemer's avatar
Pierre Kraemer committed
580
	if (isFaceIncidentToBoundary(d) || isFaceIncidentToBoundary(e))
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
		return false;

	// First traversal of both faces to check the face sizes
	// and store their edges to efficiently access them further

	std::vector<Dart> dDarts;
	std::vector<Dart> eDarts;
	dDarts.reserve(16);		// usual faces have less than 16 edges
	eDarts.reserve(16);

	Dart dFit = d ;
	Dart eFit = this->phi1(e) ;	// must take phi1 because of the use
	do							// of reverse iterator for sewing loop
	{
		dDarts.push_back(dFit) ;
		dFit = this->phi1(dFit) ;
	} while(dFit != d) ;
	do
	{
		eDarts.push_back(eFit) ;
		eFit = this->phi1(eFit) ;
	} while(eFit != this->phi1(e)) ;

	if(dDarts.size() != eDarts.size())
		return false ;

	// Make the sewing: take darts in initial order (clockwise) in first face
	// and take darts in reverse order (counter-clockwise) in the second face
	std::vector<Dart>::iterator dIt;
	std::vector<Dart>::reverse_iterator eIt;
	for (dIt = dDarts.begin(), eIt = eDarts.rbegin(); dIt != dDarts.end(); ++dIt, ++eIt)
	{
		Dart d2 = phi2(*dIt);	// Search the faces adjacent to dNext and eNext
		Dart e2 = phi2(*eIt);
		phi2unsew(d2);		// Unlink the two adjacent faces from dNext and eNext
		phi2unsew(e2);
		phi2sew(d2, e2);	// Link the two adjacent faces together
	}

	if(deleteFace)
	{
		ParentMap::deleteCycle(d);		// Delete the two alone faces
		ParentMap::deleteCycle(e);
	}

	return true ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
629
630
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::splitSurface(std::vector<Dart>& vd, bool firstSideClosed, bool secondSideClosed)
631
632
633
634
635
636
637
638
639
{
//	assert(checkSimpleOrientedPath(vd)) ;

	Dart e = vd.front() ;
	Dart e2 = phi2(e) ;

	//unsew the edge path
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
640
		//if(!Map2<MAP_IMPL>::isBoundaryEdge(*it))
641
642
643
644
			unsewFaces(*it) ;
	}

	if(firstSideClosed)
645
		fillHole(e) ;
646
647

	if(secondSideClosed)
648
		fillHole(e2) ;
649
650
}

Pierre Kraemer's avatar
Pierre Kraemer committed
651
652
653
654
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
655
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
656
bool Map2<MAP_IMPL>::sameOrientedVertex(Vertex v1, Vertex v2) const
657
{
Pierre Kraemer's avatar
Pierre Kraemer committed
658
	Dart it = v1.dart;			// Foreach dart in vertex v1
659
660
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
661
		if (it == v2.dart)		// Test equality with v2
662
663
			return true;
		it = phi2(this->phi_1(it));
Pierre Kraemer's avatar
Pierre Kraemer committed
664
	} while (it != v1.dart);
665
666
667
	return false;				// None is equal to e => vertices are distinct
}

Pierre Kraemer's avatar
Pierre Kraemer committed
668
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
669
inline bool Map2<MAP_IMPL>::sameVertex(Vertex v1, Vertex v2) const
Pierre Kraemer's avatar
Pierre Kraemer committed
670
{
Pierre Kraemer's avatar
Pierre Kraemer committed
671
	return sameOrientedVertex(v1, v2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
672
673
}

Pierre Kraemer's avatar
Pierre Kraemer committed
674
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
675
unsigned int Map2<MAP_IMPL>::vertexDegree(Vertex v) const
676
677
{
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
678
	Dart it = v.dart ;
679
680
681
682
	do
	{
		++count ;
		it = phi2(this->phi_1(it)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
683
	} while (it != v.dart) ;
684
685
686
	return count ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
687
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
688
int Map2<MAP_IMPL>::checkVertexDegree(Vertex v, unsigned int vd) const
689
690
{
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
691
	Dart it = v.dart ;
692
693
694
695
	do
	{
		++count ;
		it = phi2(this->phi_1(it)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
696
	} while ((count <= vd) && (it != v.dart)) ;
697
698
699
700

	return count - vd;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
701
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
702
bool Map2<MAP_IMPL>::isBoundaryVertex(Vertex v) const
703
{
Pierre Kraemer's avatar
Pierre Kraemer committed
704
	Dart it = v.dart ;
705
706
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
707
		if (this->template isBoundaryMarked<2>(it))
708
709
			return true ;
		it = phi2(this->phi_1(it)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
710
	} while (it != v.dart) ;
711
712
713
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
714
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
715
Dart Map2<MAP_IMPL>::findBoundaryEdgeOfVertex(Vertex v) const
716
{
Pierre Kraemer's avatar
Pierre Kraemer committed
717
	Dart it = v.dart ;
718
719
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
720
		if (this->template isBoundaryMarked<2>(it))
721
722
			return it ;
		it = phi2(this->phi_1(it)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
723
	} while (it != v.dart) ;
724
725
726
	return NIL ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
727
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
728
inline bool Map2<MAP_IMPL>::sameEdge(Edge e1, Edge e2) const
Pierre Kraemer's avatar
Pierre Kraemer committed
729
{
Pierre Kraemer's avatar
Pierre Kraemer committed
730
	return e1.dart == e2.dart || phi2(e1.dart) == e2.dart ;
Pierre Kraemer's avatar
Pierre Kraemer committed
731
732
}

Pierre Kraemer's avatar
Pierre Kraemer committed
733
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
734
inline bool Map2<MAP_IMPL>::isBoundaryEdge(Edge e) const
untereiner's avatar
untereiner committed
735
{
Pierre Kraemer's avatar
Pierre Kraemer committed
736
	return this->template isBoundaryMarked<2>(e.dart) || this->template isBoundaryMarked<2>(phi2(e.dart));
untereiner's avatar
untereiner committed
737
738
}

Pierre Kraemer's avatar
Pierre Kraemer committed
739
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
740
inline bool Map2<MAP_IMPL>::sameOrientedFace(Face f1, Face f2) const
741
{
Pierre Kraemer's avatar
Pierre Kraemer committed
742
	return ParentMap::sameCycle(f1, f2) ;
743
744
}

Pierre Kraemer's avatar
Pierre Kraemer committed
745
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
746
inline bool Map2<MAP_IMPL>::sameFace(Face f1, Face f2) const
747
{
Pierre Kraemer's avatar
Pierre Kraemer committed
748
	return sameOrientedFace(f1, f2) ;
749
750
}

Pierre Kraemer's avatar
Pierre Kraemer committed
751
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
752
inline unsigned int Map2<MAP_IMPL>::faceDegree(Face f) const
753
{
Pierre Kraemer's avatar
Pierre Kraemer committed
754
	return ParentMap::cycleDegree(f) ;
755
756
}

Pierre Kraemer's avatar
Pierre Kraemer committed
757
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
758
inline int Map2<MAP_IMPL>::checkFaceDegree(Face f, unsigned int fd) const
759
{
Pierre Kraemer's avatar
Pierre Kraemer committed
760
	return ParentMap::checkCycleDegree(f, fd) ;
761
762
}

Pierre Kraemer's avatar
Pierre Kraemer committed
763
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
764
bool Map2<MAP_IMPL>::isFaceIncidentToBoundary(Face f) const
765
{
Pierre Kraemer's avatar
Pierre Kraemer committed
766
	Dart it = f.dart ;
767
768
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
769
		if (this->template isBoundaryMarked<2>(phi2(it)))
770
771
			return true ;
		it = this->phi1(it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
772
	} while (it != f.dart) ;
773
774
775
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
776
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
777
Dart Map2<MAP_IMPL>::findBoundaryEdgeOfFace(Face f) const
778
{
Pierre Kraemer's avatar
Pierre Kraemer committed
779
	Dart it = f.dart ;
780
781
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
782
		if (this->template isBoundaryMarked<2>(phi2(it)))
783
784
			return phi2(it) ;
		it = this->phi1(it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
785
	} while (it != f.dart) ;
786
787
788
	return NIL ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
789
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
790
bool Map2<MAP_IMPL>::sameOrientedVolume(Vol v1, Vol v2) const
791
{
Pierre Kraemer's avatar
Pierre Kraemer committed
792
	DartMarkerStore<MAP_IMPL> mark(*this);	// Lock a marker
793

Pierre Kraemer's avatar
Pierre Kraemer committed
794
795
	std::list<Dart> visitedFaces;		// Faces that are traversed
	visitedFaces.push_back(v1.dart);	// Start with a face of v1
796
797
798
799
800
	std::list<Dart>::iterator face;

	// For every face added to the list
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
801
802
		// Face has not been visited yet
		if (!this->template isBoundaryMarked<2>(*face) && !mark.isMarked(*face))
803
804
805
806
		{
			Dart it = *face ;
			do
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
807
				if(it == v2.dart)
808
809
810
811
812
813
814
815
816
817
818
819
820
					return true;

				mark.mark(it);						// Mark
				Dart adj = phi2(it);				// Get adjacent face
				if (!this->isBoundaryMarked2(adj) && !mark.isMarked(adj))
					visitedFaces.push_back(adj);	// Add it
				it = this->phi1(it);
			} while(it != *face);
		}
	}
	return false;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
821
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
822
inline bool Map2<MAP_IMPL>::sameVolume(Vol v1, Vol v2) const
823
{
Pierre Kraemer's avatar
Pierre Kraemer committed
824
	return sameOrientedVolume(v1, v2) ;
825
826
}

Pierre Kraemer's avatar
Pierre Kraemer committed
827
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
828
unsigned int Map2<MAP_IMPL>::volumeDegree(Vol v) const
829
830
{
	unsigned int count = 0;
Pierre Kraemer's avatar
Pierre Kraemer committed
831
	DartMarkerStore<MAP_IMPL> mark(*this);		// Lock a marker
832
833
834

	std::vector<Dart> visitedFaces;		// Faces that are traversed
	visitedFaces.reserve(16);
Pierre Kraemer's avatar
Pierre Kraemer committed
835
	visitedFaces.push_back(v.dart);		// Start with a face of v
836
837
838
839
840

	// For every face added to the list
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
	{
		Dart df = visitedFaces[i];
Pierre Kraemer's avatar
Pierre Kraemer committed
841
		if (!this->template isBoundaryMarked<2>(df) && !mark.isMarked(df))		// Face has not been visited yet
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
		{
			++count;
			Dart it = df ;
			do
			{
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
				if ( !this->isBoundaryMarked2(adj) && !mark.isMarked(adj) )
					visitedFaces.push_back(adj);// Add it
				it = this->phi1(it);
			} while(it != df);
		}
	}

	return count;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
859
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
860
int Map2<MAP_IMPL>::checkVolumeDegree(Vol v, unsigned int vd) const
861
862
{
	unsigned int count = 0;
Pierre Kraemer's avatar
Pierre Kraemer committed
863
	DartMarkerStore<MAP_IMPL> mark(*this);		// Lock a marker
864
865
866

	std::vector<Dart> visitedFaces;		// Faces that are traversed
	visitedFaces.reserve(16);
Pierre Kraemer's avatar
Pierre Kraemer committed
867
	visitedFaces.push_back(v.dart);		// Start with a face of v
868
869
870
871
872

	// For every face added to the list
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
	{
		Dart df = visitedFaces[i];
Pierre Kraemer's avatar
Pierre Kraemer committed
873
		if (!this->template isBoundaryMarked<2>(df) && !mark.isMarked(df))		// Face has not been visited yet
874
875
876
877
878
879
880
881
882
883
884
885
		{
			++count;
			Dart it = df ;
			do
			{
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
				if ( !this->isBoundaryMarked2(adj) && !mark.isMarked(adj) )
					visitedFaces.push_back(adj);// Add it
				it = this->phi1(it);
			} while(it != df);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
886
		if (count > vd)
887
888
889
			break;
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
890
	return count - vd;
891
892
}

Pierre Kraemer's avatar
Pierre Kraemer committed
893
894
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::isTriangular() const
895
{
Pierre Kraemer's avatar
Pierre Kraemer committed
896
897
	bool tri = true;
	foreach_cell_until<FACE>(this, [&] (Face f)
898
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
899
900
		if (this->faceDegree(f) != 3)
			tri = false;
901
		return tri;
Pierre Kraemer's avatar
Pierre Kraemer committed
902
903
	});
	return tri;
904
905
}

Pierre Kraemer's avatar
Pierre Kraemer committed
906
907
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::check() const
908
909
{
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
910
	DartMarker<MAP_IMPL> m(*this);
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
	{
		Dart d2 = phi2(d);
		if (phi2(d2) != d)	// phi2 involution ?
		{
			CGoGNout << "Check: phi2 is not an involution" << CGoGNendl;
			return false;
		}
		if(d2 == d)
		{
			CGoGNout << "Check: phi2 fixed point" << CGoGNendl;
			return false;
		}

		Dart d1 = this->phi1(d);
		if (this->phi_1(d1) != d)	// phi1 a une image correcte ?
		{
			CGoGNout << "Check: inconsistent phi_1 link" << CGoGNendl;
			return false;
		}

		if (m.isMarked(d1))	// phi1 a un seul antécédent ?
		{
			CGoGNout << "Check: dart with two phi1 predecessors" << CGoGNendl;
			return false;
		}
		m.mark(d1);

		if (d1 == d)
			CGoGNout << "Check: (warning) face loop (one edge)" << CGoGNendl;
		if (this->phi1(d1) == d)
			CGoGNout << "Check: (warning) face with only two edges" << CGoGNendl;
		if (phi2(d1) == d)
			CGoGNout << "Check: (warning) dangling edge" << CGoGNendl;
	}

	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
	{
		if (!m.isMarked(d))	// phi1 a au moins un antécédent ?
		{
			CGoGNout << "Check: dart with no phi1 predecessor" << CGoGNendl;
			return false;
		}
	}

	CGoGNout << "Check: topology ok" << CGoGNendl;

	return true;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
961
962
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::checkSimpleOrientedPath(std::vector<Dart>& vd)
963
{
Pierre Kraemer's avatar
Pierre Kraemer committed
964
	DartMarkerStore<MAP_IMPL> dm(*this) ;
965
966
967
968
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
		if(dm.isMarked(*it))
			return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
969
		dm.template markOrbit<VERTEX>(*it) ;
970
971
972
973
974
975
976
977
978
979
980
981
982

		std::vector<Dart>::iterator prev ;
		if(it == vd.begin())
			prev = vd.end() - 1 ;
		else
			prev = it - 1 ;

		if(!sameVertex(*it, this->phi1(*prev)))
			return false ;
	}
	return true ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
983
984
985
986
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
987
template <typename MAP_IMPL>
988
inline void Map2<MAP_IMPL>::foreach_dart_of_vertex(Dart d, std::function<void (Dart)> f, unsigned int /*thread*/) const
989
990
991
992
{
	Dart dNext = d;
	do
	{
993
		f(dNext);
994
995
996
997
		dNext = phi2(this->phi_1(dNext));
	} while (dNext != d);
}

Pierre Kraemer's avatar
Pierre Kraemer committed
998
template <typename MAP_IMPL>
999
inline void Map2<MAP_IMPL>::foreach_dart_of_edge(Dart d, std::function<void (Dart)> f, unsigned int /*thread*/) const
1000
{
1001
1002
	f(d);
	f(phi2(d));
1003
1004
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1005
template <typename MAP_IMPL>
1006
inline void Map2<MAP_IMPL>::foreach_dart_of_face(Dart d, std::function<void (Dart)> f, unsigned int thread) const
Pierre Kraemer's avatar
Pierre Kraemer committed
1007
{
1008
	ParentMap::foreach_dart_of_cc(d, f, thread);
Pierre Kraemer's avatar
Pierre Kraemer committed
1009
1010
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1011
template <typename MAP_IMPL>
1012
inline void Map2<MAP_IMPL>::foreach_dart_of_volume(Dart d, std::function<void (Dart)> f, unsigned int thread) const
Pierre Kraemer's avatar
Pierre Kraemer committed
1013
{
1014
	foreach_dart_of_cc(d, f, thread);
Pierre Kraemer's avatar
Pierre Kraemer committed
1015
}
1016

Pierre Kraemer's avatar
Pierre Kraemer committed
1017
template <typename MAP_IMPL>
1018
void Map2<MAP_IMPL>::foreach_dart_of_cc(Dart d, std::function<void (Dart)> f, unsigned int thread) const
1019
{
Pierre Kraemer's avatar
Pierre Kraemer committed
1020
	DartMarkerStore<MAP_IMPL> mark(*this, thread);	// Lock a marker
1021
1022
1023
1024
1025
1026

	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d

	// For every face added to the list
1027
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
1028
1029
1030
1031
	{
		if (!mark.isMarked(visitedFaces[i]))	// Face has not been visited yet
		{
			// Apply functor to the darts of the face
1032
			Map2::foreach_dart_of_face(visitedFaces[i], f);
1033

1034
			// mark visited darts (current face)
1035
			// and add non visited adjacent faces to the list of face
1036
1037
			Dart e = visitedFaces[i] ;
			do
1038
			{
1039
1040
1041
1042
1043
1044
				mark.mark(e);				// Mark
				Dart adj = phi2(e);			// Get adjacent face
				if (!mark.isMarked(adj))
					visitedFaces.push_back(adj);	// Add it
				e = this->phi1(e);
			} while(e != visitedFaces[i]);
1045
1046
1047
1048
		}
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1049
template <typename MAP_IMPL>
1050
inline void Map2<MAP_IMPL>::foreach_dart_of_vertex1(Dart d, std::function<void (Dart)> f, unsigned int thread) const
1051
{
1052
	return ParentMap::foreach_dart_of_vertex(d, f, thread);
1053
1054
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1055
template <typename MAP_IMPL>
1056
inline void Map2<MAP_IMPL>::foreach_dart_of_edge1(Dart d, std::function<void (Dart)> f, unsigned int thread) const
Pierre Kraemer's avatar
Pierre Kraemer committed
1057
{
1058
	return ParentMap::foreach_dart_of_edge(d, f, thread);
Pierre Kraemer's avatar
Pierre Kraemer committed
1059
1060
}

1061
1062
1063
1064
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
1065
1066
template <typename MAP_IMPL>
Dart Map2<MAP_IMPL>::newBoundaryCycle(unsigned int nbE)
1067
1068
{
	Dart d = ParentMap::newCycle(nbE);
1069
	this->template boundaryMarkOrbit<2,FACE>(d);
1070
1071
1072
	return d;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1073
1074
template <typename MAP_IMPL>
unsigned int Map2<MAP_IMPL>::closeHole(Dart d, bool forboundary)
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
{
	assert(phi2(d) == d);		// Nothing to close

	Dart first = this->newDart();	// First edge of the face that will fill the hole
	unsigned int countEdges = 1;

	phi2sew(d, first);	// phi2-link the new edge to the hole

	Dart dNext = d;	// Turn around the hole
	Dart dPhi1;		// to complete the face
	do
	{
		do
		{
			dPhi1 = this->phi1(dNext);	// Search and put in dNext
			dNext = phi2(dPhi1);		// the next dart of the hole
		} while (dNext != dPhi1 && dPhi1 != d);

		if (dPhi1 != d)
		{
			Dart next = this->newDart();	// Add a new edge there and link it to the face
			++countEdges;
			this->phi1sew(first, next);	// the edge is linked to the face
			phi2sew(dNext, next);		// the face is linked to the hole
		}
	} while (dPhi1 != d);

	if (forboundary)
1103
		this->template boundaryMarkOrbit<2,FACE>(phi2(d));
1104
1105
1106
1107

	return countEdges ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1108
1109
template <typename MAP_IMPL>
unsigned int Map2<MAP_IMPL>::closeMap(bool forboundary)
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
{
	// Search the map for topological holes (fix points of phi2)
	unsigned int nb = 0 ;
	for (Dart d = this->begin(); d != this->end(); this->next(d))
	{
		if (phi2(d) == d)
		{
			++nb ;
			closeHole(d, forboundary);
		}
	}
	return nb ;
}

/*! @name Compute dual
 * These functions compute the dual mesh
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
1128
1129
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::reverseOrientation()
1130
{
Pierre Kraemer's avatar
Pierre Kraemer committed
1131
	DartAttribute<unsigned int, MAP_IMPL> emb0(this, this->template getEmbeddingAttributeVector<VERTEX>()) ;
1132
1133
	if(emb0.isValid())
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
1134
		DartAttribute<unsigned int, MAP_IMPL> new_emb0 = this->template addAttribute<unsigned int, DART>("new_EMB_0") ;
1135
1136
1137
		for(Dart d = this->begin(); d != this->end(); this->next(d))
			new_emb0[d] = emb0[this->phi1(d)] ;

Pierre Kraemer's avatar
Pierre Kraemer committed
1138
		this->swapAttributes(emb0, new_emb0) ;
1139
1140
1141
		this->removeAttribute(new_emb0) ;
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
1142
1143
1144
1145
	DartAttribute<Dart, MAP_IMPL> n_phi1 = this->getPermutation(0) ;
	DartAttribute<Dart, MAP_IMPL> n_phi_1 = this->getPermutationInv(0) ;

	this->swapAttributes(n_phi1, n_phi_1) ;
1146
1147
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1148
1149
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::computeDual()
1150
{
Pierre Kraemer's avatar
Pierre Kraemer committed
1151
1152
1153
	DartAttribute<Dart, MAP_IMPL> old_phi1 = this->getPermutation(0) ;
	DartAttribute<Dart, MAP_IMPL> old_phi_1 = this->getPermutationInv(0) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
1154
1155
	DartAttribute<Dart, MAP_IMPL> new_phi1 = this->template addAttribute<Dart, DART>("new_phi1") ;
	DartAttribute<Dart, MAP_IMPL> new_phi_1 = this->template addAttribute<Dart, DART>("new_phi_1") ;
1156
1157
1158
1159
1160
1161
1162
1163
1164

	for(Dart d = this->begin(); d != this->end(); this->next(d))
	{
		Dart dd = this->phi1(phi2(d));

		new_phi1[d] = dd ;
		new_phi_1[dd] = d ;
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
1165
1166
	this->swapAttributes(old_phi1, new_phi1) ;
	this->swapAttributes(old_phi_1, new_phi_1) ;
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177

	this->removeAttribute(new_phi1) ;
	this->removeAttribute(new_phi_1) ;

	this->swapEmbeddingContainers(VERTEX, FACE) ;

	reverseOrientation() ;

	// boundary management
	for(Dart d = this->begin(); d != this->end(); this->next(d))
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
1178
		if(this->template isBoundaryMarked<2>(d))
1179
			this->template boundaryMarkOrbit<2,FACE>(deleteVertex(phi2(d)));
1180
1181
1182
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1183
} // namespace CGoGN