map2.cpp 18.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-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/map/map2.h"
26
#include "Topology/generic/traversorCell.h"
untereiner's avatar
untereiner committed
27
#include "Topology/generic/traversor2CC.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
28
29
30
31

namespace CGoGN
{

Pierre Kraemer's avatar
Pierre Kraemer committed
32
33
/*! @name Boundary marker management
 *  Function used to merge boundary faces properly
Pierre Kraemer's avatar
Pierre Kraemer committed
34
35
 *************************************************************************/

36
37
38
39
40
41
42
43
//void Map2::mergeBoundaryFaces(Dart dd, Dart ee)
//{
//	if (ee != phi_1(dd))
//		phi1sew(ee, phi_1(dd)) ;
//	if (dd != phi_1(ee))
//		phi1sew(dd, phi_1(ee)) ;
//	deleteCycle(dd);
//}
44

45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//void Map2::mergeFaceWithBoundary(Dart d)
//{
//	std::vector<Dart> storeForLinkVertex;
//	std::vector<Dart> storeForLinkFace;
//
//	Dart it = d ;
//	do	// foreach vertex/edge of face
//	{
//		Dart e = phi2(it) ;
//		if(isBoundaryMarked(e))	// check if connection by edge
//		{
//			storeForLinkFace.push_back(it);
//			storeForLinkFace.push_back(e);
//		}
//		else
//		{
61
//			Dart f = findBoundaryEdgeOfVertex(alpha1(it));	// check if connection by vertex
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//			if (f != it)
//			{
//				storeForLinkVertex.push_back(phi_1(it));
//				storeForLinkVertex.push_back(phi_1(f));
//			}
//		}
//		it = phi1(it) ;
//	} while (it != d) ;
//
//	// merge by vertices
//	while (!storeForLinkVertex.empty())
//	{
//		Dart a = storeForLinkVertex.back() ;
//		storeForLinkVertex.pop_back() ;
//		Dart b = storeForLinkVertex.back() ;
//		storeForLinkVertex.pop_back() ;
//		phi1sew(a, b);
//	}
//	//merge by faces
//	while (!storeForLinkFace.empty())
//	{
//		Dart a = storeForLinkVertex.back() ;
//		storeForLinkVertex.pop_back() ;
//		Dart b = storeForLinkVertex.back() ;
//		storeForLinkVertex.pop_back() ;
//		mergeBoundaryFaces(a, b);
//	}
//}
Sylvain Thery's avatar
Sylvain Thery committed
90

Pierre Kraemer's avatar
Pierre Kraemer committed
91
92
93
94
/*! @name Generator and Deletor
 *  To generate or delete faces in a 2-map
 *************************************************************************/

95
Dart Map2::newFace(unsigned int nbEdges, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
96
{
97
	Dart d = Map1::newCycle(nbEdges);
98
	if (withBoundary)
99
	{
100
101
		Dart e = Map1::newBoundaryCycle(nbEdges);

102
		Dart it = d;
103
104
		do
		{
105
106
			phi2sew(it, e);
			it = phi1(it);
107
			e = phi_1(e);
108
		} while (it != d);
109
110
	}
	return d;
111
112
}

113
114
115
116
void Map2::deleteFace(Dart d)
{
	assert(!isBoundaryMarked(d)) ;
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
117
118
	do
	{
119
120
121
122
123
124
125
126
127
		if(!isBoundaryEdge(it))
			unsewFaces(it) ;
		it = phi1(it) ;
	} while(it != d) ;
	Dart dd = phi2(d) ;
	Map1::deleteCycle(d) ;
	Map1::deleteCycle(dd) ;
}

untereiner's avatar
untereiner committed
128
129
130
131
132
void Map2::deleteCC(Dart d)
{
	DartMarkerStore mark(*this);

	std::vector<Dart> visited;
133
	visited.reserve(1024) ;
untereiner's avatar
untereiner committed
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
	visited.push_back(d);
	std::vector<Dart>::iterator it;

	for (it = visited.begin(); it != visited.end(); ++it)
	{
		if (!mark.isMarked(*it))
		{
			Dart d1 = phi1(*it) ;
			if(!mark.isMarked(d1))
			{
				mark.mark(d1);
				visited.push_back(d1) ;
			}
			Dart d2 = phi2(*it) ;
			if(!mark.isMarked(d2))
			{
				mark.mark(d2);
				visited.push_back(d2) ;
			}
		}
	}

	for(it = visited.begin(); it != visited.end(); ++it)
		deleteDart(*it) ;
}

160
161
162
163
void Map2::fillHole(Dart d)
{
	assert(isBoundaryMarked(d)) ;
	boundaryUnmarkOrbit(FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
}

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

void Map2::splitVertex(Dart d, Dart e)
{
	assert(sameOrientedVertex(d, e));
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
	Map1::cutEdge(dd);			// Cut the edge of dd (make a new half edge)
	Map1::cutEdge(ee);			// Cut the edge of ee (make a new half edge)
	phi2sew(phi1(dd), phi1(ee));// Sew the two faces along the new edge
}

180
Dart Map2::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
181
182
{
	if(isBoundaryVertex(d))
183
		return NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
184

185
	Dart res = NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
186
187
188
	Dart vit = d ;
	do
	{
189
190
191
		if(res == NIL && phi1(phi1(d)) != d)
			res = phi1(d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
192
193
		Dart f = phi_1(phi2(vit)) ;
		phi1sew(vit, f) ;
194

Pierre Kraemer's avatar
Pierre Kraemer committed
195
196
		vit = alpha1(vit) ;
	} while(vit != d) ;
197
	deleteCycle(d) ;
198
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
199
200
}

Pierre Kraemer's avatar
Pierre Kraemer committed
201
202
203
void Map2::cutEdge(Dart d)
{
	Dart e = phi2(d);
Sylvain Thery's avatar
Sylvain Thery committed
204
	phi2unsew(d);			// remove old phi2 links
205
206
	Map1::cutEdge(d);		// Cut the 1-edge of d
	Map1::cutEdge(e);		// Cut the 1-edge of phi2(d)
Sylvain Thery's avatar
Sylvain Thery committed
207

208
209
	phi2sew(d, phi1(e));			// Correct the phi2 links
	phi2sew(e, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
210
211
}

Pierre Kraemer's avatar
Pierre Kraemer committed
212
bool Map2::uncutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
213
{
Pierre Kraemer's avatar
Pierre Kraemer committed
214
	if(vertexDegree(phi1(d)) == 2)
Pierre Kraemer's avatar
Pierre Kraemer committed
215
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
216
		Dart ne = phi2(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
217
218
219
220
221
222
223
		Dart nd = phi1(d) ;
		Dart e = phi_1(ne) ;
		phi2unsew(e) ;
		phi2unsew(d) ;
		Map1::collapseEdge(nd) ;
		Map1::collapseEdge(ne) ;
		phi2sew(d, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
224
		return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
225
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
226
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
227
228
}

229
Dart Map2::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
230
{
Pierre Kraemer's avatar
Pierre Kraemer committed
231
	Dart resV = NIL ;
232
233

	Dart e = phi2(d);
Sylvain Thery's avatar
Sylvain Thery committed
234
	phi2unsew(d);	// Unlink the opposite edges
235

236
237
	Dart f = phi1(e) ;
	Dart h = alpha1(e);
238

239
	if (h != e)
240
		resV = h;
241

242
	if (f != e && delDegenerateFaces)
Sylvain Thery's avatar
Sylvain Thery committed
243
244
	{
		Map1::collapseEdge(e) ;		// Collapse edge e
245
		collapseDegeneratedFace(f) ;// and collapse its face if degenerated
Sylvain Thery's avatar
Sylvain Thery committed
246
247
	}
	else
248
		Map1::collapseEdge(e) ;	// Just collapse edge e
249

250
251
	f = phi1(d) ;
	if(resV == NIL)
252
	{
253
254
		h = alpha1(d);
		if (h != d)
255
			resV = h;
256
257
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
258
259
	if (f != d && delDegenerateFaces)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
260
261
		Map1::collapseEdge(d) ;		// Collapse edge d
		collapseDegeneratedFace(f) ;// and collapse its face if degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
262
263
	}
	else
Pierre Kraemer's avatar
Pierre Kraemer committed
264
		Map1::collapseEdge(d) ;	// Just collapse edge d
265
266

	return resV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
267
268
269
270
}

bool Map2::flipEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
271
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
272
	{
Sylvain Thery's avatar
Sylvain Thery committed
273
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
		phi1sew(d, ePrev);		// Detach the two
		phi1sew(e, dPrev);		// vertices of the edge
		phi1sew(d, dNext);		// Insert the edge in its
		phi1sew(e, eNext);		// new vertices after flip
		return true ;
	}
	return false ; // cannot flip a border edge
}

bool Map2::flipBackEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
289
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
290
	{
Sylvain Thery's avatar
Sylvain Thery committed
291
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
292
293
294
295
296
297
298
299
300
301
302
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
		phi1sew(d, ePrev);			// Detach the two
		phi1sew(e, dPrev);			// vertices of the edge
		phi1sew(e, phi_1(dPrev));	// Insert the edge in its
		phi1sew(d, phi_1(ePrev));	// new vertices after flip
		return true ;
	}
	return false ; // cannot flip a border edge
}

303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
//void Map2::insertEdgeInVertex(Dart d, Dart e)
//{
//	assert(!sameVertex(d,e) && phi2(e) == phi_1(e));
//	phi1sew(phi_1(d), phi_1(e));
//}
//
//bool Map2::removeEdgeFromVertex(Dart d)
//{
//	if (!isBoundaryEdge(d))
//	{
//		phi1sew(phi_1(d), phi2(d)) ;
//		return true ;
//	}
//	return false ;
//}
318

319
void Map2::sewFaces(Dart d, Dart e, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
320
{
321
322
323
	// if sewing with fixed points
	if (!withBoundary)
	{
324
325
326
		assert(phi2(d) == d && phi2(e) == e) ;
		phi2sew(d, e) ;
		return ;
327
	}
328

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

331
332
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
333

334
335
	phi2unsew(d) ;	// unsew faces from boundary
	phi2unsew(e) ;
336

337
338
339
340
341
	if (ee != phi_1(dd))
		phi1sew(ee, phi_1(dd)) ;	// remove the boundary edge
	if (dd != phi_1(ee))
		phi1sew(dd, phi_1(ee)) ;	// and properly close incident boundaries
	Map1::deleteCycle(dd) ;
Sylvain Thery's avatar
Sylvain Thery committed
342

343
	phi2sew(d, e) ; // sew the faces
Pierre Kraemer's avatar
Pierre Kraemer committed
344
345
346
347
}

void Map2::unsewFaces(Dart d)
{
348
349
	assert(!isBoundaryEdge(d)) ;

Sylvain Thery's avatar
Sylvain Thery committed
350
351
	Dart dd = phi2(d);

352
	Dart e = newBoundaryCycle(2);
353
	Dart ee = phi1(e) ;
Sylvain Thery's avatar
Sylvain Thery committed
354

untereiner's avatar
untereiner committed
355
356
	Dart f = findBoundaryEdgeOfVertex(d);
	if(f != NIL)
357
		phi1sew(e, phi_1(f));
Sylvain Thery's avatar
Sylvain Thery committed
358

untereiner's avatar
untereiner committed
359
360
	f = findBoundaryEdgeOfVertex(dd);
	if(f != NIL)
361
		phi1sew(ee, phi_1(f));
Sylvain Thery's avatar
Sylvain Thery committed
362

Pierre Kraemer's avatar
Pierre Kraemer committed
363
	phi2unsew(d);
364
365
366

	phi2sew(d, e);		// sew faces
	phi2sew(dd, ee);	// to the boundary
Pierre Kraemer's avatar
Pierre Kraemer committed
367
368
369
370
}

bool Map2::collapseDegeneratedFace(Dart d)
{
371
	Dart e = phi1(d) ;				// Check if the face is degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
372
373
	if (phi1(e) == d)				// Yes: it contains one or two edge(s)
	{
374
375
376
377
378
379
380
381
382
383
384
385
386
387
		Dart d2 = phi2(d) ;			// Check opposite edges
		Dart e2 = phi2(e) ;
		phi2unsew(d) ;
		if(d != e)
		{
			phi2unsew(e) ;
			phi2sew(d2, e2) ;
		}
		else
		{
			phi1sew(d2, phi_1(d2)) ;
			Map1::deleteCycle(d2) ;
		}
		Map1::deleteCycle(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
388
389
390
391
392
393
394
		return true ;
	}
	return false ;
}

void Map2::splitFace(Dart d, Dart e)
{
395
396
397
398
399
	assert(d != e && sameFace(d, e)) ;
	Map1::cutEdge(phi_1(d)) ;
	Map1::cutEdge(phi_1(e)) ;
	Map1::splitCycle(phi_1(d), phi_1(e)) ;
	phi2sew(phi_1(d), phi_1(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
400
401
402
403
}

bool Map2::mergeFaces(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
404
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
405
	{
Sylvain Thery's avatar
Sylvain Thery committed
406
		Dart e = phi2(d) ;
407
		phi2unsew(d) ;
408
		Map1::mergeCycles(d, phi1(e)) ;
409
		Map1::splitCycle(e, phi1(d)) ;
410
		Map1::deleteCycle(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
411
412
413
414
415
416
417
418
		return true ;
	}
	return false ;
}

void Map2::extractTrianglePair(Dart d)
{
	Dart e = phi2(d) ;
Sylvain Thery's avatar
Sylvain Thery committed
419

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

Pierre Kraemer's avatar
Pierre Kraemer committed
423
424
425
426
427
	Dart d1 = phi2(phi1(d)) ;
	Dart d2 = phi2(phi_1(d)) ;
	phi2unsew(d1) ;
	phi2unsew(d2) ;
	phi2sew(d1, d2) ;
428
429
430
431
432
433

	Dart e1 = phi2(phi1(e)) ;
	Dart e2 = phi2(phi_1(e)) ;
	phi2unsew(e1) ;
	phi2unsew(e2) ;
	phi2sew(e1, e2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
434
435
436
437
438
}

void Map2::insertTrianglePair(Dart d, Dart v1, Dart v2)
{
	Dart e = phi2(d) ;
Sylvain Thery's avatar
Sylvain Thery committed
439

440
441
	assert(v1 != v2 && sameOrientedVertex(v1, v2)) ;
	assert(faceDegree(d) == 3 && faceDegree(phi2(d)) == 3) ;
Sylvain Thery's avatar
Sylvain Thery committed
442

Pierre Kraemer's avatar
Pierre Kraemer committed
443
444
445
446
	Dart vv1 = phi2(v1) ;
	phi2unsew(v1) ;
	phi2sew(phi_1(d), v1) ;
	phi2sew(phi1(d), vv1) ;
447
448
449
450
451

	Dart vv2 = phi2(v2) ;
	phi2unsew(v2) ;
	phi2sew(phi_1(e), v2) ;
	phi2sew(phi1(e), vv2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
452
453
}

454
455
void Map2::unsewAroundVertex(Dart d)
{
456
	Dart it = d ;
457
458
	do
	{
459
460
		Dart temp = phi1(it) ;
		Dart e_1 = phi_1(it) ;
461
462
463

		do
		{
464
465
466
			unsewFaces(temp) ;
			temp = phi1(temp) ;
		} while(temp != e_1);
467

468
		it = alpha1(it);
469
	}
470
	while(it != d);
471
472
}

Pierre Kraemer's avatar
Pierre Kraemer committed
473
474
bool Map2::mergeVolumes(Dart d, Dart e)
{
475
	assert(!isBoundaryMarked(d) && !isBoundaryMarked(e)) ;
Sylvain Thery's avatar
Sylvain Thery committed
476

477
	if (isBoundaryFace(d) || isBoundaryFace(e))
Sylvain Thery's avatar
Sylvain Thery committed
478
479
		return false;

Pierre Kraemer's avatar
Pierre Kraemer committed
480
	// First traversal of both faces to check the face sizes
481
	// and store their edges to efficiently access them further
Sylvain Thery's avatar
Sylvain Thery committed
482

Pierre Kraemer's avatar
Pierre Kraemer committed
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
	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 = phi1(e) ;	// must take phi1 because of the use
	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)
	{
		Dart d2 = phi2(*dIt);			// Search the faces adjacent to dNext and eNext
		Dart e2 = phi2(*eIt);
512
		phi2unsew(d2);		// Unlink the two adjacent faces from dNext and eNext
Sylvain Thery's avatar
Sylvain Thery committed
513
		phi2unsew(e2);
514
		phi2sew(d2, e2);	// Link the two adjacent faces together
Pierre Kraemer's avatar
Pierre Kraemer committed
515
	}
516
	deleteCycle(d);		// Delete the two alone faces
517
	deleteCycle(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
518
519
520
521
522
523
524
525
526
527

	return true ;
}

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

bool Map2::sameOrientedVertex(Dart d, Dart e)
{
528
	Dart it = d;				// Foreach dart dNext in the vertex of d
Pierre Kraemer's avatar
Pierre Kraemer committed
529
530
	do
	{
531
		if (it == e)			// Test equality with e
Pierre Kraemer's avatar
Pierre Kraemer committed
532
			return true;
533
534
		it = alpha1(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
535
536
537
	return false;				// None is equal to e => vertices are distinct
}

538
539
540
unsigned int Map2::vertexDegree(Dart d)
{
	unsigned int count = 0 ;
541
	Dart it = d ;
542
543
544
	do
	{
		++count ;
545
546
		it = alpha1(it) ;
	} while (it != d) ;
547
548
549
	return count ;
}

550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
bool Map2::isBoundaryVertex(Dart d)
{
	Dart it = d ;
	do
	{
		if (isBoundaryMarked(it))
			return true ;
		it = alpha1(it) ;
	} while (it != d) ;
	return false ;
}

Dart Map2::findBoundaryEdgeOfVertex(Dart d)
{
	Dart it = d ;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha1(it) ;
	} while (it != d) ;
	return NIL ;
}

bool Map2::isBoundaryFace(Dart d)
{
	Dart it = d ;
	do
	{
		if (isBoundaryMarked(phi2(it)))
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

586
bool Map2::sameOrientedVolume(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
587
{
588
589
590
591
592
593
594
	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
Pierre Kraemer's avatar
Pierre Kraemer committed
595
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Pierre Kraemer's avatar
Pierre Kraemer committed
596
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
597
		if (!isBoundaryMarked(*face) && !mark.isMarked(*face))		// Face has not been visited yet
598
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
599
			Dart it = *face ;
600
601
			do
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
602
				if(it == e)
603
604
					return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
605
606
607
				mark.mark(it);						// Mark
				Dart adj = phi2(it);				// Get adjacent face
				if (!isBoundaryMarked(adj) && !mark.isMarked(adj))
608
					visitedFaces.push_back(adj);	// Add it
Pierre Kraemer's avatar
Pierre Kraemer committed
609
610
				it = phi1(it);
			} while(it != *face);
611
612
613
		}
	}
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
614
615
616
617
618
619
620
621
622
623
624
625
626
}

unsigned int Map2::volumeDegree(Dart d)
{
	unsigned int count = 0;
	DartMarkerStore mark(*this);		// Lock a marker

	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
627
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
628
	{
Sylvain Thery's avatar
Sylvain Thery committed
629
630
		Dart df = visitedFaces[i];
		if (!isBoundaryMarked(df) && !mark.isMarked(df))		// Face has not been visited yet
Pierre Kraemer's avatar
Pierre Kraemer committed
631
632
		{
			++count;
633
			Dart it = df ;
Pierre Kraemer's avatar
Pierre Kraemer committed
634
635
			do
			{
636
637
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
Sylvain Thery's avatar
Sylvain Thery committed
638
				if ( !isBoundaryMarked(adj) && !mark.isMarked(adj) )
639
640
641
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
Pierre Kraemer's avatar
Pierre Kraemer committed
642
643
644
645
646
647
648
649
		}
	}

	return count;
}

bool Map2::isTriangular()
{
650
651
	TraversorF<Map2> t(*this) ;
	for(Dart d = t.begin(); d != t.end(); d = t.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
652
	{
653
654
		if(faceDegree(d) != 3)
			return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
655
656
657
658
659
660
	}
	return true ;
}

bool Map2::check()
{
661
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
662
	DartMarker m(*this);
Pierre Kraemer's avatar
Pierre Kraemer committed
663
	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
664
665
666
667
	{
		Dart d2 = phi2(d);
		if (phi2(d2) != d)	// phi2 involution ?
		{
668
			CGoGNout << "Check: phi2 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
669
670
			return false;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
671
672
673
674
675
		if(d2 == d)
		{
			CGoGNout << "Check: phi2 fixed point" << CGoGNendl;
			return false;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
676
677
678
679

		Dart d1 = phi1(d);
		if (phi_1(d1) != d)	// phi1 a une image correcte ?
		{
680
			CGoGNout << "Check: inconsistent phi_1 link" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
681
682
683
684
685
			return false;
		}

		if (m.isMarked(d1))	// phi1 a un seul antécédent ?
		{
686
			CGoGNout << "Check: dart with two phi1 predecessors" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
687
688
689
690
691
			return false;
		}
		m.mark(d1);

		if (d1 == d)
692
			CGoGNout << "Check: (warning) face loop (one edge)" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
693
		if (phi1(d1) == d)
694
			CGoGNout << "Check: (warning) face with only two edges" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
695
		if (phi2(d1) == d)
696
			CGoGNout << "Check: (warning) dangling edge" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
697
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
698
	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
699
700
701
	{
		if (!m.isMarked(d))	// phi1 a au moins un antécédent ?
		{
702
			CGoGNout << "Check: dart with no phi1 predecessor" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
703
704
705
			return false;
		}
	}
706
	CGoGNout << "Check: topology ok" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
707
708
709
710
711
712
713
	return true;
}

/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
714
bool Map2::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
715
716
717
718
719
720
721
722
723
724
725
{
	Dart dNext = d;
	do
	{
		if (f(dNext))
			return true;
		dNext = alpha1(dNext);
 	} while (dNext != d);
 	return false;
}

Sylvain Thery's avatar
Sylvain Thery committed
726
bool Map2::foreach_dart_of_edge(Dart d, FunctorType& fonct, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
727
728
729
{
	if (fonct(d))
		return true;
Sylvain Thery's avatar
Sylvain Thery committed
730
	return fonct(phi2(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
731
732
}

Sylvain Thery's avatar
Sylvain Thery committed
733
bool Map2::foreach_dart_of_oriented_volume(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
734
{
untereiner's avatar
untereiner committed
735
	DartMarkerStore mark(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
736
737
	bool found = false;				// Last functor return value

untereiner's avatar
untereiner committed
738
739
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
740
741
742
	visitedFaces.push_back(d);		// Start with the face of d

	// For every face added to the list
untereiner's avatar
untereiner committed
743
	for (std::vector<Dart>::iterator it = visitedFaces.begin(); !found && it != visitedFaces.end(); ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
744
	{
untereiner's avatar
untereiner committed
745
		if (!isBoundaryMarked(*it) && !mark.isMarked(*it))	// Face has not been visited yet
Pierre Kraemer's avatar
Pierre Kraemer committed
746
747
		{
			// Apply functor to the darts of the face
untereiner's avatar
untereiner committed
748
			found = foreach_dart_of_oriented_face(*it, f);
Pierre Kraemer's avatar
Pierre Kraemer committed
749
750
751
752
753

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
untereiner's avatar
untereiner committed
754
				Dart e = *it ;
Pierre Kraemer's avatar
Pierre Kraemer committed
755
756
				do
				{
untereiner's avatar
untereiner committed
757
758
					mark.mark(e);					// Mark
					Dart adj = phi2(e);				// Get adjacent face
Pierre Kraemer's avatar
Pierre Kraemer committed
759
					if (!isBoundaryMarked(adj) && !mark.isMarked(adj))
Pierre Kraemer's avatar
Pierre Kraemer committed
760
						visitedFaces.push_back(adj);	// Add it
untereiner's avatar
untereiner committed
761
762
					e = phi1(e);
				} while(e != *it);
Pierre Kraemer's avatar
Pierre Kraemer committed
763
764
765
766
767
768
			}
		}
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
769
/*! @name Close map after import or creation
770
 *  These functions must be used with care, generally only by import/creation algorithms
Pierre Kraemer's avatar
Pierre Kraemer committed
771
772
 *************************************************************************/

773
unsigned int Map2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
{
	assert(phi2(d) == d);		// Nothing to close

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

untereiner's avatar
untereiner committed
801
802
	if(forboundary)
		boundaryMarkOrbit(FACE, phi2(d));
803

Pierre Kraemer's avatar
Pierre Kraemer committed
804
805
806
807
808
809
810
811
812
813
814
815
	return countEdges ;
}

void Map2::closeMap()
{
	// Search the map for topological holes (fix points of phi2)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (phi2(d) == d)
			closeHole(d);
	}
}
Pierre Kraemer's avatar
Pierre Kraemer committed
816
817

} // namespace CGoGN