map3.cpp 18 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 125
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
		}
untereiner's avatar
untereiner committed
126
	}
127
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
128

129
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
130 131
}

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

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

		Map2::cutEdge(prev);

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

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

David Cazier's avatar
David Cazier committed
156
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
157 158
}

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

166 167
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
168 169 170
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
171

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

Pierre Kraemer's avatar
Pierre Kraemer committed
178
		return true;
untereiner's avatar
untereiner committed
179
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
180
	return false;
untereiner's avatar
untereiner committed
181 182
}

untereiner's avatar
untereiner committed
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 278 279 280 281
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;
}

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

286 287
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
288

untereiner's avatar
untereiner committed
289
	Map2::splitFace(d, e);
290
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
291

292 293
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
294 295
}

296
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
297 298 299
{
	assert(faceDegree(d) == faceDegree(e));

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

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

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

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

untereiner's avatar
untereiner committed
396 397
void Map3::splitVolume(std::vector<Dart>& vd)
{
untereiner's avatar
untereiner committed
398 399
	assert(checkSimpleOrientedPath(vd)) ;

untereiner's avatar
untereiner committed
400 401 402 403 404 405 406
	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
407 408
	Map2::fillHole(e) ;
	Map2::fillHole(e2) ;
untereiner's avatar
untereiner committed
409

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

414 415 416 417
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

418
bool Map3::sameVertex(Dart d, Dart e)
419 420 421
{
	DartMarkerStore mv(*this);	// Lock a marker

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

427
	for(unsigned int i = 0; i < darts.size(); ++i)
428
	{
429
		if(darts[i] == e)
430 431
			return true;

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

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

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

untereiner's avatar
untereiner committed
456 457 458
	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
459 460
	mv.mark(d);

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

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

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

	return count;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

603
bool Map3::check()
604
{
605 606 607 608 609 610 611 612 613 614
    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;
        }
615

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

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

629 630 631 632 633 634
        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;
        }
635

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

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

665
    std::cout << "Check: topology ok" << std::endl;
666

667 668 669
    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
670 671 672 673 674 675 676 677 678
    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 ;

679
    return true;
680 681
}

Pierre Kraemer's avatar
Pierre Kraemer committed
682 683 684 685
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

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

untereiner's avatar
untereiner committed
691 692 693
	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
694 695
	mv.mark(d);

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

untereiner's avatar
untereiner committed
703 704 705 706 707 708 709 710 711
		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
712 713
		}

714
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
715 716 717 718
	}
	return found;
}

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

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

untereiner's avatar
untereiner committed
736 737 738
	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
739 740
	mv.mark(d);

741
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
742
	{
untereiner's avatar
untereiner committed
743
		// add all successors if they are not marked yet
744 745 746
		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
747

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

764
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
765 766 767 768
	}
	return found;
}

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

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

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

untereiner's avatar
untereiner committed
783
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
784

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

untereiner's avatar
untereiner committed
791 792 793
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
794

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

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
823
		} while(f != it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
824 825
	}

untereiner's avatar
untereiner committed
826 827 828 829 830 831 832 833 834 835 836
	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
837 838 839
}

} // namespace CGoGN