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 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-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
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/map/map2.h"
26
#include "Topology/generic/traversorCell.h"
27
#include "Topology/generic/dartmarker.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
28
29
30
31

namespace CGoGN
{

32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
void Map2::rdfi(Dart t, DartMarker& m1, DartMarker& m2)
{
	Dart p = NIL;
	while (!(p == NIL && (t == NIL || (m1.isMarked(t) || m2.isMarked(t)) ) ) )
	{
		if (t == NIL || (m1.isMarked(t) || m2.isMarked(t)))
		{
			if (m2.isMarked(p))			// pop
			{
				Dart q = phi2(p);		//	q = p->s1;
				unsigned int pi=dartIndex(p);
				(*m_phi2)[pi]=t;		//	p->s1 = t;
				t = p;
				p = q;
	     	}
			else						// swing
	     	{
				m2.mark(p);				//	p->val = 2;
				Dart q = phi1(p);		//	q = p->s0;
				unsigned int pi=dartIndex(p);
				(*m_phi1)[pi]=t;		//	p->s0 = t;
				t = phi2(p);			//	t = p->s1;
				(*m_phi2)[pi]=q;		//	p->s1 = q;
			}
		}
		else							 // push
		{
			m1.mark(t);					//	t->val = 1;
			Dart q = phi1(t);			//	q = t->s0;
			unsigned int ti=dartIndex(t);
			(*m_phi1)[ti]=p;			//	t->s0 = p;
			p = t;
			t = q;
		}
	}
}

Pierre Kraemer's avatar
merges    
Pierre Kraemer committed
69
70
71
72
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))
	{
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
		unsigned int d_index = dartIndex(m_phi1->operator[](i));
		if (d_index != oldnew[d_index])
			m_phi1->operator[](i) = Dart(oldnew[d_index]);

		d_index = dartIndex(m_phi_1->operator[](i));
		if (d_index != oldnew[d_index])
			m_phi_1->operator[](i) = Dart(oldnew[d_index]);

		d_index = dartIndex(m_phi2->operator[](i));
		if (d_index != oldnew[d_index])
			m_phi2->operator[](i) = Dart(oldnew[d_index]);

//		{
//			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
merges    
Pierre Kraemer committed
103
104
105
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
106
107
108
109
/*! @name Generator and Deletor
 *  To generate or delete faces in a 2-map
 *************************************************************************/

110
Dart Map2::newFace(unsigned int nbEdges, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
111
{
112
	Dart d = Map1::newCycle(nbEdges);
113
	if (withBoundary)
114
	{
115
116
		Dart e = Map1::newBoundaryCycle(nbEdges);

117
		Dart it = d;
118
119
		do
		{
120
121
			phi2sew(it, e);
			it = phi1(it);
122
			e = phi_1(e);
123
		} while (it != d);
124
125
	}
	return d;
126
127
}

128
void Map2::deleteFace(Dart d, bool withBoundary)
129
130
{
	assert(!isBoundaryMarked(d)) ;
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
	if (withBoundary)
	{
		Dart it = d ;
		do
		{
			if(!isBoundaryEdge(it))
				unsewFaces(it) ;
			it = phi1(it) ;
		} while(it != d) ;
		Dart dd = phi2(d) ;
		Map1::deleteCycle(d) ;
		Map1::deleteCycle(dd) ;
		return;
	}
	//else with remove the face and create fixed points
146
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
147
148
	do
	{
149
		phi2unsew(it);
150
151
		it = phi1(it) ;
	} while(it != d) ;
152
	Map1::deleteCycle(d);
153
154
}

untereiner's avatar
untereiner committed
155
156
157
158
159
void Map2::deleteCC(Dart d)
{
	DartMarkerStore mark(*this);

	std::vector<Dart> visited;
160
	visited.reserve(1024) ;
untereiner's avatar
untereiner committed
161
	visited.push_back(d);
162
	mark.mark(d) ;
untereiner's avatar
untereiner committed
163

164
	for(unsigned int i = 0; i < visited.size(); ++i)
untereiner's avatar
untereiner committed
165
	{
166
		Dart d1 = phi1(visited[i]) ;
167
		if(!mark.isMarked(d1))
untereiner's avatar
untereiner committed
168
		{
169
170
171
			visited.push_back(d1) ;
			mark.mark(d1);
		}
172
		Dart d2 = phi2(visited[i]) ;
173
174
175
176
		if(!mark.isMarked(d2))
		{
			visited.push_back(d2) ;
			mark.mark(d2);
untereiner's avatar
untereiner committed
177
178
179
		}
	}

180
	for(std::vector<Dart>::iterator it = visited.begin(); it != visited.end(); ++it)
untereiner's avatar
untereiner committed
181
182
183
		deleteDart(*it) ;
}

184
185
void Map2::fillHole(Dart d)
{
186
187
188
189
190
	assert(isBoundaryEdge(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi2(dd) ;
	boundaryUnmarkOrbit(FACE, dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
191
192
193
194
195
196
197
198
}

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

void Map2::splitVertex(Dart d, Dart e)
{
David Cazier's avatar
David Cazier committed
199
200
201
202
203
204
	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
205
206
}

207
Dart Map2::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
208
209
{
	if(isBoundaryVertex(d))
210
		return NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
211

212
	Dart res = NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
213
214
215
	Dart vit = d ;
	do
	{
216
217
218
		if(res == NIL && phi1(phi1(d)) != d)
			res = phi1(d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
219
220
		Dart f = phi_1(phi2(vit)) ;
		phi1sew(vit, f) ;
221

Pierre Kraemer's avatar
Pierre Kraemer committed
222
223
		vit = alpha1(vit) ;
	} while(vit != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
224
	Map1::deleteCycle(d) ;
225
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
226
227
}

David Cazier's avatar
David Cazier committed
228
Dart Map2::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
229
230
{
	Dart e = phi2(d);
231
	phi2unsew(d);					// remove old phi2 links
Pierre Kraemer's avatar
Pierre Kraemer committed
232
233
	Dart nd = Map1::cutEdge(d);		// Cut the 1-edge of d
	Dart ne = Map1::cutEdge(e);		// Cut the 1-edge of phi2(d)
234
	phi2sew(d, ne);					// Correct the phi2 links
Pierre Kraemer's avatar
Pierre Kraemer committed
235
	phi2sew(e, nd);
David Cazier's avatar
David Cazier committed
236
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
237
238
}

Pierre Kraemer's avatar
Pierre Kraemer committed
239
bool Map2::uncutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
240
{
Pierre Kraemer's avatar
Pierre Kraemer committed
241
	if(vertexDegree(phi1(d)) == 2)
Pierre Kraemer's avatar
Pierre Kraemer committed
242
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
243
		Dart e = phi2(phi1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
244
245
		phi2unsew(e) ;
		phi2unsew(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
246
247
		Map1::uncutEdge(d) ;
		Map1::uncutEdge(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
248
		phi2sew(d, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
249
		return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
250
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
251
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
252
253
}

254
Dart Map2::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
255
{
Pierre Kraemer's avatar
Pierre Kraemer committed
256
	Dart resV = NIL ;
257
258

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

261
262
	Dart f = phi1(e) ;
	Dart h = alpha1(e);
263

264
	if (h != e)
265
		resV = h;
266

267
	if (f != e && delDegenerateFaces)
Sylvain Thery's avatar
Sylvain Thery committed
268
269
	{
		Map1::collapseEdge(e) ;		// Collapse edge e
270
		collapseDegeneratedFace(f) ;// and collapse its face if degenerated
Sylvain Thery's avatar
Sylvain Thery committed
271
272
	}
	else
273
		Map1::collapseEdge(e) ;	// Just collapse edge e
274

275
276
	f = phi1(d) ;
	if(resV == NIL)
277
	{
278
279
		h = alpha1(d);
		if (h != d)
280
			resV = h;
281
282
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
283
284
	if (f != d && delDegenerateFaces)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
285
286
		Map1::collapseEdge(d) ;		// Collapse edge d
		collapseDegeneratedFace(f) ;// and collapse its face if degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
287
288
	}
	else
Pierre Kraemer's avatar
Pierre Kraemer committed
289
		Map1::collapseEdge(d) ;	// Just collapse edge d
290
291

	return resV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
292
293
294
295
}

bool Map2::flipEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
296
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
297
	{
Sylvain Thery's avatar
Sylvain Thery committed
298
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
		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
314
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
315
	{
Sylvain Thery's avatar
Sylvain Thery committed
316
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
317
318
319
320
321
322
323
324
325
326
327
		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
}

untereiner's avatar
untereiner committed
328
329
330
331
void Map2::swapEdges(Dart d, Dart e)
{
	assert(!Map2::isBoundaryEdge(d) && !Map2::isBoundaryEdge(e));

332
333
	//Dart d2 = phi2(d);
	//Dart e2 = phi2(e);
untereiner's avatar
untereiner committed
334
335
336
337
338
339
340
341

	phi2unsew(d);
	phi2unsew(e) ;

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

342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
//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 ;
//}
357

358
void Map2::sewFaces(Dart d, Dart e, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
359
{
360
361
362
	// if sewing with fixed points
	if (!withBoundary)
	{
363
364
365
		assert(phi2(d) == d && phi2(e) == e) ;
		phi2sew(d, e) ;
		return ;
366
	}
367

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

370
371
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
372

373
374
	phi2unsew(d) ;	// unsew faces from boundary
	phi2unsew(e) ;
375

376
377
378
379
380
	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
381

382
	phi2sew(d, e) ; // sew the faces
Pierre Kraemer's avatar
Pierre Kraemer committed
383
384
385
386
}

void Map2::unsewFaces(Dart d)
{
untereiner's avatar
untereiner committed
387
	assert(!Map2::isBoundaryEdge(d)) ;
388

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

Pierre Kraemer's avatar
Pierre Kraemer committed
391
	Dart e = newBoundaryCycle(2) ;
392
	Dart ee = phi1(e) ;
Sylvain Thery's avatar
Sylvain Thery committed
393

Pierre Kraemer's avatar
Pierre Kraemer committed
394
	Dart f = findBoundaryEdgeOfVertex(d) ;
395
396
	Dart ff = findBoundaryEdgeOfVertex(dd) ;

untereiner's avatar
untereiner committed
397
	if(f != NIL)
Pierre Kraemer's avatar
Pierre Kraemer committed
398
		phi1sew(e, phi_1(f)) ;
Sylvain Thery's avatar
Sylvain Thery committed
399

400
401
	if(ff != NIL)
		phi1sew(ee, phi_1(ff)) ;
Sylvain Thery's avatar
Sylvain Thery committed
402

Pierre Kraemer's avatar
Pierre Kraemer committed
403
	phi2unsew(d) ;
404

Pierre Kraemer's avatar
Pierre Kraemer committed
405
406
	phi2sew(d, e) ;		// sew faces
	phi2sew(dd, ee) ;	// to the boundary
Pierre Kraemer's avatar
Pierre Kraemer committed
407
408
409
410
}

bool Map2::collapseDegeneratedFace(Dart d)
{
411
	Dart e = phi1(d) ;				// Check if the face is degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
412
413
	if (phi1(e) == d)				// Yes: it contains one or two edge(s)
	{
414
415
416
417
418
419
420
421
422
423
424
425
426
427
		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
428
429
430
431
432
433
434
		return true ;
	}
	return false ;
}

void Map2::splitFace(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
435
	assert(d != e && Map2::sameFace(d, e)) ;
436
437
438
439
	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
440
441
442
443
}

bool Map2::mergeFaces(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
444
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
445
	{
Sylvain Thery's avatar
Sylvain Thery committed
446
		Dart e = phi2(d) ;
447
		phi2unsew(d) ;
448
		Map1::mergeCycles(d, phi1(e)) ;
449
		Map1::splitCycle(e, phi1(d)) ;
450
		Map1::deleteCycle(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
451
452
453
454
455
456
457
458
		return true ;
	}
	return false ;
}

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
463
464
465
466
467
	Dart d1 = phi2(phi1(d)) ;
	Dart d2 = phi2(phi_1(d)) ;
	phi2unsew(d1) ;
	phi2unsew(d2) ;
	phi2sew(d1, d2) ;
468
469
470
471
472
473

	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
474
475
476
477
478
}

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

480
481
	assert(v1 != v2 && sameOrientedVertex(v1, v2)) ;
	assert(faceDegree(d) == 3 && faceDegree(phi2(d)) == 3) ;
Sylvain Thery's avatar
Sylvain Thery committed
482

Pierre Kraemer's avatar
Pierre Kraemer committed
483
484
485
486
	Dart vv1 = phi2(v1) ;
	phi2unsew(v1) ;
	phi2sew(phi_1(d), v1) ;
	phi2sew(phi1(d), vv1) ;
487
488
489
490
491

	Dart vv2 = phi2(v2) ;
	phi2unsew(v2) ;
	phi2sew(phi_1(e), v2) ;
	phi2sew(phi1(e), vv2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
492
493
494
495
}

bool Map2::mergeVolumes(Dart d, Dart e)
{
496
	assert(!isBoundaryMarked(d) && !isBoundaryMarked(e)) ;
Sylvain Thery's avatar
Sylvain Thery committed
497

untereiner's avatar
untereiner committed
498
	if (Map2::isBoundaryFace(d) || Map2::isBoundaryFace(e))
Sylvain Thery's avatar
Sylvain Thery committed
499
500
		return false;

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

Pierre Kraemer's avatar
Pierre Kraemer committed
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
	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
531
		Dart d2 = phi2(*dIt);	// Search the faces adjacent to dNext and eNext
Pierre Kraemer's avatar
Pierre Kraemer committed
532
		Dart e2 = phi2(*eIt);
533
		phi2unsew(d2);		// Unlink the two adjacent faces from dNext and eNext
Sylvain Thery's avatar
Sylvain Thery committed
534
		phi2unsew(e2);
535
		phi2sew(d2, e2);	// Link the two adjacent faces together
Pierre Kraemer's avatar
Pierre Kraemer committed
536
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
537
538
	Map1::deleteCycle(d);		// Delete the two alone faces
	Map1::deleteCycle(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
539
540
541
542

	return true ;
}

543
void Map2::splitSurface(std::vector<Dart>& vd, bool firstSideClosed, bool secondSideClosed)
544
{
545
//	assert(checkSimpleOrientedPath(vd)) ;
546

547
548
	Dart e = vd.front() ;
	Dart e2 = phi2(e) ;
549
550
551

	//unsew the edge path
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
552
553
554
555
	{
		if(!Map2::isBoundaryEdge(*it))
			unsewFaces(*it) ;
	}
556

557
	if(firstSideClosed)
untereiner's avatar
untereiner committed
558
		Map2::fillHole(e) ;
559

560
	if(secondSideClosed)
untereiner's avatar
untereiner committed
561
		Map2::fillHole(e2) ;
562
563
}

Pierre Kraemer's avatar
Pierre Kraemer committed
564
565
566
567
568
569
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

bool Map2::sameOrientedVertex(Dart d, Dart e)
{
570
	Dart it = d;				// Foreach dart dNext in the vertex of d
Pierre Kraemer's avatar
Pierre Kraemer committed
571
572
	do
	{
573
		if (it == e)			// Test equality with e
Pierre Kraemer's avatar
Pierre Kraemer committed
574
			return true;
575
		it = phi2(phi_1(it));
576
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
577
578
579
	return false;				// None is equal to e => vertices are distinct
}

580
581
582
unsigned int Map2::vertexDegree(Dart d)
{
	unsigned int count = 0 ;
583
	Dart it = d ;
584
585
586
	do
	{
		++count ;
587
		it = phi2(phi_1(it)) ;
588
	} while (it != d) ;
589
590
591
	return count ;
}

592
593
594
595
596
597
598
bool Map2::isBoundaryVertex(Dart d)
{
	Dart it = d ;
	do
	{
		if (isBoundaryMarked(it))
			return true ;
599
		it = phi2(phi_1(it)) ;
600
601
602
603
604
605
606
607
608
609
610
	} while (it != d) ;
	return false ;
}

Dart Map2::findBoundaryEdgeOfVertex(Dart d)
{
	Dart it = d ;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
611
		it = phi2(phi_1(it)) ;
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
	} 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 ;
}

628
bool Map2::sameOrientedVolume(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
629
{
630
631
632
633
634
635
636
	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
637
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Pierre Kraemer's avatar
Pierre Kraemer committed
638
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
639
		if (!isBoundaryMarked(*face) && !mark.isMarked(*face))		// Face has not been visited yet
640
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
641
			Dart it = *face ;
642
643
			do
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
644
				if(it == e)
645
646
					return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
647
648
649
				mark.mark(it);						// Mark
				Dart adj = phi2(it);				// Get adjacent face
				if (!isBoundaryMarked(adj) && !mark.isMarked(adj))
650
					visitedFaces.push_back(adj);	// Add it
Pierre Kraemer's avatar
Pierre Kraemer committed
651
652
				it = phi1(it);
			} while(it != *face);
653
654
655
		}
	}
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
656
657
658
659
660
661
662
663
664
665
666
667
668
}

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
669
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
670
	{
Sylvain Thery's avatar
Sylvain Thery committed
671
672
		Dart df = visitedFaces[i];
		if (!isBoundaryMarked(df) && !mark.isMarked(df))		// Face has not been visited yet
Pierre Kraemer's avatar
Pierre Kraemer committed
673
674
		{
			++count;
675
			Dart it = df ;
Pierre Kraemer's avatar
Pierre Kraemer committed
676
677
			do
			{
678
679
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
Sylvain Thery's avatar
Sylvain Thery committed
680
				if ( !isBoundaryMarked(adj) && !mark.isMarked(adj) )
681
682
683
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
Pierre Kraemer's avatar
Pierre Kraemer committed
684
685
686
687
688
689
690
691
		}
	}

	return count;
}

bool Map2::isTriangular()
{
692
693
	TraversorF<Map2> t(*this) ;
	for(Dart d = t.begin(); d != t.end(); d = t.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
694
	{
695
696
		if(faceDegree(d) != 3)
			return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
697
698
699
700
701
702
	}
	return true ;
}

bool Map2::check()
{
703
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
704
	DartMarker m(*this);
Pierre Kraemer's avatar
Pierre Kraemer committed
705
	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
706
707
708
709
	{
		Dart d2 = phi2(d);
		if (phi2(d2) != d)	// phi2 involution ?
		{
710
			CGoGNout << "Check: phi2 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
711
712
			return false;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
713
714
715
716
717
		if(d2 == d)
		{
			CGoGNout << "Check: phi2 fixed point" << CGoGNendl;
			return false;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
718
719
720
721

		Dart d1 = phi1(d);
		if (phi_1(d1) != d)	// phi1 a une image correcte ?
		{
722
			CGoGNout << "Check: inconsistent phi_1 link" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
723
724
725
726
727
			return false;
		}

		if (m.isMarked(d1))	// phi1 a un seul antécédent ?
		{
728
			CGoGNout << "Check: dart with two phi1 predecessors" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
729
730
731
732
733
			return false;
		}
		m.mark(d1);

		if (d1 == d)
734
			CGoGNout << "Check: (warning) face loop (one edge)" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
735
		if (phi1(d1) == d)
736
			CGoGNout << "Check: (warning) face with only two edges" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
737
		if (phi2(d1) == d)
738
			CGoGNout << "Check: (warning) dangling edge" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
739
	}
740

Pierre Kraemer's avatar
Pierre Kraemer committed
741
	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
742
743
744
	{
		if (!m.isMarked(d))	// phi1 a au moins un antécédent ?
		{
745
			CGoGNout << "Check: dart with no phi1 predecessor" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
746
747
748
			return false;
		}
	}
749

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

Pierre Kraemer's avatar
Pierre Kraemer committed
752
753
754
	return true;
}

untereiner's avatar
untereiner committed
755
756
bool Map2::checkSimpleOrientedPath(std::vector<Dart>& vd)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
757
	DartMarkerStore dm(*this) ;
untereiner's avatar
untereiner committed
758
759
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
760
761
762
763
		if(dm.isMarked(*it))
			return false ;
		dm.markOrbit(VERTEX, *it) ;

untereiner's avatar
untereiner committed
764
765
766
767
768
		std::vector<Dart>::iterator prev ;
		if(it == vd.begin())
			prev = vd.end() - 1 ;
		else
			prev = it - 1 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
769

untereiner's avatar
untereiner committed
770
771
772
773
774
775
		if(!sameVertex(*it, phi1(*prev)))
			return false ;
	}
	return true ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
776
777
778
779
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
780
bool Map2::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
781
782
783
784
785
786
{
	Dart dNext = d;
	do
	{
		if (f(dNext))
			return true;
787
		dNext = phi2(phi_1(dNext));
Pierre Kraemer's avatar
Pierre Kraemer committed
788
789
790
791
 	} while (dNext != d);
 	return false;
}

Sylvain Thery's avatar
Sylvain Thery committed
792
bool Map2::foreach_dart_of_edge(Dart d, FunctorType& fonct, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
793
794
795
{
	if (fonct(d))
		return true;
Sylvain Thery's avatar
Sylvain Thery committed
796
	return fonct(phi2(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
797
798
}

799
bool Map2::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
800
{
untereiner's avatar
untereiner committed
801
	DartMarkerStore mark(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
802
803
	bool found = false;				// Last functor return value

untereiner's avatar
untereiner committed
804
805
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
806
807
808
	visitedFaces.push_back(d);		// Start with the face of d

	// For every face added to the list
809
	for(unsigned int i = 0; !found && i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
810
	{
811
		if (!mark.isMarked(visitedFaces[i]))	// Face has not been visited yet
Pierre Kraemer's avatar
Pierre Kraemer committed
812
813
		{
			// Apply functor to the darts of the face
814
			found = Map2::foreach_dart_of_face(visitedFaces[i], f);
Pierre Kraemer's avatar
Pierre Kraemer committed
815
816
817
818
819

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
820
				Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
821
822
				do
				{
823
824
825
					mark.mark(e);				// Mark
					Dart adj = phi2(e);			// Get adjacent face
					if (!mark.isMarked(adj))
Pierre Kraemer's avatar
Pierre Kraemer committed
826
						visitedFaces.push_back(adj);	// Add it
untereiner's avatar
untereiner committed
827
					e = phi1(e);
828
				} while(e != visitedFaces[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
829
830
831
832
833
834
			}
		}
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
835
/*! @name Close map after import or creation
836
 *  These functions must be used with care, generally only by import/creation algorithms
Pierre Kraemer's avatar
Pierre Kraemer committed
837
838
 *************************************************************************/

839
unsigned int Map2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
{
	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
867
868
	if(forboundary)
		boundaryMarkOrbit(FACE, phi2(d));
869

Pierre Kraemer's avatar
Pierre Kraemer committed
870
871
872
	return countEdges ;
}

873
unsigned int Map2::closeMap()
Pierre Kraemer's avatar
Pierre Kraemer committed
874
875
{
	// Search the map for topological holes (fix points of phi2)
876
	unsigned int nb = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
877
878
879
	for (Dart d = begin(); d != end(); next(d))
	{
		if (phi2(d) == d)
880
881
		{
			++nb ;
Pierre Kraemer's avatar
Pierre Kraemer committed
882
			closeHole(d);
883
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
884
	}
885
	return nb ;
Pierre Kraemer's avatar
Pierre Kraemer committed
886
}
Pierre Kraemer's avatar
Pierre Kraemer committed
887
888

} // namespace CGoGN