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
	assert(isBoundaryEdge(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi2(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
190
	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)
{
untereiner's avatar
untereiner committed
199
	assert(sameVertex(d, e)) ;
David Cazier's avatar
David Cazier committed
200
201
202
203
204
	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
	//TODO utile ?
Pierre Kraemer's avatar
Pierre Kraemer committed
210
	if(isBoundaryVertex(d))
211
		return NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
212

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

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

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

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

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

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

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

262
	Dart f = phi1(e) ;
263
	Dart h = phi2(phi_1(e));
264

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

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

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

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

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

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

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

	phi2unsew(d);
	phi2unsew(e) ;

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

343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
void Map2::insertEdgeInVertex(Dart d, Dart e)
{
	assert(!sameVertex(d,e));
	assert(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 ;
}
359

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

370
	assert(isBoundaryEdge(d) && isBoundaryEdge(e)) ;
371

372
373
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
374

375
376
	phi2unsew(d) ;	// unsew faces from boundary
	phi2unsew(e) ;
377

378
379
380
381
382
	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
383

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

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

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

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

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

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
405
	phi2unsew(d) ;
406

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

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

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

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

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

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

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

	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
476
477
478
479
480
}

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

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

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

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

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

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
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
531
532
	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
533
		Dart d2 = phi2(*dIt);	// Search the faces adjacent to dNext and eNext
Pierre Kraemer's avatar
Pierre Kraemer committed
534
		Dart e2 = phi2(*eIt);
535
		phi2unsew(d2);		// Unlink the two adjacent faces from dNext and eNext
Sylvain Thery's avatar
Sylvain Thery committed
536
		phi2unsew(e2);
537
		phi2sew(d2, e2);	// Link the two adjacent faces together
Pierre Kraemer's avatar
Pierre Kraemer committed
538
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
539
540
	Map1::deleteCycle(d);		// Delete the two alone faces
	Map1::deleteCycle(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
541
542
543
544

	return true ;
}

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

549
550
	Dart e = vd.front() ;
	Dart e2 = phi2(e) ;
551
552
553

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

559
	if(firstSideClosed)
untereiner's avatar
untereiner committed
560
		Map2::fillHole(e) ;
561

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

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

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

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

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

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

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

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

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

	return count;
}

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

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

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

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

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

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

752
	CGoGNout << "Check: topology ok" << CGoGNendl;
753

Pierre Kraemer's avatar
Pierre Kraemer committed
754
755
756
	return true;
}

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

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

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

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

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

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

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

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

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

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

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

841
unsigned int Map2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
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
867
868
{
	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
869
	if(forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
870
		boundaryMarkOrbit<FACE>(phi2(d));
871

Pierre Kraemer's avatar
Pierre Kraemer committed
872
873
874
	return countEdges ;
}

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

} // namespace CGoGN