map3.cpp 18.1 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
	Map2::deleteCC(d) ;

	return res ;
}

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

226
	Dart dit = d;
untereiner's avatar
untereiner committed
227 228 229

	do
	{
230 231
		Dart e = dit;
		dit = alpha2(dit);
untereiner's avatar
untereiner committed
232

233 234 235
		//test si un seul polyedre autour de l'arete
		if(e == dit)
			resV == phi3(phi2(phi1(e)));
untereiner's avatar
untereiner committed
236

237
		if(delDegenerateVolumes)
untereiner's avatar
untereiner committed
238
		{
239 240 241 242 243
			Map2::collapseEdge(e, true);
			//collapseDegeneretedVolume(e);
		}
		else
			Map2::collapseEdge(e, false);
untereiner's avatar
untereiner committed
244

245 246
		if(resV == NIL)
		{
untereiner's avatar
untereiner committed
247

248
		}
untereiner's avatar
untereiner committed
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 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305
	}while(d != dit);





//	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, true);
//
//		// 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);
//		}
//	}
untereiner's avatar
untereiner committed
306 307 308 309

	return resV;
}

310
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
311
{
312
	assert(d != e && Map2::sameOrientedFace(d, e)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
313

314 315
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
316

untereiner's avatar
untereiner committed
317
	Map2::splitFace(d, e);
318
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
319

320 321
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
322 323
}

324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345
bool Map3::collapseDegeneretedVolume(Dart d)
{
	Dart e1 = phi2(d);
	Dart e2 = phi2(phi1(d));

	//Si l'une des faces est du bord
	if(isBoundaryFace(e1) || isBoundaryFace(e2))
	{
		//alors simple suppression du volume degenere
	}
	else
	{
		Dart e13 = e1;
		Dart e23 = e2;
		if(!isBoundaryFace(e1))
			e13 = phi3(e1);

		if(!isBoundaryFace(e2))
			e23 = phi3(e2);

		//if(faceDegree(e1) < faceDegree)
	}
346 347

	return false;
348 349
}

350
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
351 352 353
{
	assert(faceDegree(d) == faceDegree(e));

354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384
	// 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) ;
		}
385 386
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
387 388
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
389
	} while(fitD != dd) ;
390 391
	Map2::deleteCC(dd) ;

392 393
	fitD = d ;
	fitE = e ;
