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 23.5 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
		Dart e = newBoundaryCycle(nbEdges);
116

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
{
Thery Sylvain's avatar
Thery Sylvain committed
130
	assert(!isBoundaryMarked2(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
	assert(isBoundaryEdge(d)) ;
	Dart dd = d ;
Thery Sylvain's avatar
Thery Sylvain committed
188
	if(!isBoundaryMarked2(dd))
189
		dd = phi2(dd) ;
Thery Sylvain's avatar
Thery Sylvain committed
190
	boundaryUnmarkOrbit<FACE,2>(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

	phi2unsew(d);
	phi2unsew(e) ;

	phi2sew(d, e);
340
	phi2sew(d2, e2);
untereiner's avatar
untereiner committed
341
342
}

343
void Map2::sewFaces(Dart d, Dart e, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
344
{
345
346
347
	// if sewing with fixed points
	if (!withBoundary)
	{
348
349
350
		assert(phi2(d) == d && phi2(e) == e) ;
		phi2sew(d, e) ;
		return ;
351
	}
352

353
	assert(isBoundaryEdge(d) && isBoundaryEdge(e)) ;
354

355
356
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
357

358
359
	phi2unsew(d) ;	// unsew faces from boundary
	phi2unsew(e) ;
360

361
362
363
364
365
	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
366

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

370
void Map2::unsewFaces(Dart d, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
371
{
372
373
374
375
376
377
	if (!withBoundary)
	{
		phi2unsew(d) ;
		return ;
	}

untereiner's avatar
untereiner committed
378
	assert(!Map2::isBoundaryEdge(d)) ;
379

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

Pierre Kraemer's avatar
Pierre Kraemer committed
382
	Dart e = newBoundaryCycle(2) ;
383
	Dart ee = phi1(e) ;
Sylvain Thery's avatar
Sylvain Thery committed
384

Pierre Kraemer's avatar
Pierre Kraemer committed
385
	Dart f = findBoundaryEdgeOfVertex(d) ;
386
387
	Dart ff = findBoundaryEdgeOfVertex(dd) ;

untereiner's avatar
untereiner committed
388
	if(f != NIL)
Pierre Kraemer's avatar
Pierre Kraemer committed
389
		phi1sew(e, phi_1(f)) ;
Sylvain Thery's avatar
Sylvain Thery committed
390

391
392
	if(ff != NIL)
		phi1sew(ee, phi_1(ff)) ;
Sylvain Thery's avatar
Sylvain Thery committed
393

Pierre Kraemer's avatar
Pierre Kraemer committed
394
	phi2unsew(d) ;
395

Pierre Kraemer's avatar
Pierre Kraemer committed
396
397
	phi2sew(d, e) ;		// sew faces
	phi2sew(dd, ee) ;	// to the boundary
Pierre Kraemer's avatar
Pierre Kraemer committed
398
399
400
401
}

bool Map2::collapseDegeneratedFace(Dart d)
{
402
	Dart e = phi1(d) ;				// Check if the face is degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
403
404
	if (phi1(e) == d)				// Yes: it contains one or two edge(s)
	{
405
406
407
408
409
410
411
412
413
414
415
416
417
418
		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
419
420
421
422
423
424
425
		return true ;
	}
	return false ;
}

void Map2::splitFace(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
426
	assert(d != e && Map2::sameFace(d, e)) ;
427
428
429
430
	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
431
432
433
434
}

bool Map2::mergeFaces(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
435
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
436
	{
Sylvain Thery's avatar
Sylvain Thery committed
437
		Dart e = phi2(d) ;
438
		phi2unsew(d) ;
439
		Map1::mergeCycles(d, phi1(e)) ;
440
		Map1::splitCycle(e, phi1(d)) ;
441
		Map1::deleteCycle(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
442
443
444
445
446
447
448
449
		return true ;
	}
	return false ;
}

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
454
455
456
457
458
	Dart d1 = phi2(phi1(d)) ;
	Dart d2 = phi2(phi_1(d)) ;
	phi2unsew(d1) ;
	phi2unsew(d2) ;
	phi2sew(d1, d2) ;
459
460
461
462
463
464

	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
465
466
467
468
469
}

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

471
472
	assert(v1 != v2 && sameOrientedVertex(v1, v2)) ;
	assert(faceDegree(d) == 3 && faceDegree(phi2(d)) == 3) ;
Sylvain Thery's avatar
Sylvain Thery committed
473

Pierre Kraemer's avatar
Pierre Kraemer committed
474
475
476
477
	Dart vv1 = phi2(v1) ;
	phi2unsew(v1) ;
	phi2sew(phi_1(d), v1) ;
	phi2sew(phi1(d), vv1) ;
478
479
480
481
482

	Dart vv2 = phi2(v2) ;
	phi2unsew(v2) ;
	phi2sew(phi_1(e), v2) ;
	phi2sew(phi1(e), vv2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
483
484
485
486
}

bool Map2::mergeVolumes(Dart d, Dart e)
{
Thery Sylvain's avatar
Thery Sylvain committed
487
	assert(!isBoundaryMarked2(d) && !isBoundaryMarked2(e)) ;
Sylvain Thery's avatar
Sylvain Thery committed
488

untereiner's avatar
untereiner committed
489
	if (Map2::isBoundaryFace(d) || Map2::isBoundaryFace(e))
Sylvain Thery's avatar
Sylvain Thery committed
490
491
		return false;

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

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

	return true ;
}

534
void Map2::splitSurface(std::vector<Dart>& vd, bool firstSideClosed, bool secondSideClosed)
535
{
536
//	assert(checkSimpleOrientedPath(vd)) ;
537

538
539
	Dart e = vd.front() ;
	Dart e2 = phi2(e) ;
540
541
542

	//unsew the edge path
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
543
	{
544
		//if(!Map2::isBoundaryEdge(*it))
545
546
			unsewFaces(*it) ;
	}
547

548
	if(firstSideClosed)
untereiner's avatar
untereiner committed
549
		Map2::fillHole(e) ;
550

551
	if(secondSideClosed)
untereiner's avatar
untereiner committed
552
		Map2::fillHole(e2) ;
553
554
}

Pierre Kraemer's avatar
Pierre Kraemer committed
555
556
557
558
559
560
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

bool Map2::sameOrientedVertex(Dart d, Dart e)
{
561
	Dart it = d;				// Foreach dart dNext in the vertex of d
Pierre Kraemer's avatar
Pierre Kraemer committed
562
563
	do
	{
564
		if (it == e)			// Test equality with e
Pierre Kraemer's avatar
Pierre Kraemer committed
565
			return true;
566
		it = phi2(phi_1(it));
567
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
568
569
570
	return false;				// None is equal to e => vertices are distinct
}

571
572
573
unsigned int Map2::vertexDegree(Dart d)
{
	unsigned int count = 0 ;
574
	Dart it = d ;
575
576
577
	do
	{
		++count ;
578
		it = phi2(phi_1(it)) ;
579
	} while (it != d) ;
580
581
582
	return count ;
}

583
584
585
586
587
bool Map2::isBoundaryVertex(Dart d)
{
	Dart it = d ;
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
588
		if (isBoundaryMarked2(it))
589
			return true ;
590
		it = phi2(phi_1(it)) ;
591
592
593
594
595
596
597
598
599
	} while (it != d) ;
	return false ;
}

Dart Map2::findBoundaryEdgeOfVertex(Dart d)
{
	Dart it = d ;
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
600
		if (isBoundaryMarked2(it))
601
			return it ;
602
		it = phi2(phi_1(it)) ;
603
604
605
606
	} while (it != d) ;
	return NIL ;
}

607
608
609
610
611
Dart Map2::findBoundaryEdgeOfFace(Dart d)
{
	Dart it = d ;
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
612
		if (isBoundaryMarked2(phi2(it)))
613
614
615
616
617
618
			return phi2(it) ;
		it = phi1(it) ;
	} while (it != d) ;
	return NIL ;
}

619
620
621
622
623
bool Map2::isBoundaryFace(Dart d)
{
	Dart it = d ;
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
624
		if (isBoundaryMarked2(phi2(it)))
625
626
627
628
629
630
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

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

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

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

	return count;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

842
843
844
845
846
847
848
Dart Map2::newBoundaryCycle(unsigned int nbE)
{
	Dart d = Map1::newCycle(nbE);
	boundaryMarkOrbit<FACE,2>(d);
	return d;
}

849
unsigned int Map2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
{
	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);

877
	if (forboundary)
Thery Sylvain's avatar
Thery Sylvain committed
878
		boundaryMarkOrbit<FACE,2>(phi2(d));
879

Pierre Kraemer's avatar
Pierre Kraemer committed
880
881
882
	return countEdges ;
}

883
unsigned int Map2::closeMap()
Pierre Kraemer's avatar
Pierre Kraemer committed
884
885
{
	// Search the map for topological holes (fix points of phi2)
886
	unsigned int nb = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
887
888
889
	for (Dart d = begin(); d != end(); next(d))
	{
		if (phi2(d) == d)
890
891
		{
			++nb ;
Pierre Kraemer's avatar
Pierre Kraemer committed
892
			closeHole(d);
893
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
894
	}
895
	return nb ;
Pierre Kraemer's avatar
Pierre Kraemer committed
896
}
Pierre Kraemer's avatar
Pierre Kraemer committed
897

untereiner's avatar
untereiner committed
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
/*! @name Compute dual
 * These functions compute the dual mesh
 *************************************************************************/

void Map2::reverseOrientation()
{
	DartAttribute<unsigned int> emb0(this, getEmbeddingAttributeVector<VERTEX>()) ;
	if(emb0.isValid())
	{
		DartAttribute<unsigned int> new_emb0 = addAttribute<unsigned int, DART>("new_EMB_0") ;
		for(Dart d = begin(); d != end(); next(d))
			new_emb0[d] = emb0[phi1(d)] ;

		swapAttributes<unsigned int>(emb0, new_emb0) ;
		removeAttribute(new_emb0) ;
	}

	DartAttribute<Dart> n_phi1 = getAttribute<Dart, DART>("phi1") ;
	DartAttribute<Dart> n_phi_1 = getAttribute<Dart, DART>("phi_1") ;
	swapAttributes<Dart>(n_phi1, n_phi_1) ;
}

void Map2::computeDual()
{
	DartAttribute<Dart> old_phi1 = getAttribute<Dart, DART>("phi1");
	DartAttribute<Dart> old_phi_1 = getAttribute<Dart, DART>("phi_1") ;
	DartAttribute<Dart> new_phi1 = addAttribute<Dart, DART>("new_phi1") ;
	DartAttribute<Dart> new_phi_1 = addAttribute<Dart, DART>("new_phi_1") ;

	for(Dart d = begin(); d != end(); next(d))
	{
		Dart dd = phi1(phi2(d));

		new_phi1[d] = dd ;
		new_phi_1[dd] = d ;
	}

	swapAttributes<Dart>(old_phi1, new_phi1) ;
	swapAttributes<Dart>(old_phi_1, new_phi_1) ;

	removeAttribute(new_phi1) ;
	removeAttribute(new_phi_1) ;

	swapEmbeddingContainers(VERTEX, FACE) ;

	reverseOrientation() ;

	//boundary management
	for(Dart d = begin(); d != end(); next(d))
	{
untereiner's avatar
untereiner committed
948
		if(isBoundaryMarked2(d))
untereiner's avatar
untereiner committed
949
		{
untereiner's avatar
untereiner committed
950
			boundaryMarkOrbit<FACE,2>(deleteVertex(phi2(d)));
untereiner's avatar
untereiner committed
951
952
953
954
955
956
957
958
959
960
961
		}
	}
}

//TODO triangulation of the boundary face to compute correctly the dual(dual(T)) of mesh T
void Map2::computeDualBorderConstraint()
{
	//unmarkBoundary
	std::vector<Dart> oldb;
	for(Dart d = begin(); d != end(); next(d))
	{
untereiner's avatar
untereiner committed
962
		if(isBoundaryMarked2(d))
untereiner's avatar
untereiner committed
963
964
		{
			oldb.push_back(d);
untereiner's avatar
untereiner committed
965
			boundaryUnmarkOrbit<FACE,2>(d);
untereiner's avatar
untereiner committed
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
		}
	}

	//triangule old boundary faces
	for(std::vector<Dart>::iterator it = oldb.begin() ; it != oldb.end() ; ++it)
	{
		Dart db = *it;
		Dart d1 = phi1(db);
		splitFace(db, d1) ;
		cutEdge(phi_1(db)) ;
		Dart x = phi2(phi_1(db)) ;
		Dart dd = phi1(phi1(phi1(x)));
		while(dd != x)
		{
			Dart next = phi1(dd) ;
			splitFace(dd, phi1(x)) ;
			dd = next ;
		}
	}

	//after dual computation -> mark the new faces created with oldes vertices as a boundary facesc


	//compute dual

	DartAttribute<Dart> old_phi1 = getAttribute<Dart, DART>("phi1");
	DartAttribute<Dart> old_phi_1 = getAttribute<Dart, DART>("phi_1") ;
	DartAttribute<Dart> new_phi1 = addAttribute<Dart, DART>("new_phi1") ;
	DartAttribute<Dart> new_phi_1 = addAttribute<Dart, DART>("new_phi_1") ;

	for(Dart d = begin(); d != end(); next(d))
	{
		Dart dd = phi1(phi2(d));

		new_phi1[d] = dd ;
		new_phi_1[dd] = d ;
	}

	swapAttributes<Dart>(old_phi1, new_phi1) ;
	swapAttributes<Dart>(old_phi_1, new_phi_1) ;

	removeAttribute(new_phi1) ;
	removeAttribute(new_phi_1) ;

	swapEmbeddingContainers(VERTEX, FACE) ;

	reverseOrientation() ;

	//boundary management
	for(Dart d = begin(); d != end(); next(d))
	{
untereiner's avatar
untereiner committed
1017
		if(isBoundaryMarked2(d))
untereiner's avatar
untereiner committed
1018
		{
untereiner's avatar
untereiner committed
1019
			boundaryMarkOrbit<FACE,2>(deleteVertex(phi2(d)));
untereiner's avatar
untereiner committed
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
		}
	}


	//	for(std::vector<Dart>::iterator it = oldb.begin() ; it != oldb.end() ; ++it)
	//	{
	//		boundaryMarkOrbit<FACE>(*it);
	//	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1030
} // namespace CGoGN