map2.cpp 21.9 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
void Map2::createHole(Dart d)
{
	assert(!isBoundaryEdge(d)) ;
	boundaryMarkOrbit<FACE,2>(d) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
199
200
201
202
203
204
/*! @name Topological Operators
 *  Topological operations on 2-maps
 *************************************************************************/

void Map2::splitVertex(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
205
	assert(sameVertex(d, e)) ;
David Cazier's avatar
David Cazier committed
206
207
208
209
210
	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
211
212
}

213
Dart Map2::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
214
{
215
	//TODO utile ?
Pierre Kraemer's avatar
Pierre Kraemer committed
216
	if(isBoundaryVertex(d))
217
		return NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
218

219
	Dart res = NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
220
221
222
	Dart vit = d ;
	do
	{
223
224
225
		if(res == NIL && phi1(phi1(d)) != d)
			res = phi1(d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
226
227
		Dart f = phi_1(phi2(vit)) ;
		phi1sew(vit, f) ;
228

229
		vit = phi2(phi_1(vit)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
230
	} while(vit != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
231
	Map1::deleteCycle(d) ;
232
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
233
234
}

David Cazier's avatar
David Cazier committed
235
Dart Map2::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
236
237
{
	Dart e = phi2(d);
238
	phi2unsew(d);					// remove old phi2 links
Pierre Kraemer's avatar
Pierre Kraemer committed
239
240
	Dart nd = Map1::cutEdge(d);		// Cut the 1-edge of d
	Dart ne = Map1::cutEdge(e);		// Cut the 1-edge of phi2(d)
241
	phi2sew(d, ne);					// Correct the phi2 links
Pierre Kraemer's avatar
Pierre Kraemer committed
242
	phi2sew(e, nd);
David Cazier's avatar
David Cazier committed
243
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
244
245
}

Pierre Kraemer's avatar
Pierre Kraemer committed
246
bool Map2::uncutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
247
{
Pierre Kraemer's avatar
Pierre Kraemer committed
248
	if(vertexDegree(phi1(d)) == 2)
Pierre Kraemer's avatar
Pierre Kraemer committed
249
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
250
		Dart e = phi2(phi1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
251
252
		phi2unsew(e) ;
		phi2unsew(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
253
254
		Map1::uncutEdge(d) ;
		Map1::uncutEdge(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
255
		phi2sew(d, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
256
		return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
257
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
258
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
259
260
}

261
Dart Map2::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
262
{
Pierre Kraemer's avatar
Pierre Kraemer committed
263
	Dart resV = NIL ;
264
265

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

268
	Dart f = phi1(e) ;
269
	Dart h = phi2(phi_1(e));
270

271
	if (h != e)
272
		resV = h;
273

274
	if (f != e && delDegenerateFaces)
Sylvain Thery's avatar
Sylvain Thery committed
275
276
	{
		Map1::collapseEdge(e) ;		// Collapse edge e
277
		collapseDegeneratedFace(f) ;// and collapse its face if degenerated
Sylvain Thery's avatar
Sylvain Thery committed
278
279
	}
	else
280
		Map1::collapseEdge(e) ;	// Just collapse edge e
281

282
283
	f = phi1(d) ;
	if(resV == NIL)
284
	{
285
		h = phi2(phi_1(d));
286
		if (h != d)
287
			resV = h;
288
289
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
290
291
	if (f != d && delDegenerateFaces)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
292
293
		Map1::collapseEdge(d) ;		// Collapse edge d
		collapseDegeneratedFace(f) ;// and collapse its face if degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
294
295
	}
	else
Pierre Kraemer's avatar
Pierre Kraemer committed
296
		Map1::collapseEdge(d) ;	// Just collapse edge d
297
298

	return resV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
299
300
301
302
}

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

339
340
	Dart d2 = phi2(d);
	Dart e2 = phi2(e);
untereiner's avatar
untereiner committed
341
342
343
344
345

	phi2unsew(d);
	phi2unsew(e) ;

	phi2sew(d, e);
346
	phi2sew(d2, e2);
untereiner's avatar
untereiner committed
347
348
}

349
void Map2::sewFaces(Dart d, Dart e, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
350
{
351
352
353
	// if sewing with fixed points
	if (!withBoundary)
	{
354
355
356
		assert(phi2(d) == d && phi2(e) == e) ;
		phi2sew(d, e) ;
		return ;
357
	}
358

359
	assert(isBoundaryEdge(d) && isBoundaryEdge(e)) ;
360

361
362
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
363

364
365
	phi2unsew(d) ;	// unsew faces from boundary
	phi2unsew(e) ;
366

367
368
369
370
371
	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
372

373
	phi2sew(d, e) ; // sew the faces
Pierre Kraemer's avatar
Pierre Kraemer committed
374
375
}

376
void Map2::unsewFaces(Dart d, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
377
{
378
379
380
381
382
383
	if (!withBoundary)
	{
		phi2unsew(d) ;
		return ;
	}

untereiner's avatar
untereiner committed
384
	assert(!Map2::isBoundaryEdge(d)) ;
385

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

Pierre Kraemer's avatar
Pierre Kraemer committed
388
	Dart e = newBoundaryCycle(2) ;
389
	Dart ee = phi1(e) ;
Sylvain Thery's avatar
Sylvain Thery committed
390

Pierre Kraemer's avatar
Pierre Kraemer committed
391
	Dart f = findBoundaryEdgeOfVertex(d) ;
392
393
	Dart ff = findBoundaryEdgeOfVertex(dd) ;

untereiner's avatar
untereiner committed
394
	if(f != NIL)
Pierre Kraemer's avatar
Pierre Kraemer committed
395
		phi1sew(e, phi_1(f)) ;
Sylvain Thery's avatar
Sylvain Thery committed
396

397
398
	if(ff != NIL)
		phi1sew(ee, phi_1(ff)) ;
Sylvain Thery's avatar
Sylvain Thery committed
399

Pierre Kraemer's avatar
Pierre Kraemer committed
400
	phi2unsew(d) ;
401

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

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

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

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

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

457
458
459
	assert(!isBoundaryFace(d) && !isBoundaryFace(e)) ;
	assert(faceDegree(d) == 3 && faceDegree(e) == 3) ;

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

	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
471
472
473
474
475
}

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

477
478
	assert(v1 != v2 && sameOrientedVertex(v1, v2)) ;
	assert(faceDegree(d) == 3 && faceDegree(phi2(d)) == 3) ;
Sylvain Thery's avatar
Sylvain Thery committed
479

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

	Dart vv2 = phi2(v2) ;
	phi2unsew(v2) ;
	phi2sew(phi_1(e), v2) ;
	phi2sew(phi1(e), vv2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
489
490
491
492
}

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

untereiner's avatar
untereiner committed
495
	if (Map2::isBoundaryFace(d) || Map2::isBoundaryFace(e))
Sylvain Thery's avatar
Sylvain Thery committed
496
497
		return false;

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

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

	return true ;
}

540
void Map2::splitSurface(std::vector<Dart>& vd, bool firstSideClosed, bool secondSideClosed)
541
{
542
//	assert(checkSimpleOrientedPath(vd)) ;
543

544
545
	Dart e = vd.front() ;
	Dart e2 = phi2(e) ;
546
547
548

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

554
	if(firstSideClosed)
untereiner's avatar
untereiner committed
555
		Map2::fillHole(e) ;
556

557
	if(secondSideClosed)
untereiner's avatar
untereiner committed
558
		Map2::fillHole(e2) ;
559
560
}

Pierre Kraemer's avatar
Pierre Kraemer committed
561
562
563
564
565
566
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

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

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

589
590
591
592
593
bool Map2::isBoundaryVertex(Dart d)
{
	Dart it = d ;
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
594
		if (isBoundaryMarked2(it))
595
			return true ;
596
		it = phi2(phi_1(it)) ;
597
598
599
600
601
602
603
604
605
	} while (it != d) ;
	return false ;
}

Dart Map2::findBoundaryEdgeOfVertex(Dart d)
{
	Dart it = d ;
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
606
		if (isBoundaryMarked2(it))
607
			return it ;
608
		it = phi2(phi_1(it)) ;
609
610
611
612
	} while (it != d) ;
	return NIL ;
}

613
614
615
616
617
Dart Map2::findBoundaryEdgeOfFace(Dart d)
{
	Dart it = d ;
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
618
		if (isBoundaryMarked2(phi2(it)))
619
620
621
622
623
624
			return phi2(it) ;
		it = phi1(it) ;
	} while (it != d) ;
	return NIL ;
}

625
626
627
628
629
bool Map2::isBoundaryFace(Dart d)
{
	Dart it = d ;
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
630
		if (isBoundaryMarked2(phi2(it)))
631
632
633
634
635
636
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

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

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

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

	return count;
}

bool Map2::isTriangular()
{
701
702
	TraversorF<Map2> t(*this) ;
	for(Dart d = t.begin(); d != t.end(); d = t.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
703
	{
704
705
		if(faceDegree(d) != 3)
			return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
706
707
708
709
710
711
	}
	return true ;
}

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

		Dart d1 = phi1(d);
		if (phi_1(d1) != d)	// phi1 a une image correcte ?
		{
731
			CGoGNout << "Check: inconsistent phi_1 link" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
732
733
734
735
736
			return false;
		}

		if (m.isMarked(d1))	// phi1 a un seul antécédent ?
		{
737
			CGoGNout << "Check: dart with two phi1 predecessors" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
738
739
740
741
742
			return false;
		}
		m.mark(d1);

		if (d1 == d)
743
			CGoGNout << "Check: (warning) face loop (one edge)" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
744
		if (phi1(d1) == d)
745
			CGoGNout << "Check: (warning) face with only two edges" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
746
		if (phi2(d1) == d)
747
			CGoGNout << "Check: (warning) dangling edge" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
748
	}
749

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

759
	CGoGNout << "Check: topology ok" << CGoGNendl;
760

Pierre Kraemer's avatar
Pierre Kraemer committed
761
762
763
	return true;
}

untereiner's avatar
untereiner committed
764
765
bool Map2::checkSimpleOrientedPath(std::vector<Dart>& vd)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
766
	DartMarkerStore dm(*this) ;
untereiner's avatar
untereiner committed
767
768
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
769
770
		if(dm.isMarked(*it))
			return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
771
		dm.markOrbit<VERTEX>(*it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
772

untereiner's avatar
untereiner committed
773
774
775
776
777
		std::vector<Dart>::iterator prev ;
		if(it == vd.begin())
			prev = vd.end() - 1 ;
		else
			prev = it - 1 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
778

untereiner's avatar
untereiner committed
779
780
781
782
783
784
		if(!sameVertex(*it, phi1(*prev)))
			return false ;
	}
	return true ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
785
786
787
788
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
789
bool Map2::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
790
791
792
793
794
795
{
	Dart dNext = d;
	do
	{
		if (f(dNext))
			return true;
796
		dNext = phi2(phi_1(dNext));
Pierre Kraemer's avatar
Pierre Kraemer committed
797
798
799
800
 	} while (dNext != d);
 	return false;
}

Sylvain Thery's avatar
Sylvain Thery committed
801
bool Map2::foreach_dart_of_edge(Dart d, FunctorType& fonct, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
802
803
804
{
	if (fonct(d))
		return true;
Sylvain Thery's avatar
Sylvain Thery committed
805
	return fonct(phi2(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
806
807
}

808
bool Map2::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
809
{
untereiner's avatar
untereiner committed
810
	DartMarkerStore mark(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
811
812
	bool found = false;				// Last functor return value

untereiner's avatar
untereiner committed
813
814
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
815
816
817
	visitedFaces.push_back(d);		// Start with the face of d

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
844
/*! @name Close map after import or creation
845
 *  These functions must be used with care, generally only by import/creation algorithms
Pierre Kraemer's avatar
Pierre Kraemer committed
846
847
 *************************************************************************/

848
849
850
851
852
853
854
Dart Map2::newBoundaryCycle(unsigned int nbE)
{
	Dart d = Map1::newCycle(nbE);
	boundaryMarkOrbit<FACE,2>(d);
	return d;
}

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

883
	if (forboundary)
Thery Sylvain's avatar
Thery Sylvain committed
884
		boundaryMarkOrbit<FACE,2>(phi2(d));
885

Pierre Kraemer's avatar
Pierre Kraemer committed
886
887
888
	return countEdges ;
}

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

untereiner's avatar
untereiner committed
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
948
949
950
951
952
953
/*! @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
954
		if(isBoundaryMarked2(d))
untereiner's avatar
untereiner committed
955
		{
untereiner's avatar
untereiner committed
956
			boundaryMarkOrbit<FACE,2>(deleteVertex(phi2(d)));
untereiner's avatar
untereiner committed
957
958
959
960
		}
	}
}

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