map2.cpp 19.3 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1
2
3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2011, IGG Team, LSIIT, University of Strasbourg           *
Pierre Kraemer's avatar
Pierre Kraemer committed
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
*                                                                              *
* This library is free software; you can redistribute it and/or modify it      *
* under the terms of the GNU Lesser General Public License as published by the *
* Free Software Foundation; either version 2.1 of the License, or (at your     *
* option) any later version.                                                   *
*                                                                              *
* This library is distributed in the hope that it will be useful, but WITHOUT  *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License  *
* for more details.                                                            *
*                                                                              *
* You should have received a copy of the GNU Lesser General Public License     *
* along with this library; if not, write to the Free Software Foundation,      *
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.           *
*                                                                              *
20
* Web site: http://cgogn.u-strasbg.fr/                                         *
Pierre Kraemer's avatar
Pierre Kraemer committed
21
22
23
24
25
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/map/map2.h"
26
#include "Topology/generic/traversorCell.h"
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
69
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
void Map2::compactTopoRelations(const std::vector<unsigned int>& oldnew)
{
	for (unsigned int i = m_attribs[DART].begin(); i != m_attribs[DART].end(); m_attribs[DART].next(i))
	{
		{
			Dart& d = m_phi1->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
		{
			Dart& d = m_phi_1->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
		{
			Dart& d = m_phi2->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
95
96
97
98
/*! @name Generator and Deletor
 *  To generate or delete faces in a 2-map
 *************************************************************************/

99
Dart Map2::newFace(unsigned int nbEdges, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
100
{
101
	Dart d = Map1::newCycle(nbEdges);
102
	if (withBoundary)
103
	{
104
105
		Dart e = Map1::newBoundaryCycle(nbEdges);

106
		Dart it = d;
107
108
		do
		{
109
110
			phi2sew(it, e);
			it = phi1(it);
111
			e = phi_1(e);
112
		} while (it != d);
113
114
	}
	return d;
115
116
}

117
void Map2::deleteFace(Dart d, bool withBoundary)
118
119
{
	assert(!isBoundaryMarked(d)) ;
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
	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
135
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
136
137
	do
	{
138
		phi2unsew(it);
139
140
		it = phi1(it) ;
	} while(it != d) ;
141
	Map1::deleteCycle(d);
142
143
}

untereiner's avatar
untereiner committed
144
145
146
147
148
void Map2::deleteCC(Dart d)
{
	DartMarkerStore mark(*this);

	std::vector<Dart> visited;
149
	visited.reserve(1024) ;
untereiner's avatar
untereiner committed
150
	visited.push_back(d);
151
	mark.mark(d) ;
untereiner's avatar
untereiner committed
152

153
	for(unsigned int i = 0; i < visited.size(); ++i)
untereiner's avatar
untereiner committed
154
	{
155
		Dart d1 = phi1(visited[i]) ;
156
		if(!mark.isMarked(d1))
untereiner's avatar
untereiner committed
157
		{
158
159
160
			visited.push_back(d1) ;
			mark.mark(d1);
		}
161
		Dart d2 = phi2(visited[i]) ;
162
163
164
165
		if(!mark.isMarked(d2))
		{
			visited.push_back(d2) ;
			mark.mark(d2);
untereiner's avatar
untereiner committed
166
167
168
		}
	}

169
	for(std::vector<Dart>::iterator it = visited.begin(); it != visited.end(); ++it)
untereiner's avatar
untereiner committed
170
171
172
		deleteDart(*it) ;
}

173
174
void Map2::fillHole(Dart d)
{
175
176
177
178
179
	assert(isBoundaryEdge(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi2(dd) ;
	boundaryUnmarkOrbit(FACE, dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
180
181
182
183
184
185
186
187
}

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

void Map2::splitVertex(Dart d, Dart e)
{
David Cazier's avatar
David Cazier committed
188
189
190
191
192
193
	assert(sameOrientedVertex(d, e)) ;
	Dart d2 = phi2(d) ; assert(d != d2) ;
	Dart e2 = phi2(e) ; assert(e != e2) ;
	Dart nd = Map1::cutEdge(d2) ;	// Cut the edge of dd (make a new half edge)
	Dart ne = Map1::cutEdge(e2) ;	// Cut the edge of ee (make a new half edge)
	phi2sew(nd, ne) ;				// Sew the two faces along the new edge
Pierre Kraemer's avatar
Pierre Kraemer committed
194
195
}

196
Dart Map2::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
197
198
{
	if(isBoundaryVertex(d))
199
		return NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
200

201
	Dart res = NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
202
203
204
	Dart vit = d ;
	do
	{
205
206
207
		if(res == NIL && phi1(phi1(d)) != d)
			res = phi1(d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
208
209
		Dart f = phi_1(phi2(vit)) ;
		phi1sew(vit, f) ;
210

Pierre Kraemer's avatar
Pierre Kraemer committed
211
212
		vit = alpha1(vit) ;
	} while(vit != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
213
	Map1::deleteCycle(d) ;
214
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
215
216
}

David Cazier's avatar
David Cazier committed
217
Dart Map2::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
218
219
{
	Dart e = phi2(d);
Sylvain Thery's avatar
Sylvain Thery committed
220
	phi2unsew(d);			// remove old phi2 links
Pierre Kraemer's avatar
Pierre Kraemer committed
221
222
223
224
	Dart nd = Map1::cutEdge(d);		// Cut the 1-edge of d
	Dart ne = Map1::cutEdge(e);		// Cut the 1-edge of phi2(d)
	phi2sew(d, ne);	// Correct the phi2 links
	phi2sew(e, nd);
David Cazier's avatar
David Cazier committed
225
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
226
227
}

Pierre Kraemer's avatar
Pierre Kraemer committed
228
bool Map2::uncutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
229
{
Pierre Kraemer's avatar
Pierre Kraemer committed
230
	if(vertexDegree(phi1(d)) == 2)
Pierre Kraemer's avatar
Pierre Kraemer committed
231
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
232
		Dart e = phi2(phi1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
233
234
		phi2unsew(e) ;
		phi2unsew(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
235
236
		Map1::uncutEdge(d) ;
		Map1::uncutEdge(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
237
		phi2sew(d, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
238
		return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
239
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
240
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
241
242
}

243
Dart Map2::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
244
{
Pierre Kraemer's avatar
Pierre Kraemer committed
245
	Dart resV = NIL ;
246
247

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

250
251
	Dart f = phi1(e) ;
	Dart h = alpha1(e);
252

253
	if (h != e)
254
		resV = h;
255

256
	if (f != e && delDegenerateFaces)
Sylvain Thery's avatar
Sylvain Thery committed
257
258
	{
		Map1::collapseEdge(e) ;		// Collapse edge e
259
		collapseDegeneratedFace(f) ;// and collapse its face if degenerated
Sylvain Thery's avatar
Sylvain Thery committed
260
261
	}
	else
262
		Map1::collapseEdge(e) ;	// Just collapse edge e
263

264
265
	f = phi1(d) ;
	if(resV == NIL)
266
	{
267
268
		h = alpha1(d);
		if (h != d)
269
			resV = h;
270
271
	}

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

	return resV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
281
282
283
284
}

bool Map2::flipEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
285
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
286
	{
Sylvain Thery's avatar
Sylvain Thery committed
287
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
		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
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
		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
}

317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
//void Map2::insertEdgeInVertex(Dart d, Dart e)
//{
//	assert(!sameVertex(d,e) && phi2(e) == phi_1(e));
//	phi1sew(phi_1(d), phi_1(e));
//}
//
//bool Map2::removeEdgeFromVertex(Dart d)
//{
//	if (!isBoundaryEdge(d))
//	{
//		phi1sew(phi_1(d), phi2(d)) ;
//		return true ;
//	}
//	return false ;
//}
332

333
void Map2::sewFaces(Dart d, Dart e, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
334
{
335
336
337
	// if sewing with fixed points
	if (!withBoundary)
	{
338
339
340
		assert(phi2(d) == d && phi2(e) == e) ;
		phi2sew(d, e) ;
		return ;
341
	}
342

343
	assert(isBoundaryEdge(d) && isBoundaryEdge(e)) ;
344

345
346
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
347

348
349
	phi2unsew(d) ;	// unsew faces from boundary
	phi2unsew(e) ;
350

351
352
353
354
355
	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
356

357
	phi2sew(d, e) ; // sew the faces
Pierre Kraemer's avatar
Pierre Kraemer committed
358
359
360
361
}

void Map2::unsewFaces(Dart d)
{
362
363
	assert(!isBoundaryEdge(d)) ;

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

Pierre Kraemer's avatar
Pierre Kraemer committed
366
	Dart e = newBoundaryCycle(2) ;
367
	Dart ee = phi1(e) ;
Sylvain Thery's avatar
Sylvain Thery committed
368

Pierre Kraemer's avatar
Pierre Kraemer committed
369
	Dart f = findBoundaryEdgeOfVertex(d) ;
370
371
	Dart ff = findBoundaryEdgeOfVertex(dd) ;

untereiner's avatar
untereiner committed
372
	if(f != NIL)
Pierre Kraemer's avatar
Pierre Kraemer committed
373
		phi1sew(e, phi_1(f)) ;
Sylvain Thery's avatar
Sylvain Thery committed
374

375
376
	if(ff != NIL)
		phi1sew(ee, phi_1(ff)) ;
Sylvain Thery's avatar
Sylvain Thery committed
377

Pierre Kraemer's avatar
Pierre Kraemer committed
378
	phi2unsew(d) ;
379

Pierre Kraemer's avatar
Pierre Kraemer committed
380
381
	phi2sew(d, e) ;		// sew faces
	phi2sew(dd, ee) ;	// to the boundary
Pierre Kraemer's avatar
Pierre Kraemer committed
382
383
384
385
}

bool Map2::collapseDegeneratedFace(Dart d)
{
386
	Dart e = phi1(d) ;				// Check if the face is degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
387
388
	if (phi1(e) == d)				// Yes: it contains one or two edge(s)
	{
389
390
391
392
393
394
395
396
397
398
399
400
401
402
		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
403
404
405
406
407
408
409
		return true ;
	}
	return false ;
}

void Map2::splitFace(Dart d, Dart e)
{
410
	assert(d != e && sameFace(d, e)) ;
411
412
413
414
	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
415
416
417
418
}

bool Map2::mergeFaces(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
419
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
420
	{
Sylvain Thery's avatar
Sylvain Thery committed
421
		Dart e = phi2(d) ;
422
		phi2unsew(d) ;
423
		Map1::mergeCycles(d, phi1(e)) ;
424
		Map1::splitCycle(e, phi1(d)) ;
425
		Map1::deleteCycle(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
426
427
428
429
430
431
432
433
		return true ;
	}
	return false ;
}

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

435
436
437
	assert(!isBoundaryFace(d) && !isBoundaryFace(e)) ;
	assert(faceDegree(d) == 3 && faceDegree(e) == 3) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
438
439
440
441
442
	Dart d1 = phi2(phi1(d)) ;
	Dart d2 = phi2(phi_1(d)) ;
	phi2unsew(d1) ;
	phi2unsew(d2) ;
	phi2sew(d1, d2) ;
443
444
445
446
447
448

	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
449
450
451
452
453
}

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

455
456
	assert(v1 != v2 && sameOrientedVertex(v1, v2)) ;
	assert(faceDegree(d) == 3 && faceDegree(phi2(d)) == 3) ;
Sylvain Thery's avatar
Sylvain Thery committed
457

Pierre Kraemer's avatar
Pierre Kraemer committed
458
459
460
461
	Dart vv1 = phi2(v1) ;
	phi2unsew(v1) ;
	phi2sew(phi_1(d), v1) ;
	phi2sew(phi1(d), vv1) ;
462
463
464
465
466

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

469
470
void Map2::unsewAroundVertex(Dart d)
{
471
	Dart it = d ;
472
473
	do
	{
474
475
		Dart temp = phi1(it) ;
		Dart e_1 = phi_1(it) ;
476
477
478

		do
		{
479
480
481
			unsewFaces(temp) ;
			temp = phi1(temp) ;
		} while(temp != e_1);
482

483
		it = alpha1(it);
484
	}
485
	while(it != d);
486
487
}

Pierre Kraemer's avatar
Pierre Kraemer committed
488
489
bool Map2::mergeVolumes(Dart d, Dart e)
{
490
	assert(!isBoundaryMarked(d) && !isBoundaryMarked(e)) ;
Sylvain Thery's avatar
Sylvain Thery committed
491

untereiner's avatar
untereiner committed
492
	if (Map2::isBoundaryFace(d) || Map2::isBoundaryFace(e))
Sylvain Thery's avatar
Sylvain Thery committed
493
494
		return false;

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

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

	return true ;
}

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

bool Map2::sameOrientedVertex(Dart d, Dart e)
{
543
	Dart it = d;				// Foreach dart dNext in the vertex of d
Pierre Kraemer's avatar
Pierre Kraemer committed
544
545
	do
	{
546
		if (it == e)			// Test equality with e
Pierre Kraemer's avatar
Pierre Kraemer committed
547
			return true;
548
549
		it = alpha1(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
550
551
552
	return false;				// None is equal to e => vertices are distinct
}

553
554
555
unsigned int Map2::vertexDegree(Dart d)
{
	unsigned int count = 0 ;
556
	Dart it = d ;
557
558
559
	do
	{
		++count ;
560
561
		it = alpha1(it) ;
	} while (it != d) ;
562
563
564
	return count ;
}

565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
bool Map2::isBoundaryVertex(Dart d)
{
	Dart it = d ;
	do
	{
		if (isBoundaryMarked(it))
			return true ;
		it = alpha1(it) ;
	} while (it != d) ;
	return false ;
}

Dart Map2::findBoundaryEdgeOfVertex(Dart d)
{
	Dart it = d ;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha1(it) ;
	} while (it != d) ;
	return NIL ;
}

bool Map2::isBoundaryFace(Dart d)
{
	Dart it = d ;
	do
	{
		if (isBoundaryMarked(phi2(it)))
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

601
bool Map2::sameOrientedVolume(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
602
{
603
604
605
606
607
608
609
	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
610
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Pierre Kraemer's avatar
Pierre Kraemer committed
611
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
612
		if (!isBoundaryMarked(*face) && !mark.isMarked(*face))		// Face has not been visited yet
613
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
614
			Dart it = *face ;
615
616
			do
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
617
				if(it == e)
618
619
					return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
620
621
622
				mark.mark(it);						// Mark
				Dart adj = phi2(it);				// Get adjacent face
				if (!isBoundaryMarked(adj) && !mark.isMarked(adj))
623
					visitedFaces.push_back(adj);	// Add it
Pierre Kraemer's avatar
Pierre Kraemer committed
624
625
				it = phi1(it);
			} while(it != *face);
626
627
628
		}
	}
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
629
630
631
632
633
634
635
636
637
638
639
640
641
}

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
642
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
643
	{
Sylvain Thery's avatar
Sylvain Thery committed
644
645
		Dart df = visitedFaces[i];
		if (!isBoundaryMarked(df) && !mark.isMarked(df))		// Face has not been visited yet
Pierre Kraemer's avatar
Pierre Kraemer committed
646
647
		{
			++count;
648
			Dart it = df ;
Pierre Kraemer's avatar
Pierre Kraemer committed
649
650
			do
			{
651
652
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
Sylvain Thery's avatar
Sylvain Thery committed
653
				if ( !isBoundaryMarked(adj) && !mark.isMarked(adj) )
654
655
656
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
Pierre Kraemer's avatar
Pierre Kraemer committed
657
658
659
660
661
662
663
664
		}
	}

	return count;
}

bool Map2::isTriangular()
{
665
666
	TraversorF<Map2> t(*this) ;
	for(Dart d = t.begin(); d != t.end(); d = t.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
667
	{
668
669
		if(faceDegree(d) != 3)
			return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
670
671
672
673
674
675
	}
	return true ;
}

bool Map2::check()
{
676
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
677
	DartMarker m(*this);
Pierre Kraemer's avatar
Pierre Kraemer committed
678
	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
679
680
681
682
	{
		Dart d2 = phi2(d);
		if (phi2(d2) != d)	// phi2 involution ?
		{
683
			CGoGNout << "Check: phi2 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
684
685
			return false;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
686
687
688
689
690
		if(d2 == d)
		{
			CGoGNout << "Check: phi2 fixed point" << CGoGNendl;
			return false;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
691
692
693
694

		Dart d1 = phi1(d);
		if (phi_1(d1) != d)	// phi1 a une image correcte ?
		{
695
			CGoGNout << "Check: inconsistent phi_1 link" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
696
697
698
699
700
			return false;
		}

		if (m.isMarked(d1))	// phi1 a un seul antécédent ?
		{
701
			CGoGNout << "Check: dart with two phi1 predecessors" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
702
703
704
705
706
			return false;
		}
		m.mark(d1);

		if (d1 == d)
707
			CGoGNout << "Check: (warning) face loop (one edge)" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
708
		if (phi1(d1) == d)
709
			CGoGNout << "Check: (warning) face with only two edges" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
710
		if (phi2(d1) == d)
711
			CGoGNout << "Check: (warning) dangling edge" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
712
	}
713

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
	{
		if (!m.isMarked(d))	// phi1 a au moins un antécédent ?
		{
718
			CGoGNout << "Check: dart with no phi1 predecessor" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
719
720
721
			return false;
		}
	}
722

723
	CGoGNout << "Check: topology ok" << CGoGNendl;
724

Pierre Kraemer's avatar
Pierre Kraemer committed
725
726
727
	return true;
}

untereiner's avatar
untereiner committed
728
729
bool Map2::checkSimpleOrientedPath(std::vector<Dart>& vd)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
730
	DartMarkerStore dm(*this) ;
untereiner's avatar
untereiner committed
731
732
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
733
734
735
736
		if(dm.isMarked(*it))
			return false ;
		dm.markOrbit(VERTEX, *it) ;

untereiner's avatar
untereiner committed
737
738
739
740
741
		std::vector<Dart>::iterator prev ;
		if(it == vd.begin())
			prev = vd.end() - 1 ;
		else
			prev = it - 1 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
742

untereiner's avatar
untereiner committed
743
744
745
746
747
748
		if(!sameVertex(*it, phi1(*prev)))
			return false ;
	}
	return true ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
749
750
751
752
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
753
bool Map2::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
754
755
756
757
758
759
760
761
762
763
764
{
	Dart dNext = d;
	do
	{
		if (f(dNext))
			return true;
		dNext = alpha1(dNext);
 	} while (dNext != d);
 	return false;
}

Sylvain Thery's avatar
Sylvain Thery committed
765
bool Map2::foreach_dart_of_edge(Dart d, FunctorType& fonct, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
766
767
768
{
	if (fonct(d))
		return true;
Sylvain Thery's avatar
Sylvain Thery committed
769
	return fonct(phi2(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
770
771
}

772
bool Map2::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
773
{
untereiner's avatar
untereiner committed
774
	DartMarkerStore mark(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
775
776
	bool found = false;				// Last functor return value

untereiner's avatar
untereiner committed
777
778
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
779
780
781
	visitedFaces.push_back(d);		// Start with the face of d

	// For every face added to the list
782
	for(unsigned int i = 0; !found && i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
783
	{
784
		if (!mark.isMarked(visitedFaces[i]))	// Face has not been visited yet
Pierre Kraemer's avatar
Pierre Kraemer committed
785
786
		{
			// Apply functor to the darts of the face
787
			found = Map2::foreach_dart_of_face(visitedFaces[i], f);
Pierre Kraemer's avatar
Pierre Kraemer committed
788
789
790
791
792

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
793
				Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
794
795
				do
				{
796
797
798
					mark.mark(e);				// Mark
					Dart adj = phi2(e);			// Get adjacent face
					if (!mark.isMarked(adj))
Pierre Kraemer's avatar
Pierre Kraemer committed
799
						visitedFaces.push_back(adj);	// Add it
untereiner's avatar
untereiner committed
800
					e = phi1(e);
801
				} while(e != visitedFaces[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
802
803
804
805
806
807
			}
		}
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
808
/*! @name Close map after import or creation
809
 *  These functions must be used with care, generally only by import/creation algorithms
Pierre Kraemer's avatar
Pierre Kraemer committed
810
811
 *************************************************************************/

812
unsigned int Map2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
{
	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
840
841
	if(forboundary)
		boundaryMarkOrbit(FACE, phi2(d));
842

Pierre Kraemer's avatar
Pierre Kraemer committed
843
844
845
846
847
848
849
850
851
852
853
854
	return countEdges ;
}

void Map2::closeMap()
{
	// Search the map for topological holes (fix points of phi2)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (phi2(d) == d)
			closeHole(d);
	}
}
Pierre Kraemer's avatar
Pierre Kraemer committed
855
856

} // namespace CGoGN