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

map2.cpp 18.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/map/map2.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 Map2::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_phi1->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
		{
			Dart& d = m_phi_1->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
		{
			Dart& d = m_phi2->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
	}
}

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

60
Dart Map2::newFace(unsigned int nbEdges, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
61
{
62
	Dart d = Map1::newCycle(nbEdges);
63
	if (withBoundary)
64
	{
65
66
		Dart e = Map1::newBoundaryCycle(nbEdges);

67
		Dart it = d;
68
69
		do
		{
70
71
			phi2sew(it, e);
			it = phi1(it);
72
			e = phi_1(e);
73
		} while (it != d);
74
75
	}
	return d;
76
77
}

78
79
80
81
void Map2::deleteFace(Dart d)
{
	assert(!isBoundaryMarked(d)) ;
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
82
83
	do
	{
84
85
86
87
88
89
90
91
92
		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
93
94
95
96
97
void Map2::deleteCC(Dart d)
{
	DartMarkerStore mark(*this);

	std::vector<Dart> visited;
98
	visited.reserve(1024) ;
untereiner's avatar
untereiner committed
99
	visited.push_back(d);
100
	mark.mark(d) ;
untereiner's avatar
untereiner committed
101

102
	for(unsigned int i = 0; i < visited.size(); ++i)
untereiner's avatar
untereiner committed
103
	{
104
		Dart d1 = phi1(visited[i]) ;
105
		if(!mark.isMarked(d1))
untereiner's avatar
untereiner committed
106
		{
107
108
109
			visited.push_back(d1) ;
			mark.mark(d1);
		}
110
		Dart d2 = phi2(visited[i]) ;
111
112
113
114
		if(!mark.isMarked(d2))
		{
			visited.push_back(d2) ;
			mark.mark(d2);
untereiner's avatar
untereiner committed
115
116
117
		}
	}

118
	for(std::vector<Dart>::iterator it = visited.begin(); it != visited.end(); ++it)
untereiner's avatar
untereiner committed
119
120
121
		deleteDart(*it) ;
}

122
123
void Map2::fillHole(Dart d)
{
124
125
126
127
128
	assert(isBoundaryEdge(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi2(dd) ;
	boundaryUnmarkOrbit(FACE, dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
129
130
131
132
133
134
135
136
}

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

void Map2::splitVertex(Dart d, Dart e)
{
David Cazier's avatar
David Cazier committed
137
138
139
140
141
142
	assert(sameOrientedVertex(d, e)) ;
	Dart d2 = phi2(d) ; assert(d != d2) ;
	Dart e2 = phi2(e) ; assert(e != e2) ;
	Dart nd = Map1::cutEdge(d2) ;	// Cut the edge of dd (make a new half edge)
	Dart ne = Map1::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
143
144
}

145
Dart Map2::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
146
147
{
	if(isBoundaryVertex(d))
148
		return NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
149

150
	Dart res = NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
151
152
153
	Dart vit = d ;
	do
	{
154
155
156
		if(res == NIL && phi1(phi1(d)) != d)
			res = phi1(d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
157
158
		Dart f = phi_1(phi2(vit)) ;
		phi1sew(vit, f) ;
159

Pierre Kraemer's avatar
Pierre Kraemer committed
160
161
		vit = alpha1(vit) ;
	} while(vit != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
162
	Map1::deleteCycle(d) ;
163
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
164
165
}

David Cazier's avatar
David Cazier committed
166
Dart Map2::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
167
168
{
	Dart e = phi2(d);
Sylvain Thery's avatar
Sylvain Thery committed
169
	phi2unsew(d);			// remove old phi2 links
Pierre Kraemer's avatar
Pierre Kraemer committed
170
171
172
173
	Dart nd = Map1::cutEdge(d);		// Cut the 1-edge of d
	Dart ne = Map1::cutEdge(e);		// Cut the 1-edge of phi2(d)
	phi2sew(d, ne);	// Correct the phi2 links
	phi2sew(e, nd);
David Cazier's avatar
David Cazier committed
174
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
175
176
}

Pierre Kraemer's avatar
Pierre Kraemer committed
177
bool Map2::uncutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
178
{
Pierre Kraemer's avatar
Pierre Kraemer committed
179
	if(vertexDegree(phi1(d)) == 2)
Pierre Kraemer's avatar
Pierre Kraemer committed
180
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
181
		Dart e = phi2(phi1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
182
183
		phi2unsew(e) ;
		phi2unsew(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
184
185
		Map1::uncutEdge(d) ;
		Map1::uncutEdge(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
186
		phi2sew(d, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
187
		return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
188
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
189
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
190
191
}

192
Dart Map2::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
193
{
Pierre Kraemer's avatar
Pierre Kraemer committed
194
	Dart resV = NIL ;
195
196

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

199
200
	Dart f = phi1(e) ;
	Dart h = alpha1(e);
201

202
	if (h != e)
203
		resV = h;
204

205
	if (f != e && delDegenerateFaces)
Sylvain Thery's avatar
Sylvain Thery committed
206
207
	{
		Map1::collapseEdge(e) ;		// Collapse edge e
208
		collapseDegeneratedFace(f) ;// and collapse its face if degenerated
Sylvain Thery's avatar
Sylvain Thery committed
209
210
	}
	else
211
		Map1::collapseEdge(e) ;	// Just collapse edge e
212

213
214
	f = phi1(d) ;
	if(resV == NIL)
215
	{
216
217
		h = alpha1(d);
		if (h != d)
218
			resV = h;
219
220
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
221
222
	if (f != d && delDegenerateFaces)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
223
224
		Map1::collapseEdge(d) ;		// Collapse edge d
		collapseDegeneratedFace(f) ;// and collapse its face if degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
225
226
	}
	else
Pierre Kraemer's avatar
Pierre Kraemer committed
227
		Map1::collapseEdge(d) ;	// Just collapse edge d
228
229

	return resV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
230
231
232
233
}

bool Map2::flipEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
234
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
235
	{
Sylvain Thery's avatar
Sylvain Thery committed
236
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
		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
252
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
253
	{
Sylvain Thery's avatar
Sylvain Thery committed
254
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
255
256
257
258
259
260
261
262
263
264
265
		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
}

266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
//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 ;
//}
281

282
void Map2::sewFaces(Dart d, Dart e, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
283
{
284
285
286
	// if sewing with fixed points
	if (!withBoundary)
	{
287
288
289
		assert(phi2(d) == d && phi2(e) == e) ;
		phi2sew(d, e) ;
		return ;
290
	}
291

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

294
295
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
296

297
298
	phi2unsew(d) ;	// unsew faces from boundary
	phi2unsew(e) ;
299

300
301
302
303
304
	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
305

306
	phi2sew(d, e) ; // sew the faces
Pierre Kraemer's avatar
Pierre Kraemer committed
307
308
309
310
}

void Map2::unsewFaces(Dart d)
{
311
312
	assert(!isBoundaryEdge(d)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
313
	Dart dd = phi2(d) ;
Sylvain Thery's avatar
Sylvain Thery committed
314

Pierre Kraemer's avatar
Pierre Kraemer committed
315
	Dart e = newBoundaryCycle(2) ;
316
	Dart ee = phi1(e) ;
Sylvain Thery's avatar
Sylvain Thery committed
317

Pierre Kraemer's avatar
Pierre Kraemer committed
318
	Dart f = findBoundaryEdgeOfVertex(d) ;
untereiner's avatar
untereiner committed
319
	if(f != NIL)
Pierre Kraemer's avatar
Pierre Kraemer committed
320
		phi1sew(e, phi_1(f)) ;
Sylvain Thery's avatar
Sylvain Thery committed
321

Pierre Kraemer's avatar
Pierre Kraemer committed
322
	f = findBoundaryEdgeOfVertex(dd) ;
untereiner's avatar
untereiner committed
323
	if(f != NIL)
Pierre Kraemer's avatar
Pierre Kraemer committed
324
		phi1sew(ee, phi_1(f)) ;
Sylvain Thery's avatar
Sylvain Thery committed
325

Pierre Kraemer's avatar
Pierre Kraemer committed
326
	phi2unsew(d) ;
327

Pierre Kraemer's avatar
Pierre Kraemer committed
328
329
	phi2sew(d, e) ;		// sew faces
	phi2sew(dd, ee) ;	// to the boundary
Pierre Kraemer's avatar
Pierre Kraemer committed
330
331
332
333
}

bool Map2::collapseDegeneratedFace(Dart d)
{
334
	Dart e = phi1(d) ;				// Check if the face is degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
335
336
	if (phi1(e) == d)				// Yes: it contains one or two edge(s)
	{
337
338
339
340
341
342
343
344
345
346
347
348
349
350
		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
351
352
353
354
355
356
357
		return true ;
	}
	return false ;
}

void Map2::splitFace(Dart d, Dart e)
{
358
	assert(d != e && sameFace(d, e)) ;
359
360
361
362
	Dart dd = Map1::cutEdge(phi_1(d)) ;
	Dart ee = Map1::cutEdge(phi_1(e)) ;
	Map1::splitCycle(dd, ee) ;
	phi2sew(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
363
364
365
366
}

bool Map2::mergeFaces(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
367
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
368
	{
Sylvain Thery's avatar
Sylvain Thery committed
369
		Dart e = phi2(d) ;
370
		phi2unsew(d) ;
371
		Map1::mergeCycles(d, phi1(e)) ;
372
		Map1::splitCycle(e, phi1(d)) ;
373
		Map1::deleteCycle(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
374
375
376
377
378
379
380
381
		return true ;
	}
	return false ;
}

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
386
387
388
389
390
	Dart d1 = phi2(phi1(d)) ;
	Dart d2 = phi2(phi_1(d)) ;
	phi2unsew(d1) ;
	phi2unsew(d2) ;
	phi2sew(d1, d2) ;
391
392
393
394
395
396

	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
397
398
399
400
401
}

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

403
404
	assert(v1 != v2 && sameOrientedVertex(v1, v2)) ;
	assert(faceDegree(d) == 3 && faceDegree(phi2(d)) == 3) ;
Sylvain Thery's avatar
Sylvain Thery committed
405

Pierre Kraemer's avatar
Pierre Kraemer committed
406
407
408
409
	Dart vv1 = phi2(v1) ;
	phi2unsew(v1) ;
	phi2sew(phi_1(d), v1) ;
	phi2sew(phi1(d), vv1) ;
410
411
412
413
414

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

417
418
void Map2::unsewAroundVertex(Dart d)
{
419
	Dart it = d ;
420
421
	do
	{
422
423
		Dart temp = phi1(it) ;
		Dart e_1 = phi_1(it) ;
424
425
426

		do
		{
427
428
429
			unsewFaces(temp) ;
			temp = phi1(temp) ;
		} while(temp != e_1);
430

431
		it = alpha1(it);
432
	}
433
	while(it != d);
434
435
}

Pierre Kraemer's avatar
Pierre Kraemer committed
436
437
bool Map2::mergeVolumes(Dart d, Dart e)
{
438
	assert(!isBoundaryMarked(d) && !isBoundaryMarked(e)) ;
Sylvain Thery's avatar
Sylvain Thery committed
439

untereiner's avatar
untereiner committed
440
	if (Map2::isBoundaryFace(d) || Map2::isBoundaryFace(e))
Sylvain Thery's avatar
Sylvain Thery committed
441
442
		return false;

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

Pierre Kraemer's avatar
Pierre Kraemer committed
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
	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)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
473
		Dart d2 = phi2(*dIt);	// Search the faces adjacent to dNext and eNext
Pierre Kraemer's avatar
Pierre Kraemer committed
474
		Dart e2 = phi2(*eIt);
475
		phi2unsew(d2);		// Unlink the two adjacent faces from dNext and eNext
Sylvain Thery's avatar
Sylvain Thery committed
476
		phi2unsew(e2);
477
		phi2sew(d2, e2);	// Link the two adjacent faces together
Pierre Kraemer's avatar
Pierre Kraemer committed
478
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
479
480
	Map1::deleteCycle(d);		// Delete the two alone faces
	Map1::deleteCycle(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
481
482
483
484
485
486
487
488
489
490

	return true ;
}

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

bool Map2::sameOrientedVertex(Dart d, Dart e)
{
491
	Dart it = d;				// Foreach dart dNext in the vertex of d
Pierre Kraemer's avatar
Pierre Kraemer committed
492
493
	do
	{
494
		if (it == e)			// Test equality with e
Pierre Kraemer's avatar
Pierre Kraemer committed
495
			return true;
496
497
		it = alpha1(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
498
499
500
	return false;				// None is equal to e => vertices are distinct
}

501
502
503
unsigned int Map2::vertexDegree(Dart d)
{
	unsigned int count = 0 ;
504
	Dart it = d ;
505
506
507
	do
	{
		++count ;
508
509
		it = alpha1(it) ;
	} while (it != d) ;
510
511
512
	return count ;
}

513
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
539
540
541
542
543
544
545
546
547
548
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 ;
}

549
bool Map2::sameOrientedVolume(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
550
{
551
552
553
554
555
556
557
	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
558
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Pierre Kraemer's avatar
Pierre Kraemer committed
559
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
560
		if (!isBoundaryMarked(*face) && !mark.isMarked(*face))		// Face has not been visited yet
561
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
562
			Dart it = *face ;
563
564
			do
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
565
				if(it == e)
566
567
					return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
568
569
570
				mark.mark(it);						// Mark
				Dart adj = phi2(it);				// Get adjacent face
				if (!isBoundaryMarked(adj) && !mark.isMarked(adj))
571
					visitedFaces.push_back(adj);	// Add it
Pierre Kraemer's avatar
Pierre Kraemer committed
572
573
				it = phi1(it);
			} while(it != *face);
574
575
576
		}
	}
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
577
578
579
580
581
582
583
584
585
586
587
588
589
}

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
590
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
591
	{
Sylvain Thery's avatar
Sylvain Thery committed
592
593
		Dart df = visitedFaces[i];
		if (!isBoundaryMarked(df) && !mark.isMarked(df))		// Face has not been visited yet
Pierre Kraemer's avatar
Pierre Kraemer committed
594
595
		{
			++count;
596
			Dart it = df ;
Pierre Kraemer's avatar
Pierre Kraemer committed
597
598
			do
			{
599
600
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
Sylvain Thery's avatar
Sylvain Thery committed
601
				if ( !isBoundaryMarked(adj) && !mark.isMarked(adj) )
602
603
604
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
Pierre Kraemer's avatar
Pierre Kraemer committed
605
606
607
608
609
610
611
612
		}
	}

	return count;
}

bool Map2::isTriangular()
{
613
614
	TraversorF<Map2> t(*this) ;
	for(Dart d = t.begin(); d != t.end(); d = t.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
615
	{
616
617
		if(faceDegree(d) != 3)
			return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
618
619
620
621
622
623
	}
	return true ;
}

bool Map2::check()
{
624
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
625
	DartMarker m(*this);
Pierre Kraemer's avatar
Pierre Kraemer committed
626
	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
627
628
629
630
	{
		Dart d2 = phi2(d);
		if (phi2(d2) != d)	// phi2 involution ?
		{
631
			CGoGNout << "Check: phi2 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
632
633
			return false;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
634
635
636
637
638
		if(d2 == d)
		{
			CGoGNout << "Check: phi2 fixed point" << CGoGNendl;
			return false;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
639
640
641
642

		Dart d1 = phi1(d);
		if (phi_1(d1) != d)	// phi1 a une image correcte ?
		{
643
			CGoGNout << "Check: inconsistent phi_1 link" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
644
645
646
647
648
			return false;
		}

		if (m.isMarked(d1))	// phi1 a un seul antécédent ?
		{
649
			CGoGNout << "Check: dart with two phi1 predecessors" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
650
651
652
653
654
			return false;
		}
		m.mark(d1);

		if (d1 == d)
655
			CGoGNout << "Check: (warning) face loop (one edge)" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
656
		if (phi1(d1) == d)
657
			CGoGNout << "Check: (warning) face with only two edges" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
658
		if (phi2(d1) == d)
659
			CGoGNout << "Check: (warning) dangling edge" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
660
	}
661

Pierre Kraemer's avatar
Pierre Kraemer committed
662
	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
663
664
665
	{
		if (!m.isMarked(d))	// phi1 a au moins un antécédent ?
		{
666
			CGoGNout << "Check: dart with no phi1 predecessor" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
667
668
669
			return false;
		}
	}
670

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

Pierre Kraemer's avatar
Pierre Kraemer committed
673
674
675
	return true;
}

untereiner's avatar
untereiner committed
676
677
bool Map2::checkSimpleOrientedPath(std::vector<Dart>& vd)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
678
	DartMarkerStore dm(*this) ;
untereiner's avatar
untereiner committed
679
680
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
681
682
683
684
		if(dm.isMarked(*it))
			return false ;
		dm.markOrbit(VERTEX, *it) ;

untereiner's avatar
untereiner committed
685
686
687
688
689
		std::vector<Dart>::iterator prev ;
		if(it == vd.begin())
			prev = vd.end() - 1 ;
		else
			prev = it - 1 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
690

untereiner's avatar
untereiner committed
691
692
693
694
695
696
		if(!sameVertex(*it, phi1(*prev)))
			return false ;
	}
	return true ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
697
698
699
700
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
701
bool Map2::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
702
703
704
705
706
707
708
709
710
711
712
{
	Dart dNext = d;
	do
	{
		if (f(dNext))
			return true;
		dNext = alpha1(dNext);
 	} while (dNext != d);
 	return false;
}

Sylvain Thery's avatar
Sylvain Thery committed
713
bool Map2::foreach_dart_of_edge(Dart d, FunctorType& fonct, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
714
715
716
{
	if (fonct(d))
		return true;
Sylvain Thery's avatar
Sylvain Thery committed
717
	return fonct(phi2(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
718
719
}

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

untereiner's avatar
untereiner committed
725
726
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
727
728
729
	visitedFaces.push_back(d);		// Start with the face of d

	// For every face added to the list
730
	for(unsigned int i = 0; !found && i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
731
	{
732
		if (!mark.isMarked(visitedFaces[i]))	// Face has not been visited yet
Pierre Kraemer's avatar
Pierre Kraemer committed
733
734
		{
			// Apply functor to the darts of the face
735
			found = foreach_dart_of_oriented_face(visitedFaces[i], f);
Pierre Kraemer's avatar
Pierre Kraemer committed
736
737
738
739
740

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
741
				Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
742
743
				do
				{
744
745
746
					mark.mark(e);				// Mark
					Dart adj = phi2(e);			// Get adjacent face
					if (!mark.isMarked(adj))
Pierre Kraemer's avatar
Pierre Kraemer committed
747
						visitedFaces.push_back(adj);	// Add it
untereiner's avatar
untereiner committed
748
					e = phi1(e);
749
				} while(e != visitedFaces[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
750
751
752
753
754
755
			}
		}
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
756
/*! @name Close map after import or creation
757
 *  These functions must be used with care, generally only by import/creation algorithms
Pierre Kraemer's avatar
Pierre Kraemer committed
758
759
 *************************************************************************/

760
unsigned int Map2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
{
	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
788
789
	if(forboundary)
		boundaryMarkOrbit(FACE, phi2(d));
790

Pierre Kraemer's avatar
Pierre Kraemer committed
791
792
793
794
795
796
797
798
799
800
801
802
	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
803
804

} // namespace CGoGN