map2.cpp 19 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1 2 3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2011, IGG Team, LSIIT, University of Strasbourg           *
Pierre Kraemer's avatar
Pierre Kraemer committed
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*                                                                              *
* This library is free software; you can redistribute it and/or modify it      *
* under the terms of the GNU Lesser General Public License as published by the *
* Free Software Foundation; either version 2.1 of the License, or (at your     *
* option) any later version.                                                   *
*                                                                              *
* This library is distributed in the hope that it will be useful, but WITHOUT  *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License  *
* for more details.                                                            *
*                                                                              *
* You should have received a copy of the GNU Lesser General Public License     *
* along with this library; if not, write to the Free Software Foundation,      *
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.           *
*                                                                              *
20
* Web site: http://cgogn.u-strasbg.fr/                                         *
Pierre Kraemer's avatar
Pierre Kraemer committed
21 22 23 24 25
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/map/map2.h"
26
#include "Topology/generic/traversorCell.h"
untereiner's avatar
untereiner committed
27
#include "Topology/generic/traversor2CC.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
28 29 30 31

namespace CGoGN
{

Pierre Kraemer's avatar
Pierre Kraemer committed
32 33
/*! @name Boundary marker management
 *  Function used to merge boundary faces properly
Pierre Kraemer's avatar
Pierre Kraemer committed
34 35
 *************************************************************************/

36 37 38 39 40 41 42 43
//void Map2::mergeBoundaryFaces(Dart dd, Dart ee)
//{
//	if (ee != phi_1(dd))
//		phi1sew(ee, phi_1(dd)) ;
//	if (dd != phi_1(ee))
//		phi1sew(dd, phi_1(ee)) ;
//	deleteCycle(dd);
//}
44

45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
//void Map2::mergeFaceWithBoundary(Dart d)
//{
//	std::vector<Dart> storeForLinkVertex;
//	std::vector<Dart> storeForLinkFace;
//
//	Dart it = d ;
//	do	// foreach vertex/edge of face
//	{
//		Dart e = phi2(it) ;
//		if(isBoundaryMarked(e))	// check if connection by edge
//		{
//			storeForLinkFace.push_back(it);
//			storeForLinkFace.push_back(e);
//		}
//		else
//		{
61
//			Dart f = findBoundaryEdgeOfVertex(alpha1(it));	// check if connection by vertex
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
//			if (f != it)
//			{
//				storeForLinkVertex.push_back(phi_1(it));
//				storeForLinkVertex.push_back(phi_1(f));
//			}
//		}
//		it = phi1(it) ;
//	} while (it != d) ;
//
//	// merge by vertices
//	while (!storeForLinkVertex.empty())
//	{
//		Dart a = storeForLinkVertex.back() ;
//		storeForLinkVertex.pop_back() ;
//		Dart b = storeForLinkVertex.back() ;
//		storeForLinkVertex.pop_back() ;
//		phi1sew(a, b);
//	}
//	//merge by faces
//	while (!storeForLinkFace.empty())
//	{
//		Dart a = storeForLinkVertex.back() ;
//		storeForLinkVertex.pop_back() ;
//		Dart b = storeForLinkVertex.back() ;
//		storeForLinkVertex.pop_back() ;
//		mergeBoundaryFaces(a, b);
//	}
//}
Sylvain Thery's avatar
Sylvain Thery committed
90

Pierre Kraemer's avatar
Pierre Kraemer committed
91 92 93 94
/*! @name Generator and Deletor
 *  To generate or delete faces in a 2-map
 *************************************************************************/

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

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

113 114 115 116
void Map2::deleteFace(Dart d)
{
	assert(!isBoundaryMarked(d)) ;
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
117 118
	do
	{
119 120 121 122 123 124 125 126 127
		if(!isBoundaryEdge(it))
			unsewFaces(it) ;
		it = phi1(it) ;
	} while(it != d) ;
	Dart dd = phi2(d) ;
	Map1::deleteCycle(d) ;
	Map1::deleteCycle(dd) ;
}

untereiner's avatar
untereiner committed
128 129 130 131 132
void Map2::deleteCC(Dart d)
{
	DartMarkerStore mark(*this);

	std::vector<Dart> visited;
133
	visited.reserve(1024) ;
untereiner's avatar
untereiner committed
134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
	visited.push_back(d);
	std::vector<Dart>::iterator it;

	for (it = visited.begin(); it != visited.end(); ++it)
	{
		if (!mark.isMarked(*it))
		{
			Dart d1 = phi1(*it) ;
			if(!mark.isMarked(d1))
			{
				mark.mark(d1);
				visited.push_back(d1) ;
			}
			Dart d2 = phi2(*it) ;
			if(!mark.isMarked(d2))
			{
				mark.mark(d2);
				visited.push_back(d2) ;
			}
		}
	}

	for(it = visited.begin(); it != visited.end(); ++it)
		deleteDart(*it) ;
}

160 161 162 163
void Map2::fillHole(Dart d)
{
	assert(isBoundaryMarked(d)) ;
	boundaryUnmarkOrbit(FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
}

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

void Map2::splitVertex(Dart d, Dart e)
{
	assert(sameOrientedVertex(d, e));
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
	Map1::cutEdge(dd);			// Cut the edge of dd (make a new half edge)
	Map1::cutEdge(ee);			// Cut the edge of ee (make a new half edge)
	phi2sew(phi1(dd), phi1(ee));// Sew the two faces along the new edge
}

180
Dart Map2::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
181 182
{
	if(isBoundaryVertex(d))
183
		return NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
184

185
	Dart res = NIL ;
Pierre Kraemer's avatar
Pierre Kraemer committed
186 187 188
	Dart vit = d ;
	do
	{
189 190 191
		if(res == NIL && phi1(phi1(d)) != d)
			res = phi1(d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
192 193
		Dart f = phi_1(phi2(vit)) ;
		phi1sew(vit, f) ;
194

Pierre Kraemer's avatar
Pierre Kraemer committed
195 196
		vit = alpha1(vit) ;
	} while(vit != d) ;
197
	deleteCycle(d) ;
198
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
199 200
}

Pierre Kraemer's avatar
Pierre Kraemer committed
201 202 203
void Map2::cutEdge(Dart d)
{
	Dart e = phi2(d);
Sylvain Thery's avatar
Sylvain Thery committed
204
	phi2unsew(d);			// remove old phi2 links
205 206
	Map1::cutEdge(d);		// Cut the 1-edge of d
	Map1::cutEdge(e);		// Cut the 1-edge of phi2(d)
Sylvain Thery's avatar
Sylvain Thery committed
207

208 209
	phi2sew(d, phi1(e));			// Correct the phi2 links
	phi2sew(e, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
210 211
}

Pierre Kraemer's avatar
Pierre Kraemer committed
212
bool Map2::uncutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
213
{
Pierre Kraemer's avatar
Pierre Kraemer committed
214
	if(vertexDegree(phi1(d)) == 2)
Pierre Kraemer's avatar
Pierre Kraemer committed
215
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
216
		Dart ne = phi2(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
217 218 219 220 221 222 223
		Dart nd = phi1(d) ;
		Dart e = phi_1(ne) ;
		phi2unsew(e) ;
		phi2unsew(d) ;
		Map1::collapseEdge(nd) ;
		Map1::collapseEdge(ne) ;
		phi2sew(d, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
224
		return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
225
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
226
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
227 228
}

229
Dart Map2::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
230
{
Pierre Kraemer's avatar
Pierre Kraemer committed
231
	Dart resV = NIL ;
232 233

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

236 237
	Dart f = phi1(e) ;
	Dart h = alpha1(e);
238

239
	if (h != e)
240
		resV = h;
241

242
	if (f != e && delDegenerateFaces)
Sylvain Thery's avatar
Sylvain Thery committed
243 244
	{
		Map1::collapseEdge(e) ;		// Collapse edge e
245
		collapseDegeneratedFace(f) ;// and collapse its face if degenerated
Sylvain Thery's avatar
Sylvain Thery committed
246 247
	}
	else
248
		Map1::collapseEdge(e) ;	// Just collapse edge e
249

250 251
	f = phi1(d) ;
	if(resV == NIL)
252
	{
253 254
		h = alpha1(d);
		if (h != d)
255
			resV = h;
256 257
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
258 259
	if (f != d && delDegenerateFaces)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
260 261
		Map1::collapseEdge(d) ;		// Collapse edge d
		collapseDegeneratedFace(f) ;// and collapse its face if degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
262 263
	}
	else
Pierre Kraemer's avatar
Pierre Kraemer committed
264
		Map1::collapseEdge(d) ;	// Just collapse edge d
265 266

	return resV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
267 268 269 270
}

bool Map2::flipEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
271
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
272
	{
Sylvain Thery's avatar
Sylvain Thery committed
273
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
274 275 276 277 278 279 280 281 282 283 284 285 286 287 288
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
		phi1sew(d, ePrev);		// Detach the two
		phi1sew(e, dPrev);		// vertices of the edge
		phi1sew(d, dNext);		// Insert the edge in its
		phi1sew(e, eNext);		// new vertices after flip
		return true ;
	}
	return false ; // cannot flip a border edge
}

bool Map2::flipBackEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
289
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
290
	{
Sylvain Thery's avatar
Sylvain Thery committed
291
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
292 293 294 295 296 297 298 299 300 301 302
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
		phi1sew(d, ePrev);			// Detach the two
		phi1sew(e, dPrev);			// vertices of the edge
		phi1sew(e, phi_1(dPrev));	// Insert the edge in its
		phi1sew(d, phi_1(ePrev));	// new vertices after flip
		return true ;
	}
	return false ; // cannot flip a border edge
}

303 304 305 306 307 308 309 310 311 312 313 314 315 316 317
//void Map2::insertEdgeInVertex(Dart d, Dart e)
//{
//	assert(!sameVertex(d,e) && phi2(e) == phi_1(e));
//	phi1sew(phi_1(d), phi_1(e));
//}
//
//bool Map2::removeEdgeFromVertex(Dart d)
//{
//	if (!isBoundaryEdge(d))
//	{
//		phi1sew(phi_1(d), phi2(d)) ;
//		return true ;
//	}
//	return false ;
//}
318

319
void Map2::sewFaces(Dart d, Dart e, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
320
{
321 322 323
	// if sewing with fixed points
	if (!withBoundary)
	{
324 325 326
		assert(phi2(d) == d && phi2(e) == e) ;
		phi2sew(d, e) ;
		return ;
327
	}
328

329
	assert(isBoundaryEdge(d) && isBoundaryEdge(e)) ;
330

331 332
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
333

334 335
	phi2unsew(d) ;	// unsew faces from boundary
	phi2unsew(e) ;
336

337 338 339 340 341
	if (ee != phi_1(dd))
		phi1sew(ee, phi_1(dd)) ;	// remove the boundary edge
	if (dd != phi_1(ee))
		phi1sew(dd, phi_1(ee)) ;	// and properly close incident boundaries
	Map1::deleteCycle(dd) ;
Sylvain Thery's avatar
Sylvain Thery committed
342

343
	phi2sew(d, e) ; // sew the faces
Pierre Kraemer's avatar
Pierre Kraemer committed
344 345 346 347
}

void Map2::unsewFaces(Dart d)
{
348 349
	assert(!isBoundaryEdge(d)) ;

Sylvain Thery's avatar
Sylvain Thery committed
350 351
	Dart dd = phi2(d);

352
	Dart e = newBoundaryCycle(2);
353
	Dart ee = phi1(e) ;
Sylvain Thery's avatar
Sylvain Thery committed
354 355 356

	if (isBoundaryVertex(d))
	{
357
		Dart f = findBoundaryEdgeOfVertex(d);
358
		phi1sew(e, phi_1(f));
Sylvain Thery's avatar
Sylvain Thery committed
359 360 361 362
	}

	if (isBoundaryVertex(dd))
	{
363
		Dart f = findBoundaryEdgeOfVertex(dd);
364
		phi1sew(ee, phi_1(f));
Sylvain Thery's avatar
Sylvain Thery committed
365 366
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
367
	phi2unsew(d);
368 369 370

	phi2sew(d, e);		// sew faces
	phi2sew(dd, ee);	// to the boundary
Pierre Kraemer's avatar
Pierre Kraemer committed
371 372 373 374
}

bool Map2::collapseDegeneratedFace(Dart d)
{
375
	Dart e = phi1(d) ;				// Check if the face is degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
376 377
	if (phi1(e) == d)				// Yes: it contains one or two edge(s)
	{
378 379 380 381 382 383 384 385 386 387 388 389 390 391
		Dart d2 = phi2(d) ;			// Check opposite edges
		Dart e2 = phi2(e) ;
		phi2unsew(d) ;
		if(d != e)
		{
			phi2unsew(e) ;
			phi2sew(d2, e2) ;
		}
		else
		{
			phi1sew(d2, phi_1(d2)) ;
			Map1::deleteCycle(d2) ;
		}
		Map1::deleteCycle(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
392 393 394 395 396 397 398
		return true ;
	}
	return false ;
}

void Map2::splitFace(Dart d, Dart e)
{
399 400 401 402 403
	assert(d != e && sameFace(d, e)) ;
	Map1::cutEdge(phi_1(d)) ;
	Map1::cutEdge(phi_1(e)) ;
	Map1::splitCycle(phi_1(d), phi_1(e)) ;
	phi2sew(phi_1(d), phi_1(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
404 405 406 407
}

bool Map2::mergeFaces(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
408
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
409
	{
Sylvain Thery's avatar
Sylvain Thery committed
410
		Dart e = phi2(d) ;
411
		phi2unsew(d) ;
412
		Map1::mergeCycles(d, phi1(e)) ;
413
		Map1::splitCycle(e, phi1(d)) ;
414
		Map1::deleteCycle(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
415 416 417 418 419 420 421 422
		return true ;
	}
	return false ;
}

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

424 425 426
	assert(!isBoundaryFace(d) && !isBoundaryFace(e)) ;
	assert(faceDegree(d) == 3 && faceDegree(e) == 3) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
427 428 429 430 431
	Dart d1 = phi2(phi1(d)) ;
	Dart d2 = phi2(phi_1(d)) ;
	phi2unsew(d1) ;
	phi2unsew(d2) ;
	phi2sew(d1, d2) ;
432 433 434 435 436 437

	Dart e1 = phi2(phi1(e)) ;
	Dart e2 = phi2(phi_1(e)) ;
	phi2unsew(e1) ;
	phi2unsew(e2) ;
	phi2sew(e1, e2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
438 439 440 441 442
}

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

444 445
	assert(v1 != v2 && sameOrientedVertex(v1, v2)) ;
	assert(faceDegree(d) == 3 && faceDegree(phi2(d)) == 3) ;
Sylvain Thery's avatar
Sylvain Thery committed
446

Pierre Kraemer's avatar
Pierre Kraemer committed
447 448 449 450
	Dart vv1 = phi2(v1) ;
	phi2unsew(v1) ;
	phi2sew(phi_1(d), v1) ;
	phi2sew(phi1(d), vv1) ;
451 452 453 454 455

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

458 459
void Map2::unsewAroundVertex(Dart d)
{
460
	Dart it = d ;
461 462
	do
	{
463 464
		Dart temp = phi1(it) ;
		Dart e_1 = phi_1(it) ;
465 466 467

		do
		{
468 469 470
			unsewFaces(temp) ;
			temp = phi1(temp) ;
		} while(temp != e_1);
471

472
		it = alpha1(it);
473
	}
474
	while(it != d);
475 476
}

Pierre Kraemer's avatar
Pierre Kraemer committed
477 478
bool Map2::mergeVolumes(Dart d, Dart e)
{
479
	assert(!isBoundaryMarked(d) && !isBoundaryMarked(e)) ;
Sylvain Thery's avatar
Sylvain Thery committed
480

481
	if (isBoundaryFace(d) || isBoundaryFace(e))
Sylvain Thery's avatar
Sylvain Thery committed
482 483
		return false;

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

Pierre Kraemer's avatar
Pierre Kraemer committed
487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515
	std::vector<Dart> dDarts;
	std::vector<Dart> eDarts;
	dDarts.reserve(16);		// usual faces have less than 16 edges
	eDarts.reserve(16);

	Dart dFit = d ;
	Dart eFit = phi1(e) ;	// must take phi1 because of the use
	do						// of reverse iterator for sewing loop
	{
		dDarts.push_back(dFit) ;
		dFit = phi1(dFit) ;
	} while(dFit != d) ;
	do
	{
		eDarts.push_back(eFit) ;
		eFit = phi1(eFit) ;
	} while(eFit != phi1(e)) ;

	if(dDarts.size() != eDarts.size())
		return false ;

	// Make the sewing: take darts in initial order (clockwise) in first face
	// and take darts in reverse order (counter-clockwise) in the second face
	std::vector<Dart>::iterator dIt;
	std::vector<Dart>::reverse_iterator eIt;
	for (dIt = dDarts.begin(), eIt = eDarts.rbegin(); dIt != dDarts.end(); ++dIt, ++eIt)
	{
		Dart d2 = phi2(*dIt);			// Search the faces adjacent to dNext and eNext
		Dart e2 = phi2(*eIt);
516
		phi2unsew(d2);		// Unlink the two adjacent faces from dNext and eNext
Sylvain Thery's avatar
Sylvain Thery committed
517
		phi2unsew(e2);
518
		phi2sew(d2, e2);	// Link the two adjacent faces together
Pierre Kraemer's avatar
Pierre Kraemer committed
519
	}
520
	deleteCycle(d);		// Delete the two alone faces
521
	deleteCycle(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
522 523 524 525 526 527 528 529 530 531

	return true ;
}

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

bool Map2::sameOrientedVertex(Dart d, Dart e)
{
532
	Dart it = d;				// Foreach dart dNext in the vertex of d
Pierre Kraemer's avatar
Pierre Kraemer committed
533 534
	do
	{
535
		if (it == e)			// Test equality with e
Pierre Kraemer's avatar
Pierre Kraemer committed
536
			return true;
537 538
		it = alpha1(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
539 540 541
	return false;				// None is equal to e => vertices are distinct
}

542 543 544
unsigned int Map2::vertexDegree(Dart d)
{
	unsigned int count = 0 ;
545
	Dart it = d ;
546 547 548
	do
	{
		++count ;
549 550
		it = alpha1(it) ;
	} while (it != d) ;
551 552 553
	return count ;
}

554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595
bool Map2::isBoundaryVertex(Dart d)
{
	Dart it = d ;
	do
	{
		if (isBoundaryMarked(it))
			return true ;
		it = alpha1(it) ;
	} while (it != d) ;
	return false ;
}

Dart Map2::findBoundaryEdgeOfVertex(Dart d)
{
	Dart it = d ;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha1(it) ;
	} while (it != d) ;
	return NIL ;
}

bool Map2::isBoundaryEdge(Dart d)
{
	Dart e = phi2(d);
	return isBoundaryMarked(e) || isBoundaryMarked(d);
}

bool Map2::isBoundaryFace(Dart d)
{
	Dart it = d ;
	do
	{
		if (isBoundaryMarked(phi2(it)))
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

596
bool Map2::sameOrientedVolume(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
597
{
598 599 600 601 602 603 604
	DartMarkerStore mark(*this);	// Lock a marker

	std::list<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.push_back(d);		// Start with the face of d
	std::list<Dart>::iterator face;

	// For every face added to the list
Pierre Kraemer's avatar
Pierre Kraemer committed
605
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Pierre Kraemer's avatar
Pierre Kraemer committed
606
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
607
		if (!isBoundaryMarked(*face) && !mark.isMarked(*face))		// Face has not been visited yet
608
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
609
			Dart it = *face ;
610 611
			do
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
612
				if(it == e)
613 614
					return true;

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

unsigned int Map2::volumeDegree(Dart d)
{
	unsigned int count = 0;
	DartMarkerStore mark(*this);		// Lock a marker

	std::vector<Dart> visitedFaces;		// Faces that are traversed
	visitedFaces.reserve(16);
	visitedFaces.push_back(d);			// Start with the face of d
	std::vector<Dart>::iterator face;

	// For every face added to the list
637
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
638
	{
Sylvain Thery's avatar
Sylvain Thery committed
639 640
		Dart df = visitedFaces[i];
		if (!isBoundaryMarked(df) && !mark.isMarked(df))		// Face has not been visited yet
Pierre Kraemer's avatar
Pierre Kraemer committed
641 642
		{
			++count;
643
			Dart it = df ;
Pierre Kraemer's avatar
Pierre Kraemer committed
644 645
			do
			{
646 647
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
Sylvain Thery's avatar
Sylvain Thery committed
648
				if ( !isBoundaryMarked(adj) && !mark.isMarked(adj) )
649 650 651
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
Pierre Kraemer's avatar
Pierre Kraemer committed
652 653 654 655 656 657 658 659
		}
	}

	return count;
}

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

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

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

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

		if (d1 == d)
702
			CGoGNout << "Check: (warning) face loop (one edge)" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
703
		if (phi1(d1) == d)
704
			CGoGNout << "Check: (warning) face with only two edges" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
705
		if (phi2(d1) == d)
706
			CGoGNout << "Check: (warning) dangling edge" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
707
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
708
	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
709 710 711
	{
		if (!m.isMarked(d))	// phi1 a au moins un antécédent ?
		{
712
			CGoGNout << "Check: dart with no phi1 predecessor" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
713 714 715
			return false;
		}
	}
716
	CGoGNout << "Check: topology ok" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
717 718 719 720 721 722 723
	return true;
}

/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
724
bool Map2::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
725 726 727 728 729 730 731 732 733 734 735
{
	Dart dNext = d;
	do
	{
		if (f(dNext))
			return true;
		dNext = alpha1(dNext);
 	} while (dNext != d);
 	return false;
}

Sylvain Thery's avatar
Sylvain Thery committed
736
bool Map2::foreach_dart_of_edge(Dart d, FunctorType& fonct, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
737 738 739
{
	if (fonct(d))
		return true;
Sylvain Thery's avatar
Sylvain Thery committed
740
	return fonct(phi2(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
741 742
}

Sylvain Thery's avatar
Sylvain Thery committed
743
bool Map2::foreach_dart_of_oriented_volume(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
744
{
untereiner's avatar
untereiner committed
745
	DartMarkerStore mark(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
746 747 748 749 750 751 752 753 754
	bool found = false;				// Last functor return value

	std::list<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.push_back(d);		// Start with the face of d
	std::list<Dart>::iterator face;

	// For every face added to the list
	for (face = visitedFaces.begin(); !found && face != visitedFaces.end(); ++face)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
755
		if (!isBoundaryMarked(*face) && !mark.isMarked(*face))		// Face has not been visited yet
Pierre Kraemer's avatar
Pierre Kraemer committed
756 757 758 759 760 761 762 763
		{
			// Apply functor to the darts of the face
			found = foreach_dart_of_oriented_face(*face, f);

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
untereiner's avatar
untereiner committed
764
				Dart it = *face ;
Pierre Kraemer's avatar
Pierre Kraemer committed
765 766
				do
				{
untereiner's avatar
untereiner committed
767 768
					mark.mark(it);					// Mark
					Dart adj = phi2(it);				// Get adjacent face
Pierre Kraemer's avatar
Pierre Kraemer committed
769
					if (!isBoundaryMarked(adj) && !mark.isMarked(adj))
Pierre Kraemer's avatar
Pierre Kraemer committed
770
						visitedFaces.push_back(adj);	// Add it
untereiner's avatar
untereiner committed
771 772
					it = phi1(it);
				} while(it != *face);
Pierre Kraemer's avatar
Pierre Kraemer committed
773 774 775 776 777 778
			}
		}
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
779
/*! @name Close map after import or creation
780
 *  These functions must be used with care, generally only by import/creation algorithms
Pierre Kraemer's avatar
Pierre Kraemer committed
781 782
 *************************************************************************/

783
unsigned int Map2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810
{
	assert(phi2(d) == d);		// Nothing to close

	Dart first = newDart();		// First edge of the face that will fill the hole
	unsigned int countEdges = 1;

	phi2sew(d, first);	// phi2-link the new edge to the hole

	Dart dNext = d;	// Turn around the hole
	Dart dPhi1;		// to complete the face
	do
	{
		do
		{
			dPhi1 = phi1(dNext);	// Search and put in dNext
			dNext = phi2(dPhi1);	// the next dart of the hole
		} while (dNext != dPhi1 && dPhi1 != d);

		if (dPhi1 != d)
		{
			Dart next = newDart();	// Add a new edge there and link it to the face
			++countEdges;
			phi1sew(first, next);	// the edge is linked to the face
			phi2sew(dNext, next);	// the face is linked to the hole
		}
	} while (dPhi1 != d);

811
	if (countEdges < 3)
Pierre Kraemer's avatar
Pierre Kraemer committed
812 813 814 815
	{
		countEdges = 0 ;
		collapseDegeneratedFace(first); // if the closing face is 2-sided, collapse it
	}
816 817 818 819 820
	else
	{
		if(forboundary)
			boundaryMarkOrbit(FACE, phi2(d));
	}
821

Pierre Kraemer's avatar
Pierre Kraemer committed
822 823 824 825 826 827 828 829 830 831 832 833
	return countEdges ;
}

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

} // namespace CGoGN