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
239
	if(!this->template isBoundaryMarked<2>(d))
		d = phi2(d) ;
	this->template boundaryUnmarkOrbit<FACE,2>(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
246
247
248
249
250
251
252
{
	assert(!isBoundaryEdge(d)) ;
	this->template boundaryMarkOrbit<FACE,2>(d) ;
}

/*! @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
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
{
	Dart e = phi2(d) ;

	assert(!isBoundaryFace(d) && !isBoundaryFace(e)) ;
	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

580
	if (isBoundaryFace(d) || isBoundaryFace(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
656
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::sameOrientedVertex(Dart d, Dart e) const
657
658
659
660
661
662
663
664
665
666
667
{
	Dart it = d;				// Foreach dart dNext in the vertex of d
	do
	{
		if (it == e)			// Test equality with e
			return true;
		it = phi2(this->phi_1(it));
	} while (it != d);
	return false;				// None is equal to e => vertices are distinct
}

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

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

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

	return count - vd;
}

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

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

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

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

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

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

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

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

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
789
790
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::sameOrientedVolume(Dart d, Dart e) const
791
{
Pierre Kraemer's avatar
Pierre Kraemer committed
792
	DartMarkerStore<MAP_IMPL> mark(*this);	// Lock a marker
793
794
795
796
797
798
799
800

	std::list<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.push_back(d);		// Start with the face of d
	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
		if (!this->template isBoundaryMarked<2>(*face) && !mark.isMarked(*face))		// Face has not been visited yet
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
		{
			Dart it = *face ;
			do
			{
				if(it == e)
					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
820
821
template <typename MAP_IMPL>
inline bool Map2<MAP_IMPL>::sameVolume(Dart d, Dart e) const
822
823
824
825
{
	return sameOrientedVolume(d, e) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
826
827
template <typename MAP_IMPL>
unsigned int Map2<MAP_IMPL>::volumeDegree(Dart d) const
828
829
{
	unsigned int count = 0;
Pierre Kraemer's avatar
Pierre Kraemer committed
830
	DartMarkerStore<MAP_IMPL> mark(*this);		// Lock a marker
831
832
833
834
835
836
837
838
839
840

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

	// 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
860
template <typename MAP_IMPL>
int Map2<MAP_IMPL>::checkVolumeDegree(Dart d, unsigned int volDeg) 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
867
868
869
870
871
872

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

	// 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
886
887
888
889
890
891
892
		{
			++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);
		}
		if (count > volDeg)
			break;
	}

	return count - volDeg;
}

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
	TraversorF<Map2<MAP_IMPL> > t(*this) ;
897
898
899
900
901
902
903
904
	for(Dart d = t.begin(); d != t.end(); d = t.next())
	{
		if(faceDegree(d) != 3)
			return false ;
	}
	return true ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
905
906
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::check() const
907
908
{
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
909
	DartMarker<MAP_IMPL> m(*this);
910
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
	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
960
961
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::checkSimpleOrientedPath(std::vector<Dart>& vd)
962
{
Pierre Kraemer's avatar
Pierre Kraemer committed
963
	DartMarkerStore<MAP_IMPL> dm(*this) ;
964
965
966
967
	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
968
		dm.template markOrbit<VERTEX>(*it) ;
969
970
971
972
973
974
975
976
977
978
979
980
981

		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
982
983
984
985
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
986
987
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int /*thread*/) const
988
989
990
991
992
993
994
995
996
997
998
{
	Dart dNext = d;
	do
	{
		if (f(dNext))
			return true;
		dNext = phi2(this->phi_1(dNext));
	} while (dNext != d);
	return false;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
999
1000
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::foreach_dart_of_edge(Dart d, FunctorType& fonct, unsigned int /*thread*/) const
1001
1002
1003
1004
1005
1006
{
	if (fonct(d))
		return true;
	return fonct(phi2(d));
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1007
1008
template <typename MAP_IMPL>
inline bool Map2<MAP_IMPL>::foreach_dart_of_face(Dart d, FunctorType& f, unsigned int thread) const
Pierre Kraemer's avatar
Pierre Kraemer committed
1009
{
1010
	return ParentMap::foreach_dart_of_cc(d, f, thread);
Pierre Kraemer's avatar
Pierre Kraemer committed
1011
1012
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1013
1014
template <typename MAP_IMPL>
inline bool Map2<MAP_IMPL>::foreach_dart_of_volume(Dart d, FunctorType& f, unsigned int thread) const
Pierre Kraemer's avatar
Pierre Kraemer committed
1015
1016
1017
{
	return foreach_dart_of_cc(d, f, thread);
}
1018

Pierre Kraemer's avatar
Pierre Kraemer committed
1019
1020
template <typename MAP_IMPL>
bool Map2<MAP_IMPL>::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread) const
1021
{
Pierre Kraemer's avatar
Pierre Kraemer committed
1022
	DartMarkerStore<MAP_IMPL> mark(*this, thread);	// Lock a marker
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
	bool found = false;				// Last functor return value

	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
	for(unsigned int i = 0; !found && i < visitedFaces.size(); ++i)
	{
		if (!mark.isMarked(visitedFaces[i]))	// Face has not been visited yet
		{
			// Apply functor to the darts of the face
			found = Map2::foreach_dart_of_face(visitedFaces[i], f);

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
				Dart e = visitedFaces[i] ;
				do
				{
					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]);
			}
		}
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1056
1057
template <typename MAP_IMPL>
inline bool Map2<MAP_IMPL>::foreach_dart_of_vertex1(Dart d, FunctorType& f, unsigned int thread) const
1058
{
1059
	return ParentMap::foreach_dart_of_vertex(d,f,thread);
1060
1061
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1062
1063
template <typename MAP_IMPL>
inline bool Map2<MAP_IMPL>::foreach_dart_of_edge1(Dart d, FunctorType& f, unsigned int thread) const
Pierre Kraemer's avatar
Pierre Kraemer committed
1064
{
1065
	return ParentMap::foreach_dart_of_edge(d,f,thread);
Pierre Kraemer's avatar
Pierre Kraemer committed
1066
1067
}

1068
1069
1070
1071
/*! @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
1072
1073
template <typename MAP_IMPL>
Dart Map2<MAP_IMPL>::newBoundaryCycle(unsigned int nbE)
1074
1075
1076
1077
1078
1079
{
	Dart d = ParentMap::newCycle(nbE);
	this->template boundaryMarkOrbit<FACE,2>(d);
	return d;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1080
1081
template <typename MAP_IMPL>
unsigned int Map2<MAP_IMPL>::closeHole(Dart d, bool forboundary)
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
{
	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)
		this->template boundaryMarkOrbit<FACE,2>(phi2(d));

	return countEdges ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1115
1116
template <typename MAP_IMPL>
unsigned int Map2<MAP_IMPL>::closeMap(bool forboundary)
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
{
	// 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
1135
1136
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::reverseOrientation()
1137
{
Pierre Kraemer's avatar
Pierre Kraemer committed
1138
	DartAttribute<unsigned int, MAP_IMPL> emb0(this, this->template getEmbeddingAttributeVector<VERTEX>()) ;
1139
1140
	if(emb0.isValid())
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
1141
		DartAttribute<unsigned int, MAP_IMPL> new_emb0 = this->template addAttribute<unsigned int, DART>("new_EMB_0") ;
1142
1143
1144
		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
1145
		this->swapAttributes(emb0, new_emb0) ;
1146
1147
1148
		this->removeAttribute(new_emb0) ;
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
1149
1150
1151
1152
	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) ;
1153
1154
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1155
1156
template <typename MAP_IMPL>
void Map2<MAP_IMPL>::computeDual()
1157
{
Pierre Kraemer's avatar
Pierre Kraemer committed
1158
1159
1160
	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
1161
1162
	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") ;
1163
1164
1165
1166
1167
1168
1169
1170
1171

	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
1172
1173
	this->swapAttributes(old_phi1, new_phi1) ;
	this->swapAttributes(old_phi_1, new_phi_1) ;
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184

	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
1185
		if(this->template isBoundaryMarked<2>(d))
1186
1187
1188
1189
			this->template boundaryMarkOrbit<FACE,2>(deleteVertex(phi2(d)));
	}
}

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