394 395
	do
	{
396
		phi3sew(fitD, fitE) ;
397 398 399 400 401 402 403
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void Map3::unsewVolumes(Dart d)
{
untereiner's avatar
untereiner committed
404 405 406 407 408 409 410 411 412 413 414 415
	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 ;
416 417
	do
	{
untereiner's avatar
untereiner committed
418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437
		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) ;
438 439 440 441
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
442
	if(!Map3::isBoundaryFace(d))
443
	{
untereiner's avatar
untereiner committed
444
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
445 446 447 448 449
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
450 451
void Map3::splitVolume(std::vector<Dart>& vd)
{
untereiner's avatar
untereiner committed
452 453
	assert(checkSimpleOrientedPath(vd)) ;

untereiner's avatar
untereiner committed
454 455 456 457 458 459 460
	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
461 462
	Map2::fillHole(e) ;
	Map2::fillHole(e2) ;
untereiner's avatar
untereiner committed
463

untereiner's avatar
untereiner committed
464 465
	//sew the two connected components
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
466 467
}

468 469 470 471
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

472
bool Map3::sameVertex(Dart d, Dart e)
473 474 475
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
476 477 478
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
479 480
	mv.mark(d);

481
	for(unsigned int i = 0; i < darts.size(); ++i)
482
	{
483
		if(darts[i] == e)
484 485
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
486
		// add phi21 and phi23 successor if they are not marked yet
487
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
488 489
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
490

untereiner's avatar
untereiner committed
491 492 493 494 495 496 497 498 499
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
500 501 502 503 504
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
505 506
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
507
	unsigned int count = 0;
untereiner's avatar
untereiner committed
508 509
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
510 511 512
	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
513 514
	mv.mark(d);

515
	for(unsigned int i = 0; i < darts.size(); ++i)
untereiner's avatar
untereiner committed
516 517
	{
		//add phi21 and phi23 successor if they are not marked yet
518
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
519 520 521 522 523
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
524
			darts.push_back(d21);
untereiner's avatar
untereiner committed
525 526
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
527
		if(!mv.isMarked(d23))
untereiner's avatar
untereiner committed
528
		{
untereiner's avatar
untereiner committed
529
			darts.push_back(d23);
untereiner's avatar
untereiner committed
530 531 532 533 534
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
untereiner's avatar
untereiner committed
535
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
536
	{
untereiner's avatar
untereiner committed
537
		if(!me.isMarked(*it))
untereiner's avatar
untereiner committed
538 539
		{
			++count;
untereiner's avatar
untereiner committed
540
			me.markOrbit(EDGE, *it);
untereiner's avatar
untereiner committed
541 542 543 544 545 546
		}
	}

	return count;
}

547 548
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
549
	DartMarkerStore mv(*this);	// Lock a marker
550

untereiner's avatar
untereiner committed
551 552 553
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
554 555
	mv.mark(d);

556
	for(unsigned int i = 0; i < darts.size(); ++i)
557
	{
558
		if(isBoundaryMarked(darts[i]))
untereiner's avatar
untereiner committed
559
			return true ;
560 561

		//add phi21 and phi23 successor if they are not marked yet
562
		Dart d2 = phi2(darts[i]);
563 564 565 566 567
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
568
			darts.push_back(d21);
569 570
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
571
		if(!mv.isMarked(d23))
572
		{
untereiner's avatar
untereiner committed
573
			darts.push_back(d23);
574 575 576
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
577
	return false ;
578 579 580 581
}

bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
582
	Dart it = d;
583 584
	do
	{
untereiner's avatar
untereiner committed
585
		if(it == e)
586
			return true;
untereiner's avatar
untereiner committed
587 588
		it = alpha2(it);
	} while (it != d);
589 590 591
	return false;
}

untereiner's avatar
untereiner committed
592
unsigned int Map3::edgeDegree(Dart d)
593
{
untereiner's avatar
untereiner committed
594
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
595
	Dart it = d;
596 597
	do
	{
untereiner's avatar
untereiner committed
598 599 600
		++deg;
		it = alpha2(it);
	} while(it != d);
601 602 603
	return deg;
}

untereiner's avatar
untereiner committed
604
bool Map3::isBoundaryEdge(Dart d)
605
{
untereiner's avatar
untereiner committed
606 607 608 609 610 611 612 613
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
614 615
}

untereiner's avatar
untereiner committed
616
Dart Map3::findBoundaryFaceOfEdge(Dart d)
617
{
untereiner's avatar
untereiner committed
618 619 620 621 622 623 624 625
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
626 627
}

Pierre Kraemer's avatar
Pierre Kraemer committed
628 629
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
630
	DartMarkerStore mark(*this);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
631 632

	std::vector<Dart> visitedFaces ;
untereiner's avatar
untereiner committed
633
	visitedFaces.reserve(128) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
634
	visitedFaces.push_back(d) ;
untereiner's avatar
untereiner committed
635
	mark.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
636

637
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
638
	{
639
		if (isBoundaryMarked(phi3(visitedFaces[i])))
untereiner's avatar
untereiner committed
640
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
641

642
		Dart e = visitedFaces[i] ;
untereiner's avatar
untereiner committed
643
		do	// add all face neighbours to the table
Pierre Kraemer's avatar
Pierre Kraemer committed
644
		{
untereiner's avatar
untereiner committed
645 646
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
Pierre Kraemer's avatar
Pierre Kraemer committed
647
			{
untereiner's avatar
untereiner committed
648 649 650 651
				visitedFaces.push_back(ee) ;
				mark.markOrbit(ORIENTED_FACE, ee) ;
			}
			e = phi1(e) ;
652
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
653
	}
untereiner's avatar
untereiner committed
654
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
655 656
}

657
bool Map3::check()
658
{
659 660 661 662 663 664 665 666 667 668
    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;
        }
669

untereiner's avatar
untereiner committed
670 671 672 673 674
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
			return false;
		}
675

676 677 678 679 680 681
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
682

683 684 685 686 687 688
        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;
        }
689

690
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
691
		{
692 693 694 695
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
696

697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712
        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 ?
713
		{
714 715 716 717
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
718

719
    std::cout << "Check: topology ok" << std::endl;
720

721
    return true;
722 723
}

Pierre Kraemer's avatar
Pierre Kraemer committed
724 725 726 727
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
728
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
729
{
untereiner's avatar
untereiner 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(256);
	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
	{
740
		// add phi21 and phi23 successor if they are not marked yet
741
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
742 743
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
744

untereiner's avatar
untereiner committed
745 746 747 748 749 750 751 752 753
		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
754 755
		}

756
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
757 758 759 760
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
761
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
762
{
untereiner's avatar
untereiner committed
763
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
764 765
	do
	{
untereiner's avatar
untereiner committed
766
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
767
			return true;
untereiner's avatar
untereiner committed
768 769
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
770 771 772
	return false;
}

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

untereiner's avatar
untereiner committed
778 779 780
	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
781 782
	mv.mark(d);

783
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
784
	{
untereiner's avatar
untereiner committed
785
		// add all successors if they are not marked yet
786 787 788
		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
789

untereiner's avatar
untereiner committed
790 791 792 793 794
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
795 796
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
797 798
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
799 800 801
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
802
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
803 804 805
			mv.mark(d4);
		}

806
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
807 808 809 810
	}
	return found;
}

untereiner's avatar
untereiner committed
811 812 813
/*! @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
814

untereiner's avatar
untereiner committed
815
unsigned int Map3::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
816
{
untereiner's avatar
untereiner committed
817
	assert(phi3(d) == d);		// Nothing to close
818
	DartMarkerStore m(*this) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
819

untereiner's avatar
untereiner committed
820 821 822
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
823
	m.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
824

untereiner's avatar
untereiner committed
825
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
826

untereiner's avatar
untereiner committed
827
	// For every face added to the list
828
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
829
	{
830 831 832
		Dart it = visitedFaces[i] ;
		Dart f = it ;

untereiner's avatar
untereiner committed
833 834 835
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
836

untereiner's avatar
untereiner committed
837 838
		Dart bit = b ;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
839
		{
untereiner's avatar
untereiner committed
840 841 842 843 844 845 846
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
				if(phi3(e) == e)
				{
					found = true ;
847 848 849 850 851
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
						m.markOrbit(ORIENTED_FACE, e) ;
					}
untereiner's avatar
untereiner committed
852
				}
853
				else if(isBoundaryMarked(e))
untereiner's avatar
untereiner committed
854 855
				{
					found = true ;
856
					phi2sew(e, bit) ;
untereiner's avatar
untereiner committed
857 858 859 860 861 862 863 864
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
865
		} while(f != it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
866 867
	}

untereiner's avatar
untereiner committed
868 869 870 871 872 873 874 875 876 877 878
	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
879 880 881
}

} // namespace CGoGN