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
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
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
94
95
96
97
/*! @name Generator and Deletor
 *  To generate or delete faces in a 2-map
 *************************************************************************/

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

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

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

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

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

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

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

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

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

void Map2::splitVertex(Dart d, Dart e)
{
David Cazier's avatar
David Cazier committed
187
188
189
190
191
192
	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
193
194
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

bool Map2::flipEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
284
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
285
	{
Sylvain Thery's avatar
Sylvain Thery committed
286
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
		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
302
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
303
	{
Sylvain Thery's avatar
Sylvain Thery committed
304
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
305
306
307
308
309
310
311
312
313
314
315
		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
}

316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
//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 ;
//}
331

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	return true ;
}

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

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

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

564
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
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 ;
}

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

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

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

	return count;
}

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

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

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

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
713
	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
714
715
716
	{
		if (!m.isMarked(d))	// phi1 a au moins un antécédent ?
		{
717
			CGoGNout << "Check: dart with no phi1 predecessor" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
718
719
720
			return false;
		}
	}
721

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

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

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

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

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

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

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

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

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

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

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

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

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

811
unsigned int Map2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
812
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
{
	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
839
840
	if(forboundary)
		boundaryMarkOrbit(FACE, phi2(d));
841

Pierre Kraemer's avatar
Pierre Kraemer committed
842
843
844
845
846
847
848
849
850
851
852
853
	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
854
855

} // namespace CGoGN