map3.cpp 17.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-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 26 27 28 29 30 31 32
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/map/map3.h"

namespace CGoGN
{

/*! @name Generator and Deletor
 *  To generate or delete volumes in a 3-map
 *************************************************************************/
33 34

void Map3::deleteVolume(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
35 36 37 38
{
	DartMarkerStore mark(*this);		// Lock a marker

	std::vector<Dart> visitedFaces;		// Faces that are traversed
39
	visitedFaces.reserve(512);
Pierre Kraemer's avatar
Pierre Kraemer committed
40 41
	visitedFaces.push_back(d);			// Start with the face of d

42
	mark.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
43

44
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
45
	{
46
		Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
47

48 49
		if(!isBoundaryFace(e))
			unsewVolumes(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
50 51 52 53 54 55 56

		do	// add all face neighbours to the table
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
57
				mark.markOrbit(ORIENTED_FACE, ee) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
58 59
			}
			e = phi1(e) ;
60
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
61 62
	}

untereiner's avatar
untereiner committed
63 64 65
	Dart dd = phi3(d) ;
	Map2::deleteCC(d) ;
	Map2::deleteCC(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
66 67
}

68 69
void Map3::fillHole(Dart d)
{
70 71 72 73 74
	assert(isBoundaryFace(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi3(dd) ;
	boundaryUnmarkOrbit(VOLUME, dd) ;
75 76
}

Pierre Kraemer's avatar
Pierre Kraemer committed
77 78 79 80
/*! @name Topological Operators
 *  Topological operations on 3-maps
 *************************************************************************/

81
Dart Map3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
82
{
83 84 85
	if(isBoundaryVertex(d))
		return NIL ;

Pierre Kraemer's avatar
Pierre Kraemer committed
86 87
	// Save the darts around the vertex
	// (one dart per face should be enough)
untereiner's avatar
untereiner committed
88
	std::vector<Dart> fstoretmp;
89
	fstoretmp.reserve(128);
untereiner's avatar
untereiner committed
90 91 92
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

Pierre Kraemer's avatar
Pierre Kraemer committed
93
	// just one dart per face
untereiner's avatar
untereiner committed
94
	std::vector<Dart> fstore;
95
	fstore.reserve(128);
untereiner's avatar
untereiner committed
96
	DartMarker mf(*this);
97
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
98
	{
99
		if(!mf.isMarked(fstoretmp[i]))
100
		{
101 102
			mf.markOrbit(FACE, fstoretmp[i]);
			fstore.push_back(fstoretmp[i]);
untereiner's avatar
untereiner committed
103
		}
104
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
105

106
	Dart res = NIL ;
untereiner's avatar
untereiner committed
107 108
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
109 110 111 112 113 114 115 116
		Dart fit = *it ;
		Dart end = phi_1(fit) ;
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
117

118 119
			if(res == NIL)
				res = d2 ;
120

121 122 123 124
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
125 126

			fit = phi1(fit) ;
127
		}
untereiner's avatar
untereiner committed
128
	}
129

130
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
131

132
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
133 134
}

David Cazier's avatar
David Cazier committed
135
Dart Map3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
136 137 138
{
	Dart prev = d;
	Dart dd = alpha2(d);
David Cazier's avatar
David Cazier committed
139
	Dart nd = Map2::cutEdge(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
140

141
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
142 143 144 145 146 147
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

148 149 150 151
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
152 153
	}

154 155 156 157
	Dart d3 = phi3(d);
	phi3unsew(d);
	phi3sew(d, phi1(d3));
	phi3sew(d3, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
158

David Cazier's avatar
David Cazier committed
159
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
160 161
}

Pierre Kraemer's avatar
Pierre Kraemer committed
162
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
163
{
Pierre Kraemer's avatar
Pierre Kraemer committed
164 165
	if(vertexDegree(phi1(d)) == 2)
	{
166 167
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
168

169 170
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
171 172 173
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
174

175 176
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
177 178
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
179 180
		} while (dd != d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
181
		return true;
untereiner's avatar
untereiner committed
182
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
183
	return false;
untereiner's avatar
untereiner committed
184 185
}

untereiner's avatar
untereiner committed
186 187 188 189 190 191
Dart Map3::deleteEdge(Dart d)
{
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
192 193
	Dart dit = d ;
	do
untereiner's avatar
untereiner committed
194
	{
195 196
		Dart fit = dit ;
		Dart end = fit ;
untereiner's avatar
untereiner committed
197 198 199 200 201 202
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
203

untereiner's avatar
untereiner committed
204 205
			if(res == NIL)
				res = d2 ;
206

untereiner's avatar
untereiner committed
207 208 209 210
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
211 212

			fit = phi1(fit) ;
untereiner's avatar
untereiner committed
213
		}
214 215 216
		dit = alpha2(dit) ;
	} while(dit != d) ;

untereiner's avatar
untereiner committed
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241
	Map2::deleteCC(d) ;

	return res ;
}

Dart Map3::collapseEdge(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;

	Dart e = d;

	//stocke un brin par volume autour de l'arete
	std::vector<Dart> tmp;
	tmp.reserve(32);
	do
	{
		tmp.push_back(e);
		e = alpha2(e);
	} while (e != d);

	//contraction de la 2 carte de chaque 2-arete
	for (std::vector<Dart>::iterator it = tmp.begin(); it != tmp.end(); ++it)
	{
		//un brin d'une face adjacente a l'arrete contracte
		Dart d = phi2(phi_1(*it));
242
		Map2::collapseEdge(*it, false);
untereiner's avatar
untereiner committed
243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278

		//test de la degeneresence
		//impossible d'avoir un volume de moins de 4 faces sans avoir de phi2 en points fixe donc on les vire
		if(delDegenerateVolumes && Map2::volumeDegree(d) < 4)
		{
			Dart e = d;
			//pour tous les brins de la face adjacente

			do
			{
				Dart ee = phi3(e);
				Dart ff = phi3(phi2(e));

				//si les brins ont un voisin par phi3
				if(ee != e)
					phi3unsew(ee);

				if(ff != phi2(e))
					phi3unsew(ff);

				//si les deux en ont un, il faut les coudres ensemble
				if(ee != e && ff != phi2(e))
					phi3sew(ee, ff);

				//on peut supprimer les brins de cette arete
				deleteDart(e);
				deleteDart(phi2(e));
				e = phi1(e);

			} while (e != d);
		}
	}

	return resV;
}

279
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
280
{
281
	assert(d != e && Map2::sameOrientedFace(d, e)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
282

283 284
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
285

untereiner's avatar
untereiner committed
286
	Map2::splitFace(d, e);
287
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
288

289 290
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
291 292
}

293
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
294 295 296
{
	assert(faceDegree(d) == faceDegree(e));

297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327
	// if sewing with fixed points
	if (!withBoundary)
	{
		assert(phi3(d) == d && phi3(e) == e) ;
		Dart fitD = d ;
		Dart fitE = e ;
		do
		{
			phi3sew(fitD, fitE) ;
			fitD = phi1(fitD) ;
			fitE = phi_1(fitE) ;
		} while(fitD != d) ;
		return ;
	}

	Dart dd = phi3(d) ;
	Dart ee = phi3(e) ;

	Dart fitD = dd ;
	Dart fitE = ee ;
	do
	{
		Dart fitD2 = phi2(fitD) ;
		Dart fitE2 = phi2(fitE) ;
		if(fitD2 != fitE)
		{
			phi2unsew(fitD) ;
			phi2unsew(fitE) ;
			phi2sew(fitD2, fitE2) ;
			phi2sew(fitD, fitE) ;
		}
328 329
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
330 331
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
332
	} while(fitD != dd) ;
333 334
	Map2::deleteCC(dd) ;

335 336
	fitD = d ;
	fitE = e ;
337 338
	do
	{
339
		phi3sew(fitD, fitE) ;
340 341 342 343 344 345 346
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void Map3::unsewVolumes(Dart d)
{
untereiner's avatar
untereiner committed
347 348 349 350 351 352 353 354 355 356 357 358
	assert(!isBoundaryFace(d)) ;

	unsigned int nbE = faceDegree(d) ;
	Dart d3 = phi3(d);

	Dart b1 = newBoundaryCycle(nbE) ;
	Dart b2 = newBoundaryCycle(nbE) ;

	Dart fit1 = d ;
	Dart fit2 = d3 ;
	Dart fitB1 = b1 ;
	Dart fitB2 = b2 ;
359 360
	do
	{
untereiner's avatar
untereiner committed
361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380
		Dart f = findBoundaryFaceOfEdge(fit1) ;
		if(f != NIL)
		{
			Dart f2 = phi2(f) ;
			phi2unsew(f) ;
			phi2sew(fitB1, f) ;
			phi2sew(fitB2, f2) ;
		}
		else
			phi2sew(fitB1, fitB2) ;

		phi3unsew(fit1) ;
		phi3sew(fit1, fitB1) ;
		phi3sew(fit2, fitB2) ;

		fit1 = phi1(fit1) ;
		fit2 = phi_1(fit2) ;
		fitB1 = phi_1(fitB1) ;
		fitB2 = phi1(fitB2) ;
	} while(fitB1 != b1) ;
381 382 383 384
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
385
	if(!Map3::isBoundaryFace(d))
386
	{
untereiner's avatar
untereiner committed
387
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
388 389 390 391 392
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
393 394
void Map3::splitVolume(std::vector<Dart>& vd)
{
untereiner's avatar
untereiner committed
395 396
	assert(checkSimpleOrientedPath(vd)) ;

untereiner's avatar
untereiner committed
397 398 399 400 401 402 403
	Dart e = vd.front();
	Dart e2 = phi2(e);

	//unsew the edge path
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
		Map2::unsewFaces(*it);

untereiner's avatar
untereiner committed
404 405
	Map2::fillHole(e) ;
	Map2::fillHole(e2) ;
untereiner's avatar
untereiner committed
406

untereiner's avatar
untereiner committed
407 408
	//sew the two connected components
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
409 410
}

411 412 413 414
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

415
bool Map3::sameVertex(Dart d, Dart e)
416 417 418
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
419 420 421
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
422 423
	mv.mark(d);

424
	for(unsigned int i = 0; i < darts.size(); ++i)
425
	{
426
		if(darts[i] == e)
427 428
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
429
		// add phi21 and phi23 successor if they are not marked yet
430
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
431 432
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
433

untereiner's avatar
untereiner committed
434 435 436 437 438 439 440 441 442
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
443 444 445 446 447
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
448 449
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
450
	unsigned int count = 0;
untereiner's avatar
untereiner committed
451 452
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
453 454 455
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
untereiner's avatar
untereiner committed
456 457
	mv.mark(d);

458
	for(unsigned int i = 0; i < darts.size(); ++i)
untereiner's avatar
untereiner committed
459 460
	{
		//add phi21 and phi23 successor if they are not marked yet
461
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
462 463 464 465 466
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
467
			darts.push_back(d21);
untereiner's avatar
untereiner committed
468 469
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
470
		if(!mv.isMarked(d23))
untereiner's avatar
untereiner committed
471
		{
untereiner's avatar
untereiner committed
472
			darts.push_back(d23);
untereiner's avatar
untereiner committed
473 474 475 476 477
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
untereiner's avatar
untereiner committed
478
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
479
	{
untereiner's avatar
untereiner committed
480
		if(!me.isMarked(*it))
untereiner's avatar
untereiner committed
481 482
		{
			++count;
untereiner's avatar
untereiner committed
483
			me.markOrbit(EDGE, *it);
untereiner's avatar
untereiner committed
484 485 486 487 488 489
		}
	}

	return count;
}

490 491
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
492
	DartMarkerStore mv(*this);	// Lock a marker
493

untereiner's avatar
untereiner committed
494 495 496
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
497 498
	mv.mark(d);

499
	for(unsigned int i = 0; i < darts.size(); ++i)
500
	{
501
		if(isBoundaryMarked(darts[i]))
untereiner's avatar
untereiner committed
502
			return true ;
503 504

		//add phi21 and phi23 successor if they are not marked yet
505
		Dart d2 = phi2(darts[i]);
506 507 508 509 510
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
511
			darts.push_back(d21);
512 513
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
514
		if(!mv.isMarked(d23))
515
		{
untereiner's avatar
untereiner committed
516
			darts.push_back(d23);
517 518 519
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
520
	return false ;
521 522 523 524
}

bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
525
	Dart it = d;
526 527
	do
	{
untereiner's avatar
untereiner committed
528
		if(it == e)
529
			return true;
untereiner's avatar
untereiner committed
530 531
		it = alpha2(it);
	} while (it != d);
532 533 534
	return false;
}

untereiner's avatar
untereiner committed
535
unsigned int Map3::edgeDegree(Dart d)
536
{
untereiner's avatar
untereiner committed
537
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
538
	Dart it = d;
539 540
	do
	{
untereiner's avatar
untereiner committed
541 542 543
		++deg;
		it = alpha2(it);
	} while(it != d);
544 545 546
	return deg;
}

untereiner's avatar
untereiner committed
547
bool Map3::isBoundaryEdge(Dart d)
548
{
untereiner's avatar
untereiner committed
549 550 551 552 553 554 555 556
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
557 558
}

untereiner's avatar
untereiner committed
559
Dart Map3::findBoundaryFaceOfEdge(Dart d)
560
{
untereiner's avatar
untereiner committed
561 562 563 564 565 566 567 568
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
569 570
}

Pierre Kraemer's avatar
Pierre Kraemer committed
571 572
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
573
	DartMarkerStore mark(*this);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
574 575

	std::vector<Dart> visitedFaces ;
untereiner's avatar
untereiner committed
576
	visitedFaces.reserve(128) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
577
	visitedFaces.push_back(d) ;
untereiner's avatar
untereiner committed
578
	mark.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
579

580
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
581
	{
582
		if (isBoundaryMarked(phi3(visitedFaces[i])))
untereiner's avatar
untereiner committed
583
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
584

585
		Dart e = visitedFaces[i] ;
untereiner's avatar
untereiner committed
586
		do	// add all face neighbours to the table
Pierre Kraemer's avatar
Pierre Kraemer committed
587
		{
untereiner's avatar
untereiner committed
588 589
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
Pierre Kraemer's avatar
Pierre Kraemer committed
590
			{
untereiner's avatar
untereiner committed
591 592 593 594
				visitedFaces.push_back(ee) ;
				mark.markOrbit(ORIENTED_FACE, ee) ;
			}
			e = phi1(e) ;
595
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
596
	}
untereiner's avatar
untereiner committed
597
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
598 599
}

600
bool Map3::check()
601
{
602 603 604 605 606 607 608 609 610 611
    std::cout << "Check: topology begin" << std::endl;
    DartMarker m(*this);
    for(Dart d = Map3::begin(); d != Map3::end(); Map3::next(d))
    {
        Dart d3 = phi3(d);
        if (phi3(d3) != d) // phi3 involution ?
		{
            std::cout << "Check: phi3 is not an involution" << std::endl;
            return false;
        }
612

untereiner's avatar
untereiner committed
613 614 615 616 617
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
			return false;
		}
618

619 620 621 622 623 624
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
625

626 627 628 629 630 631
        Dart d1 = phi1(d);
        if (phi_1(d1) != d) // phi1 a une image correcte ?
		{
            std::cout << "Check: unconsistent phi_1 link" << std::endl;
            return false;
        }
632

633
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
634
		{
635 636 637 638
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
639

640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655
        if (d1 == d)
            std::cout << "Check: (warning) face loop (one edge)" << std::endl;

        if (phi1(d1) == d)
            std::cout << "Check: (warning) face with only two edges" << std::endl;

        if (phi2(d1) == d)
            std::cout << "Check: (warning) dandling edge (phi2)" << std::endl;

        if (phi3(d1) == d)
            std::cout << "Check: (warning) dandling edge (phi3)" << std::endl;
    }

    for(Dart d = this->begin(); d != this->end(); this->next(d))
    {
        if (!m.isMarked(d)) // phi1 a au moins un antécédent ?
656
		{
657 658 659 660
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
661

662
    std::cout << "Check: topology ok" << std::endl;
663

664 665 666
    std::cout << "nb vertex orbits" << getNbOrbits(VERTEX) << std::endl ;
    std::cout << "nb vertex cells" << m_attribs[VERTEX].size() << std::endl ;

untereiner's avatar
untereiner committed
667 668 669 670 671 672 673 674 675
    std::cout << "nb edge orbits" << getNbOrbits(EDGE) << std::endl ;
    std::cout << "nb edge cells" << m_attribs[EDGE].size() << std::endl ;

    std::cout << "nb face orbits" << getNbOrbits(FACE) << std::endl ;
    std::cout << "nb face cells" << m_attribs[FACE].size() << std::endl ;

    std::cout << "nb volume orbits" << getNbOrbits(VOLUME) << std::endl ;
    std::cout << "nb volume cells" << m_attribs[VOLUME].size() << std::endl ;

676
    return true;
677 678
}

Pierre Kraemer's avatar
Pierre Kraemer committed
679 680 681 682
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
683
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
684
{
untereiner's avatar
untereiner committed
685
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
686 687
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
688 689 690
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
Pierre Kraemer's avatar
Pierre Kraemer committed
691 692
	mv.mark(d);

693
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
694
	{
695
		// add phi21 and phi23 successor if they are not marked yet
696
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
697 698
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
699

untereiner's avatar
untereiner committed
700 701 702 703 704 705 706 707 708
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
Pierre Kraemer's avatar
Pierre Kraemer committed
709 710
		}

711
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
712 713 714 715
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
716
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
717
{
untereiner's avatar
untereiner committed
718
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
719 720
	do
	{
untereiner's avatar
untereiner committed
721
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
722
			return true;
untereiner's avatar
untereiner committed
723 724
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
725 726 727
	return false;
}

untereiner's avatar
untereiner committed
728
bool Map3::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
729
{
Sylvain Thery's avatar
Sylvain Thery committed
730
	DartMarkerStore mv(*this,thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
731 732
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
733 734 735
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(1024);
	darts.push_back(d);			// Start with the dart d
Pierre Kraemer's avatar
Pierre Kraemer committed
736 737
	mv.mark(d);

738
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
739
	{
untereiner's avatar
untereiner committed
740
		// add all successors if they are not marked yet
741 742 743
		Dart d2 = phi1(darts[i]); // turn in face
		Dart d3 = phi2(darts[i]); // change face
		Dart d4 = phi3(darts[i]); // change volume
Pierre Kraemer's avatar
Pierre Kraemer committed
744

untereiner's avatar
untereiner committed
745 746 747 748 749
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
750 751
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
752 753
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
754 755 756
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
757
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
758 759 760
			mv.mark(d4);
		}

761
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
762 763 764 765
	}
	return found;
}

untereiner's avatar
untereiner committed
766 767 768
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
769

untereiner's avatar
untereiner committed
770
unsigned int Map3::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
771
{
untereiner's avatar
untereiner committed
772
	assert(phi3(d) == d);		// Nothing to close
773
	DartMarkerStore m(*this) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
774

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

untereiner's avatar
untereiner committed
780
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
781

untereiner's avatar
untereiner committed
782
	// For every face added to the list
783
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
784
	{
785 786 787
		Dart it = visitedFaces[i] ;
		Dart f = it ;

untereiner's avatar
untereiner committed
788 789 790
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
791

untereiner's avatar
untereiner committed
792 793
		Dart bit = b ;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
794
		{
untereiner's avatar
untereiner committed
795 796 797 798 799 800 801
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
				if(phi3(e) == e)
				{
					found = true ;
802 803 804 805 806
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
						m.markOrbit(ORIENTED_FACE, e) ;
					}
untereiner's avatar
untereiner committed
807
				}
808
				else if(isBoundaryMarked(e))
untereiner's avatar
untereiner committed
809 810
				{
					found = true ;
811
					phi2sew(e, bit) ;
untereiner's avatar
untereiner committed
812 813 814 815 816 817 818 819
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
820
		} while(f != it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
821 822
	}

untereiner's avatar
untereiner committed
823 824 825 826 827 828 829 830 831 832 833
	return count ;
}

void Map3::closeMap()
{
	// Search the map for topological holes (fix points of phi3)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (phi3(d) == d)
			closeHole(d);
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
834 835 836
}

} // namespace CGoGN