map3.cpp 18.2 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(std::vector<Dart>::iterator face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Pierre Kraemer's avatar
Pierre Kraemer committed
45 46 47
	{
		Dart e = *face ;

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 60 61 62
			}
			e = phi1(e) ;
		} while(e != *face) ;
	}

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 ;

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

	//just one dart per face
	std::vector<Dart> fstore;
95
	fstore.reserve(128);
untereiner's avatar
untereiner committed
96 97
	DartMarker mf(*this);
	for(std::vector<Dart>::iterator it = fstoretmp.begin() ; it != fstoretmp.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
98
	{
untereiner's avatar
untereiner committed
99
		if(!mf.isMarked(*it))
100
		{
untereiner's avatar
untereiner committed
101 102 103
			mf.markOrbit(FACE, *it);
			fstore.push_back(*it);
		}
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 117 118 119 120 121 122 123
		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) ;
			if(res == NIL)
				res = d2 ;
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
		}
untereiner's avatar
untereiner committed
124
	}
125
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
126

127
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
128 129 130 131 132 133 134 135
}

void Map3::cutEdge(Dart d)
{
	Dart prev = d;
	Dart dd = alpha2(d);
	Map2::cutEdge(d);

136
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
137 138 139 140 141 142
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

143 144 145 146
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
147 148
	}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
155
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
156
{
Pierre Kraemer's avatar
Pierre Kraemer committed
157 158
	if(vertexDegree(phi1(d)) == 2)
	{
159 160
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
161

162 163
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
164 165 166
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
167

168 169
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
170 171
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
172 173
		} while (dd != d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
174
		return true;
untereiner's avatar
untereiner committed
175
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
176
	return false;
untereiner's avatar
untereiner committed
177 178
}

untereiner's avatar
untereiner committed
179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 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 242 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
Dart Map3::deleteEdge(Dart d)
{
	if(isBoundaryEdge(d))
		return NIL ;

	//Save the darts around the edge
	//(one dart per face should be enough)
	std::vector<Dart> fstore;
	fstore.reserve(128);
	Dart dit = d;
	do
	{
		fstore.push_back(dit);
		dit = alpha2(dit);
	}while(dit != d);


	Dart res = NIL ;
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
		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) ;
			if(res == NIL)
				res = d2 ;
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
		}
	}
	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));
		Map2::collapseEdge(*it,false);

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

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

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

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

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

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

296 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
	// 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) ;
		}
327 328
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
329 330
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
331
	} while(fitD != dd) ;
332 333
	Map2::deleteCC(dd) ;

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

void Map3::unsewVolumes(Dart d)
{
untereiner's avatar
untereiner committed
346 347 348 349 350 351 352 353 354 355 356 357
	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 ;
358 359
	do
	{
untereiner's avatar
untereiner committed
360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379
		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) ;
380 381 382 383
}

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

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

untereiner's avatar
untereiner committed
396 397 398 399 400 401 402
	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
403 404
	Map2::fillHole(e) ;
	Map2::fillHole(e2) ;
untereiner's avatar
untereiner committed
405

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

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

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

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

untereiner's avatar
untereiner committed
423
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
424
	{
untereiner's avatar
untereiner committed
425
		if(*it == e)
426 427 428
			return true;

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

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

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

untereiner's avatar
untereiner committed
452 453 454
	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
455 456
	mv.mark(d);

untereiner's avatar
untereiner committed
457
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
458 459
	{
		//add phi21 and phi23 successor if they are not marked yet
untereiner's avatar
untereiner committed
460
		Dart d2 = phi2(*it);
untereiner's avatar
untereiner committed
461 462 463 464 465
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

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

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

	return count;
}

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

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

untereiner's avatar
untereiner committed
498
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
499
	{
untereiner's avatar
untereiner committed
500 501
		if(isBoundaryMarked(*it))
			return true ;
502 503

		//add phi21 and phi23 successor if they are not marked yet
untereiner's avatar
untereiner committed
504
		Dart d2 = phi2(*it);
505 506 507 508 509
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

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

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

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

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

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

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

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

untereiner's avatar
untereiner committed
579
	for(std::vector<Dart>::iterator it = visitedFaces.begin(); it != visitedFaces.end(); ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
580
	{
untereiner's avatar
untereiner committed
581 582
		if (isBoundaryMarked(phi3(*it)))
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
583

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

599
bool Map3::check()
600
{
601 602 603 604 605 606 607 608 609 610
    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;
        }
611

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

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

625 626 627 628 629 630
        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;
        }
631

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

639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654
        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 ?
655
		{
656 657 658 659
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
660

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

663 664 665
    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
666 667 668 669 670 671 672 673 674
    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 ;

675
    return true;
676 677
}

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

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

untereiner's avatar
untereiner committed
687 688 689
	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
690 691
	mv.mark(d);

untereiner's avatar
untereiner committed
692
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
693
	{
694
		// add phi21 and phi23 successor if they are not marked yet
untereiner's avatar
untereiner committed
695 696 697
		Dart d2 = phi2(*it);
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
698

untereiner's avatar
untereiner committed
699 700 701 702 703 704 705 706 707
		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
708 709
		}

untereiner's avatar
untereiner committed
710
		found = f(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
711 712 713 714
	}
	return found;
}

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

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

untereiner's avatar
untereiner committed
732 733 734
	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
735 736
	mv.mark(d);

untereiner's avatar
untereiner committed
737
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
738
	{
untereiner's avatar
untereiner committed
739
		Dart d1 = *it;
Pierre Kraemer's avatar
Pierre Kraemer committed
740

untereiner's avatar
untereiner committed
741 742
		// add all successors if they are not marked yet
		Dart d2 = phi1(d1); // turn in face
Pierre Kraemer's avatar
Pierre Kraemer committed
743 744 745
		Dart d3 = phi2(d1); // change face
		Dart d4 = phi3(d1); // change volume

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

		found = f(d1);
	}
	return found;
}

untereiner's avatar
untereiner committed
767 768 769
/*! @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
770

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

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

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

untereiner's avatar
untereiner committed
783 784
	// For every face added to the list
	for (std::vector<Dart>::iterator it = visitedFaces.begin(); it != visitedFaces.end(); ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
785
	{
untereiner's avatar
untereiner committed
786 787 788 789
		Dart f = *it ;
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
790

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

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

untereiner's avatar
untereiner committed
822 823 824 825 826 827 828 829 830 831 832
	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
833 834 835
}

} // namespace CGoGN