Création d'un compte pour un collaborateur extérieur au laboratoire depuis l'intranet ICube : https://intranet.icube.unistra.fr/fr/labs/member/profile

gmap2.cpp 20.2 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-2011, 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.u-strasbg.fr/                                         *
Pierre Kraemer's avatar
Pierre Kraemer committed
21
22
23
24
25
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/gmap/gmap2.h"
26
#include "Topology/generic/traversorCell.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
27
28
29
30

namespace CGoGN
{

Pierre Kraemer's avatar
merges    
Pierre Kraemer committed
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
void GMap2::compactTopoRelations(const std::vector<unsigned int>& oldnew)
{
	for (unsigned int i = m_attribs[DART].begin(); i != m_attribs[DART].end(); m_attribs[DART].next(i))
	{
		{
			Dart& d = m_beta0->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
		{
			Dart& d = m_beta1->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
		{
			Dart& d = m_beta2->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
	}
}

56
57
/*! @name Generator and Deletor
 *  To generate or delete faces in a 2-G-map
Pierre Kraemer's avatar
Pierre Kraemer committed
58
59
 *************************************************************************/

60
61
62
63
64
Dart GMap2::newFace(unsigned int nbEdges, bool withBoundary)
{
	Dart d = GMap1::newFace(nbEdges);
	if (withBoundary)
	{
65
		Dart e = GMap1::newBoundaryFace(nbEdges);
66
67
68
69
70
71
72
73
74
75
76
77
78

		Dart it = d;
		do
		{
			beta2sew(it, beta0(e));
			beta2sew(beta0(it), e);
			it = phi1(it);
			e = phi_1(e);
		} while (it != d);
	}
	return d;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
79
80
void GMap2::deleteFace(Dart d)
{
81
82
	assert(!isBoundaryMarked(d)) ;
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
83
84
	do
	{
85
86
87
88
89
90
91
92
93
		if(!isBoundaryEdge(it))
			unsewFaces(it) ;
		it = phi1(it) ;
	} while(it != d) ;
	Dart dd = phi2(d) ;
	GMap1::deleteFace(d) ;
	GMap1::deleteFace(dd) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
94
95
96
97
98
99
100
101
102
void GMap2::deleteCC(Dart d)
{
	DartMarkerStore mark(*this);

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

103
	for(unsigned int i = 0; i < visited.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
104
	{
105
		Dart d0 = beta0(visited[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
106
107
108
109
110
		if(!mark.isMarked(d0))
		{
			visited.push_back(d0) ;
			mark.mark(d0);
		}
111
		Dart d1 = beta1(visited[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
112
113
114
115
116
		if(!mark.isMarked(d1))
		{
			visited.push_back(d1) ;
			mark.mark(d1);
		}
117
		Dart d2 = beta2(visited[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
118
119
120
121
122
123
124
125
126
127
128
		if(!mark.isMarked(d2))
		{
			visited.push_back(d2) ;
			mark.mark(d2);
		}
	}

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

129
130
void GMap2::fillHole(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
131
132
133
134
135
	assert(isBoundaryEdge(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi2(dd) ;
	boundaryUnmarkOrbit(FACE, dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
136
137
138
139
140
141
142
143
}

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

void GMap2::splitVertex(Dart d, Dart e)
{
144
	assert(sameVertex(d, e));
Pierre Kraemer's avatar
Pierre Kraemer committed
145
146
147
148

	if(!sameOrientedVertex(d, e))
		e = beta2(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
149
150
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
151
152
153
	beta2unsew(d) ;
	beta2unsew(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
154
155
	GMap1::cutEdge(dd);			// Cut the edge of dd (make a new edge)
	GMap1::cutEdge(ee);			// Cut the edge of ee (make a new edge)
Pierre Kraemer's avatar
Pierre Kraemer committed
156

157
158
	beta2sew(phi1(dd), beta0(phi1(ee)));	// Sew the two faces along the new edge
	beta2sew(phi1(ee), beta0(phi1(dd)));
Pierre Kraemer's avatar
Pierre Kraemer committed
159
160
	beta2sew(d, beta0(dd)) ;
	beta2sew(e, beta0(ee)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
161
162
}

163
Dart GMap2::deleteVertex(Dart d)
164
165
{
	if(isBoundaryVertex(d))
166
		return NIL ;
167

168
	Dart res = NIL ;
169
170
171
	Dart vit = d ;
	do
	{
172
173
174
175
176
177
178
179
180
181
182
183
		if(res == NIL && phi1(phi1(d)) != d)
			res = phi1(d) ;

		Dart d0 = beta0(vit) ;
		Dart d02 = beta2(d0) ;
		Dart d01 = beta1(d0) ;
		Dart d021 = beta1(d02) ;
		beta1unsew(d0) ;
		beta1unsew(d02) ;
		beta1sew(d0, d02) ;
		beta1sew(d01, d021) ;

184
185
		vit = alpha1(vit) ;
	} while(vit != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
186
	GMap1::deleteFace(d) ;
187
	return res ;
188
189
}

190
Dart GMap2::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
191
{
192
	Dart e = phi2(d) ;
193
194
	Dart nd = GMap1::cutEdge(d) ;
	Dart ne = GMap1::cutEdge(e) ;
195

196
197
	beta2sew(nd, beta1(ne)) ;
	beta2sew(ne, beta1(nd)) ;
198
199

	return nd ;
Pierre Kraemer's avatar
Pierre Kraemer committed
200
201
}

202
bool GMap2::uncutEdge(Dart d)
203
{
204
	if(vertexDegree(phi1(d)) == 2)
205
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
206
207
		GMap1::uncutEdge(d) ;
		GMap1::uncutEdge(beta2(d)) ;
208
		return true ;
209
	}
210
	return false ;
211
212
213
}

Dart GMap2::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
214
{
215
	Dart resV = NIL ;
216
217

	Dart e = phi2(d);
218
219
	beta2unsew(d);	// Unlink the opposite edges
	beta2unsew(e);
220

221
222
	Dart f = phi1(e) ;
	Dart h = alpha1(e);
223

224
225
	if (h != e)
		resV = h;
226

227
228
229
230
231
232
233
	if (f != e && delDegenerateFaces)
	{
		GMap1::collapseEdge(e) ;		// Collapse edge e
		collapseDegeneratedFace(f) ;	// and collapse its face if degenerated
	}
	else
		GMap1::collapseEdge(e) ;	// Just collapse edge e
234

235
	f = phi1(d) ;
236
	if(resV == NIL)
237
	{
238
239
240
		h = alpha1(d);
		if (h != d)
			resV = h;
241
242
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
243
244
	if (f != d && delDegenerateFaces)
	{
245
246
		GMap1::collapseEdge(d) ;		// Collapse edge d
		collapseDegeneratedFace(f) ;	// and collapse its face if degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
247
248
	}
	else
249
		GMap1::collapseEdge(d) ;	// Just collapse edge d
250
251

	return resV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
252
253
254
255
}

bool GMap2::flipEdge(Dart d)
{
256
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
257
	{
258
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
259
260
261
262
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
		Dart dNext2 = phi1(dNext);
		Dart eNext2 = phi1(eNext);

		beta1unsew(d) ;
		beta1unsew(eNext) ;
		beta1unsew(e) ;
		beta1unsew(dNext) ;
		beta1unsew(dNext2) ;
		beta1unsew(eNext2) ;

		beta1sew(beta0(e), eNext2) ;
		beta1sew(d, beta0(eNext)) ;
		beta1sew(beta0(d), dNext2) ;
		beta1sew(e, beta0(dNext)) ;
		beta1sew(eNext, beta0(dPrev)) ;
		beta1sew(dNext, beta0(ePrev)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
280
281
282
283
284
285
286
		return true ;
	}
	return false ; // cannot flip a border edge
}

bool GMap2::flipBackEdge(Dart d)
{
287
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
288
	{
289
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
290
291
292
293
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
		Dart dPrev1 = beta1(dPrev) ;
		Dart ePrev1 = beta1(ePrev) ;

		beta1unsew(d) ;
		beta1unsew(eNext) ;
		beta1unsew(e) ;
		beta1unsew(dNext) ;
		beta1unsew(dPrev) ;
		beta1unsew(ePrev) ;

		beta1sew(beta0(e), dPrev) ;
		beta1sew(d, dPrev1) ;
		beta1sew(beta0(d), ePrev) ;
		beta1sew(e, ePrev1) ;
		beta1sew(eNext, beta0(dPrev)) ;
		beta1sew(dNext, beta0(ePrev)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
311
312
313
314
315
		return true ;
	}
	return false ; // cannot flip a border edge
}

316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
//void GMap2::insertEdgeInVertex(Dart d, Dart e)
//{
//	assert(!sameVertex(d,e) && phi2(e)==phi_1(e));
//
//	phi1sew(phi_1(d),phi_1(e));
//}
//
//void GMap2::removeEdgeFromVertex(Dart d)
//{
//	assert(phi2(d)!=d);
//
//	phi1sew(phi_1(d),phi2(d));
//}

void GMap2::sewFaces(Dart d, Dart e, bool withBoundary)
331
{
332
333
334
335
336
337
338
339
	// if sewing with fixed points
	if (!withBoundary)
	{
		assert(beta2(d) == d && beta2(beta0(d)) == beta0(d) && beta2(e) == e && beta2(beta0(e)) == beta0(e)) ;
		beta2sew(d, beta0(e)) ;
		beta2sew(e, beta0(d)) ;
		return ;
	}
340

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

343
344
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
345

346
347
348
349
	beta2unsew(d) ;	// unsew faces from boundary
	beta2unsew(beta0(d)) ;
	beta2unsew(e) ;
	beta2unsew(beta0(e)) ;
350

351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
	if (ee != phi_1(dd))
	{
		Dart eeN = phi1(ee) ;		// remove the boundary edge
		Dart dd1 = beta1(dd) ;
		beta1unsew(eeN) ;
		beta1unsew(dd1) ;
		beta1sew(beta0(ee), dd) ;
		beta1sew(eeN, dd1) ;
	}
	if (dd != phi_1(ee))
	{
		Dart ddN = phi1(dd) ;		// and properly close incident boundaries
		Dart ee1 = beta1(ee) ;
		beta1unsew(ddN) ;
		beta1unsew(ee1) ;
		beta1sew(beta0(dd), ee) ;
		beta1sew(ddN, ee1) ;
	}
	GMap1::deleteFace(dd) ;

	beta2sew(d, beta0(e)) ; // sew the faces
	beta2sew(e, beta0(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
373
374
375
376
}

void GMap2::unsewFaces(Dart d)
{
377
378
379
380
381
382
383
	assert(!isBoundaryEdge(d)) ;

	Dart dd = phi2(d);

	Dart e = newBoundaryFace(2);
	Dart ee = phi1(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
384
385
	Dart f = findBoundaryEdgeOfVertex(d) ;
	if (f != NIL)
386
387
388
389
390
391
392
393
	{
		Dart f1 = beta1(f) ;
		beta1unsew(ee) ;
		beta1unsew(f) ;
		beta1sew(f, beta0(e)) ;
		beta1sew(f1, ee) ;
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
394
395
	f = findBoundaryEdgeOfVertex(dd) ;
	if (f != NIL)
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
	{
		Dart f1 = beta1(f) ;
		beta1unsew(e) ;
		beta1unsew(f) ;
		beta1sew(f, beta0(ee)) ;
		beta1sew(f1, e) ;
	}

	beta2unsew(d) ;
	beta2unsew(beta0(d)) ;
	beta2unsew(dd) ;
	beta2unsew(beta0(dd)) ;

	beta2sew(d, beta0(e)) ;		// sew faces
	beta2sew(e, beta0(d)) ;
	beta2sew(dd, beta0(ee)) ;	// to the boundary
	beta2sew(ee, beta0(dd)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
413
414
415
416
417
418
419
}

bool GMap2::collapseDegeneratedFace(Dart d)
{
	Dart e = phi1(d);				// Check if the face is a loop
	if (phi1(e) == d)				// Yes: it contains one or two edge(s)
	{
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
		Dart d2 = phi2(d) ;			// Check opposite edges
		Dart e2 = phi2(e) ;
		beta2unsew(d) ;
		beta2unsew(beta0(d)) ;
		if(d != e)
		{
			beta2unsew(e) ;
			beta2unsew(beta0(e)) ;
			beta2sew(d2, beta0(e2)) ;
			beta2sew(e2, beta0(d2)) ;
		}
		else
		{
			Dart d21 = beta1(d2) ;
			Dart d2N = phi1(d2) ;
			beta1unsew(d2) ;
			beta1unsew(d2N) ;
			beta1sew(d21, d2N) ;
			beta1sew(d2, beta0(d2)) ;
			GMap1::deleteFace(d2) ;
		}
		GMap1::deleteFace(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
442
443
444
445
446
447
448
		return true ;
	}
	return false ;
}

void GMap2::splitFace(Dart d, Dart e)
{
449
450
451
452
453
	assert(d != e && sameFace(d, e)) ;

	if(!sameOrientedFace(d, e))
		e = beta1(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
454
455
456
457
458
459
	Dart dprev = phi_1(d) ;
	Dart eprev = phi_1(e) ;

	beta2unsew(beta1(d)) ;
	beta2unsew(beta1(e)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
460
461
462
463
464
	Dart dd = GMap1::cutEdge(phi_1(d)) ;
	Dart ee = GMap1::cutEdge(phi_1(e)) ;
	GMap1::splitFace(dd, ee) ;
	beta2sew(dd, beta1(e)) ;
	beta2sew(ee, beta1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
465
466
467

	beta2sew(beta0(dprev), beta0(beta2(dprev))) ;
	beta2sew(beta0(eprev), beta0(beta2(eprev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
468
469
470
471
}

bool GMap2::mergeFaces(Dart d)
{
472
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
473
	{
474
475
476
477
478
479
		Dart e = phi2(d) ;
		beta2unsew(d) ;
		beta2unsew(e) ;
		GMap1::mergeFaces(d, phi1(e)) ;
		GMap1::mergeFaces(e, phi1(d)) ;
		GMap1::deleteFace(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
480
481
482
483
484
485
486
487
		return true ;
	}
	return false ;
}

void GMap2::extractTrianglePair(Dart d)
{
	Dart e = phi2(d) ;
488
489
490
491

	assert(!isBoundaryFace(d) && !isBoundaryFace(e)) ;
	assert(faceDegree(d) == 3 && faceDegree(e) == 3) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
492
493
	Dart d1 = phi2(phi1(d)) ;
	Dart d2 = phi2(phi_1(d)) ;
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
	beta2unsew(d1) ;
	beta2unsew(beta0(d1)) ;
	beta2unsew(d2) ;
	beta2unsew(beta0(d2)) ;
	beta2sew(d1, beta0(d2)) ;
	beta2sew(d2, beta0(d1)) ;

	Dart e1 = phi2(phi1(e)) ;
	Dart e2 = phi2(phi_1(e)) ;
	beta2unsew(e1) ;
	beta2unsew(beta0(e1)) ;
	beta2unsew(e2) ;
	beta2unsew(beta0(e2)) ;
	beta2sew(e1, beta0(e2)) ;
	beta2sew(e2, beta0(e1)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
509
510
511
512
513
}

void GMap2::insertTrianglePair(Dart d, Dart v1, Dart v2)
{
	Dart e = phi2(d) ;
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538

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

	Dart vv1 = phi2(v1) ;
	beta2unsew(v1) ;
	beta2unsew(vv1) ;
	beta2sew(phi_1(d), beta0(v1)) ;
	beta2sew(beta1(d), v1) ;
	beta2sew(phi1(d), beta0(vv1)) ;
	beta2sew(beta0(phi1(d)), vv1) ;

	Dart vv2 = phi2(v2) ;
	beta2unsew(v2) ;
	beta2unsew(vv2) ;
	beta2sew(phi_1(e), beta0(v2)) ;
	beta2sew(beta1(e), v2) ;
	beta2sew(phi1(e), beta0(vv2)) ;
	beta2sew(beta0(phi1(e)), vv2) ;
}

void GMap2::unsewAroundVertex(Dart d)
{
	Dart it = d ;
	do
Pierre Kraemer's avatar
Pierre Kraemer committed
539
	{
540
541
542
543
544
545
546
547
548
549
		Dart temp = phi1(it) ;
		Dart e_1 = phi_1(it) ;

		do
		{
			unsewFaces(temp) ;
			temp = phi1(temp) ;
		} while(temp != e_1);

		it = alpha1(it);
Pierre Kraemer's avatar
Pierre Kraemer committed
550
	}
551
	while(it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
552
553
554
555
}

bool GMap2::mergeVolumes(Dart d, Dart e)
{
556
557
	assert(!isBoundaryMarked(d) && !isBoundaryMarked(e)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
558
	if (GMap2::isBoundaryFace(d) || GMap2::isBoundaryFace(e))
559
560
		return false;

Pierre Kraemer's avatar
Pierre Kraemer committed
561
	// First traversal of both faces to check the face sizes
562
563
	// and store their edges to efficiently access them further

Pierre Kraemer's avatar
Pierre Kraemer committed
564
565
	std::vector<Dart> dDarts;
	std::vector<Dart> eDarts;
566
	dDarts.reserve(16);		// usual faces have less than 16 edges
Pierre Kraemer's avatar
Pierre Kraemer committed
567
568
569
	eDarts.reserve(16);

	Dart dFit = d ;
570
	Dart eFit = phi1(e) ;	// must take phi1 because of the use
Pierre Kraemer's avatar
Pierre Kraemer committed
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
	do						// of reverse iterator for sewing loop
	{
		dDarts.push_back(dFit) ;
		dFit = phi1(dFit) ;
	} while(dFit != d) ;
	do
	{
		eDarts.push_back(eFit) ;
		eFit = phi1(eFit) ;
	} while(eFit != 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)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
591
		Dart d2 = phi2(*dIt);	// Search the faces adjacent to dNext and eNext
Pierre Kraemer's avatar
Pierre Kraemer committed
592
		Dart e2 = phi2(*eIt);
593
594
595
596
597
598
		beta2unsew(d2);		// Unlink the two adjacent faces from dNext and eNext
		beta2unsew(beta0(d2));
		beta2unsew(e2);
		beta2unsew(beta0(e2));
		beta2sew(d2, beta0(e2));	// Link the two adjacent faces together
		beta2sew(e2, beta0(d2));
Pierre Kraemer's avatar
Pierre Kraemer committed
599
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
600
601
	GMap1::deleteFace(d);		// Delete the two alone faces
	GMap1::deleteFace(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
602
603
604
605
606
607
608
609

	return true ;
}

/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

Thomas's avatar
Thomas committed
610
611
bool GMap2::sameOrientedVertex(Dart d, Dart e)
{
612
	Dart it = d;
Thomas's avatar
Thomas committed
613
614
	do
	{
615
		if (it == e)	// Test equality with e
Thomas's avatar
Thomas committed
616
			return true;
617
618
619
		it = alpha1(it);
	} while (it != d);
	return false;		// None is equal to e => vertices are distinct
Thomas's avatar
Thomas committed
620
621
}

622
623
624
625
626
627
628
629
630
631
632
unsigned int GMap2::vertexDegree(Dart d)
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
	{
		++count ;
		it = alpha1(it) ;
	} while (it != d) ;
	return count ;
}
Thomas's avatar
Thomas committed
633

634
bool GMap2::isBoundaryVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
635
{
636
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
637
638
	do
	{
639
640
641
642
643
		if (isBoundaryMarked(it))
			return true ;
		it = alpha1(it) ;
	} while (it != d) ;
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
644
645
}

646
Dart GMap2::findBoundaryEdgeOfVertex(Dart d)
647
{
648
	Dart it = d ;
649
650
	do
	{
651
652
653
654
655
		if (isBoundaryMarked(it))
			return it ;
		it = alpha1(it) ;
	} while (it != d) ;
	return NIL ;
656
657
}

658
659
660
bool GMap2::isBoundaryFace(Dart d)
{
	Dart it = d ;
661
662
	do
	{
663
		if (isBoundaryMarked(beta2(it)))
664
			return true ;
665
666
		it = phi1(it) ;
	} while (it != d) ;
667
668
669
	return false ;
}

Thomas's avatar
Thomas committed
670
671
672
673
674
675
676
677
678
bool GMap2::sameOrientedVolume(Dart d, Dart e)
{
	DartMarkerStore mark(*this);	// Lock a marker

	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
679
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Thomas's avatar
Thomas committed
680
	{
681
		if (!isBoundaryMarked(*face) && !mark.isMarked(*face))		// Face has not been visited yet
Thomas's avatar
Thomas committed
682
		{
683
			Dart it = *face ;
Thomas's avatar
Thomas committed
684
685
			do
			{
686
				if(it == e)
Thomas's avatar
Thomas committed
687
688
					return true;

689
690
691
				mark.mark(it);						// Mark
				Dart adj = phi2(it);				// Get adjacent face
				if (!isBoundaryMarked(adj) && !mark.isMarked(adj))
Thomas's avatar
Thomas committed
692
					visitedFaces.push_back(adj);	// Add it
693
694
				it = phi1(it);
			} while(it != *face);
Thomas's avatar
Thomas committed
695
696
697
698
699
		}
	}
	return false;
}

700
unsigned int GMap2::volumeDegree(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
701
{
702
703
	unsigned int count = 0;
	DartMarkerStore mark(*this);		// Lock a marker
704

705
706
707
708
	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;
709
710

	// For every face added to the list
711
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
712
	{
713
714
		Dart df = visitedFaces[i];
		if (!isBoundaryMarked(df) && !mark.isMarked(df))		// Face has not been visited yet
715
		{
716
717
			++count;
			Dart it = df ;
718
719
			do
			{
720
721
722
723
724
725
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
				if ( !isBoundaryMarked(adj) && !mark.isMarked(adj) )
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
726
727
		}
	}
728
729
730
731
732
733
734
735
736
737
738
739
740

	return count;
}

bool GMap2::isTriangular()
{
	TraversorF<GMap2> t(*this) ;
	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
741
742
743
744
}

bool GMap2::check()
{
745
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
746
747
748
749
750
	for(Dart d = begin(); d != end(); next(d))
	{
		Dart dd = beta0(d);
		if (beta0(dd) != d)	// beta0 involution ?
		{
751
			CGoGNout << "Check: beta0 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
752
753
754
755
756
757
			return false;
		}

		dd = beta1(d);
		if (beta1(dd) != d)	// beta1 involution ?
		{
758
			CGoGNout << "Check: beta1 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
759
760
761
762
763
764
			return false;
		}

		dd = beta2(d);
		if (beta2(dd) != d)	// beta2 involution ?
		{
765
			CGoGNout << "Check: beta2 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
766
767
			return false;
		}
768
769
		if(dd == d)
			CGoGNout << "Check (warning): beta2 has fix points" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
770
771
	}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
774
775
776
	return true;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
bool GMap2::checkSimpleOrientedPath(std::vector<Dart>& vd)
{
	DartMarkerStore dm(*this) ;
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
		if(dm.isMarked(*it))
			return false ;
		dm.markOrbit(VERTEX, *it) ;

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
798
799
800
801
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
802
bool GMap2::foreach_dart_of_oriented_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
803
{
804
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
805
806
	do
	{
807
		if (f(it))
Pierre Kraemer's avatar
Pierre Kraemer committed
808
			return true;
809
810
		it = alpha1(it);
 	} while (it != d);
811
 	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
812
813
}

Sylvain Thery's avatar
Sylvain Thery committed
814
bool GMap2::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
815
816
817
818
{
	if (f(d))
		return true ;
	Dart e = beta0(d) ;
819
820
821
822
823
824
	if (f(e))
		return true ;
	e = beta2(d) ;
	if (f(e))
		return true ;
	e = beta0(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
825
826
827
828
829
830
	if (f(e))
		return true ;

	return false ;
}

831
832
bool GMap2::foreach_dart_of_oriented_volume(Dart d, FunctorType& f, unsigned int thread)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
833
	DartMarkerStore mark(*this, thread);	// Lock a marker
834
835
	bool found = false;				// Last functor return value

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

	// For every face added to the list
841
	for(unsigned int i = 0; !found && i < visitedFaces.size(); ++i)
842
	{
843
		if (!mark.isMarked(visitedFaces[i]))		// Face has not been visited yet
844
845
		{
			// Apply functor to the darts of the face
846
			found = foreach_dart_of_oriented_face(visitedFaces[i], f);
847
848
849
850
851

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
852
				Dart e = visitedFaces[i] ;
853
854
				do
				{
Pierre Kraemer's avatar
Pierre Kraemer committed
855
856
					mark.mark(e);					// Mark
					Dart adj = phi2(e);				// Get adjacent face
Pierre Kraemer's avatar
Pierre Kraemer committed
857
					if (!mark.isMarked(adj))
858
						visitedFaces.push_back(adj);	// Add it
Pierre Kraemer's avatar
Pierre Kraemer committed
859
					e = phi1(e);
860
				} while(e != visitedFaces[i]);
861
862
863
864
865
866
			}
		}
	}
	return found;
}

867
868
869
870
871
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/

unsigned int GMap2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
872
{
873
	assert(beta2(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
874

875
876
	Dart first = newEdge();		// First edge of the face that will fill the hole
	unsigned int countEdges = 1;
Pierre Kraemer's avatar
Pierre Kraemer committed
877

878
879
	beta2sew(d, beta0(first));	// sew the new edge to the hole
	beta2sew(first, beta0(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
880

881
	Dart prev = first ;
882
883
884
	Dart dNext = d;	// Turn around the hole
	Dart dPhi1;		// to complete the face
	do
Pierre Kraemer's avatar
Pierre Kraemer committed
885
	{
886
887
		dPhi1 = phi1(dNext) ;
		dNext = beta2(dPhi1) ;
888
		while(dNext != dPhi1 && dPhi1 != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
889
		{
890
891
			dPhi1 = beta1(dNext) ;	// Search and put in dNext
			dNext = beta2(dPhi1) ;	// the next dart of the hole
Pierre Kraemer's avatar
Pierre Kraemer committed
892
		}
893
894

		if (dPhi1 != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
895
		{
896
897
			Dart next = newEdge();	// Add a new edge there and link it to the face
			++countEdges;
898
899
			beta1sew(beta0(next), prev);	// the edge is linked to the face
			prev = next ;
900
901
			beta2sew(dNext, beta0(next));	// the face is linked to the hole
			beta2sew(next, beta0(dNext));
Pierre Kraemer's avatar
Pierre Kraemer committed
902
		}
903
904
	} while (dPhi1 != d);

905
906
	beta1sew(prev, beta0(first)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
907
908
	if(forboundary)
		boundaryMarkOrbit(FACE, phi2(d));
909
910
911
912
913
914
915
916
917
918
919

	return countEdges ;
}

void GMap2::closeMap()
{
	// Search the map for topological holes (fix points of phi2)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (beta2(d) == d)
			closeHole(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
920
921
922
923
	}
}

} // namespace CGoGN