gmap2.cpp 20.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
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/gmap/gmap2.h"
26
#include "Topology/generic/traversorCell.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
27 28 29 30

namespace CGoGN
{

Pierre Kraemer's avatar
merges  
Pierre Kraemer committed
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
void GMap2::compactTopoRelations(const std::vector<unsigned int>& oldnew)
{
	for (unsigned int i = m_attribs[DART].begin(); i != m_attribs[DART].end(); m_attribs[DART].next(i))
	{
		{
			Dart& d = m_beta0->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
		{
			Dart& d = m_beta1->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
		{
			Dart& d = m_beta2->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
	}
}

56 57
/*! @name Generator and Deletor
 *  To generate or delete faces in a 2-G-map
Pierre Kraemer's avatar
Pierre Kraemer committed
58 59
 *************************************************************************/

60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
Dart GMap2::newFace(unsigned int nbEdges, bool withBoundary)
{
	Dart d = GMap1::newFace(nbEdges);
	if (withBoundary)
	{
		Dart e = GMap1::newFace(nbEdges);

		Dart it = d;
		do
		{
			beta2sew(it, beta0(e));
			beta2sew(beta0(it), e);
			it = phi1(it);
			e = phi_1(e);
		} while (it != d);
	}
	return d;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
79 80
void GMap2::deleteFace(Dart d)
{
81 82
	assert(!isBoundaryMarked(d)) ;
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
83 84
	do
	{
85 86 87 88 89 90 91 92 93
		if(!isBoundaryEdge(it))
			unsewFaces(it) ;
		it = phi1(it) ;
	} while(it != d) ;
	Dart dd = phi2(d) ;
	GMap1::deleteFace(d) ;
	GMap1::deleteFace(dd) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
94 95 96 97 98 99 100 101 102
void GMap2::deleteCC(Dart d)
{
	DartMarkerStore mark(*this);

	std::vector<Dart> visited;
	visited.reserve(1024) ;
	visited.push_back(d);
	mark.mark(d) ;

103
	for(unsigned int i = 0; i < visited.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
104
	{
105
		Dart d0 = beta0(visited[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
106 107 108 109 110
		if(!mark.isMarked(d0))
		{
			visited.push_back(d0) ;
			mark.mark(d0);
		}
111
		Dart d1 = beta1(visited[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
112 113 114 115 116
		if(!mark.isMarked(d1))
		{
			visited.push_back(d1) ;
			mark.mark(d1);
		}
117
		Dart d2 = beta2(visited[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
118 119 120 121 122 123 124 125 126 127 128
		if(!mark.isMarked(d2))
		{
			visited.push_back(d2) ;
			mark.mark(d2);
		}
	}

	for(std::vector<Dart>::iterator it = visited.begin(); it != visited.end(); ++it)
		deleteDart(*it) ;
}

129 130
void GMap2::fillHole(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
131 132 133 134 135
	assert(isBoundaryEdge(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi2(dd) ;
	boundaryUnmarkOrbit(FACE, dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
136 137 138 139 140 141 142 143
}

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

void GMap2::splitVertex(Dart d, Dart e)
{
144
	assert(sameVertex(d, e));
Pierre Kraemer's avatar
Pierre Kraemer committed
145 146 147 148

	if(!sameOrientedVertex(d, e))
		e = beta2(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
149 150
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
151 152 153
	beta2unsew(d) ;
	beta2unsew(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
154 155
	GMap1::cutEdge(dd);			// Cut the edge of dd (make a new edge)
	GMap1::cutEdge(ee);			// Cut the edge of ee (make a new edge)
Pierre Kraemer's avatar
Pierre Kraemer committed
156

157 158
	beta2sew(phi1(dd), beta0(phi1(ee)));	// Sew the two faces along the new edge
	beta2sew(phi1(ee), beta0(phi1(dd)));
Pierre Kraemer's avatar
Pierre Kraemer committed
159 160
	beta2sew(d, beta0(dd)) ;
	beta2sew(e, beta0(ee)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
161 162
}

163
Dart GMap2::deleteVertex(Dart d)
164 165
{
	if(isBoundaryVertex(d))
166
		return NIL ;
167

168
	Dart res = NIL ;
169 170 171
	Dart vit = d ;
	do
	{
172 173 174 175 176 177 178 179 180 181 182 183
		if(res == NIL && phi1(phi1(d)) != d)
			res = phi1(d) ;

		Dart d0 = beta0(vit) ;
		Dart d02 = beta2(d0) ;
		Dart d01 = beta1(d0) ;
		Dart d021 = beta1(d02) ;
		beta1unsew(d0) ;
		beta1unsew(d02) ;
		beta1sew(d0, d02) ;
		beta1sew(d01, d021) ;

184 185
		vit = alpha1(vit) ;
	} while(vit != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
186
	GMap1::deleteFace(d) ;
187
	return res ;
188 189
}

190
Dart GMap2::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
191
{
192
	Dart e = phi2(d) ;
193 194
	Dart nd = GMap1::cutEdge(d) ;
	Dart ne = GMap1::cutEdge(e) ;
195

196 197
	beta2sew(nd, beta1(ne)) ;
	beta2sew(ne, beta1(nd)) ;
198 199

	return nd ;
Pierre Kraemer's avatar
Pierre Kraemer committed
200 201
}

202
bool GMap2::uncutEdge(Dart d)
203
{
204
	if(vertexDegree(phi1(d)) == 2)
205
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
206 207
		GMap1::uncutEdge(d) ;
		GMap1::uncutEdge(beta2(d)) ;
208
		return true ;
209
	}
210
	return false ;
211 212 213
}

Dart GMap2::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
214
{
215
	Dart resV = NIL ;
216 217

	Dart e = phi2(d);
218 219
	beta2unsew(d);	// Unlink the opposite edges
	beta2unsew(e);
220

221 222
	Dart f = phi1(e) ;
	Dart h = alpha1(e);
223

224 225
	if (h != e)
		resV = h;
226

227 228 229 230 231 232 233
	if (f != e && delDegenerateFaces)
	{
		GMap1::collapseEdge(e) ;		// Collapse edge e
		collapseDegeneratedFace(f) ;	// and collapse its face if degenerated
	}
	else
		GMap1::collapseEdge(e) ;	// Just collapse edge e
234

235
	f = phi1(d) ;
236
	if(resV == NIL)
237
	{
238 239 240
		h = alpha1(d);
		if (h != d)
			resV = h;
241 242
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
243 244
	if (f != d && delDegenerateFaces)
	{
245 246
		GMap1::collapseEdge(d) ;		// Collapse edge d
		collapseDegeneratedFace(f) ;	// and collapse its face if degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
247 248
	}
	else
249
		GMap1::collapseEdge(d) ;	// Just collapse edge d
250 251

	return resV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
252 253 254 255
}

bool GMap2::flipEdge(Dart d)
{
256
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
257
	{
258
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
259 260 261 262
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279
		Dart dNext2 = phi1(dNext);
		Dart eNext2 = phi1(eNext);

		beta1unsew(d) ;
		beta1unsew(eNext) ;
		beta1unsew(e) ;
		beta1unsew(dNext) ;
		beta1unsew(dNext2) ;
		beta1unsew(eNext2) ;

		beta1sew(beta0(e), eNext2) ;
		beta1sew(d, beta0(eNext)) ;
		beta1sew(beta0(d), dNext2) ;
		beta1sew(e, beta0(dNext)) ;
		beta1sew(eNext, beta0(dPrev)) ;
		beta1sew(dNext, beta0(ePrev)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
280 281 282 283 284 285 286
		return true ;
	}
	return false ; // cannot flip a border edge
}

bool GMap2::flipBackEdge(Dart d)
{
287
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
288
	{
289
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
290 291 292 293
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
		Dart dPrev1 = beta1(dPrev) ;
		Dart ePrev1 = beta1(ePrev) ;

		beta1unsew(d) ;
		beta1unsew(eNext) ;
		beta1unsew(e) ;
		beta1unsew(dNext) ;
		beta1unsew(dPrev) ;
		beta1unsew(ePrev) ;

		beta1sew(beta0(e), dPrev) ;
		beta1sew(d, dPrev1) ;
		beta1sew(beta0(d), ePrev) ;
		beta1sew(e, ePrev1) ;
		beta1sew(eNext, beta0(dPrev)) ;
		beta1sew(dNext, beta0(ePrev)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
311 312 313 314 315
		return true ;
	}
	return false ; // cannot flip a border edge
}

316 317 318 319 320 321 322 323 324 325 326 327 328 329 330
//void GMap2::insertEdgeInVertex(Dart d, Dart e)
//{
//	assert(!sameVertex(d,e) && phi2(e)==phi_1(e));
//
//	phi1sew(phi_1(d),phi_1(e));
//}
//
//void GMap2::removeEdgeFromVertex(Dart d)
//{
//	assert(phi2(d)!=d);
//
//	phi1sew(phi_1(d),phi2(d));
//}

void GMap2::sewFaces(Dart d, Dart e, bool withBoundary)
331
{
332 333 334 335 336 337 338 339
	// if sewing with fixed points
	if (!withBoundary)
	{
		assert(beta2(d) == d && beta2(beta0(d)) == beta0(d) && beta2(e) == e && beta2(beta0(e)) == beta0(e)) ;
		beta2sew(d, beta0(e)) ;
		beta2sew(e, beta0(d)) ;
		return ;
	}
340

341
	assert(isBoundaryEdge(d) && isBoundaryEdge(e)) ;
342

343 344
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
345

346 347 348 349
	beta2unsew(d) ;	// unsew faces from boundary
	beta2unsew(beta0(d)) ;
	beta2unsew(e) ;
	beta2unsew(beta0(e)) ;
350

351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372
	if (ee != phi_1(dd))
	{
		Dart eeN = phi1(ee) ;		// remove the boundary edge
		Dart dd1 = beta1(dd) ;
		beta1unsew(eeN) ;
		beta1unsew(dd1) ;
		beta1sew(beta0(ee), dd) ;
		beta1sew(eeN, dd1) ;
	}
	if (dd != phi_1(ee))
	{
		Dart ddN = phi1(dd) ;		// and properly close incident boundaries
		Dart ee1 = beta1(ee) ;
		beta1unsew(ddN) ;
		beta1unsew(ee1) ;
		beta1sew(beta0(dd), ee) ;
		beta1sew(ddN, ee1) ;
	}
	GMap1::deleteFace(dd) ;

	beta2sew(d, beta0(e)) ; // sew the faces
	beta2sew(e, beta0(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
373 374 375 376
}

void GMap2::unsewFaces(Dart d)
{
377 378 379 380 381 382 383
	assert(!isBoundaryEdge(d)) ;

	Dart dd = phi2(d);

	Dart e = newBoundaryFace(2);
	Dart ee = phi1(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
384 385
	Dart f = findBoundaryEdgeOfVertex(d) ;
	if (f != NIL)
386 387 388 389 390 391 392 393
	{
		Dart f1 = beta1(f) ;
		beta1unsew(ee) ;
		beta1unsew(f) ;
		beta1sew(f, beta0(e)) ;
		beta1sew(f1, ee) ;
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
394 395
	f = findBoundaryEdgeOfVertex(dd) ;
	if (f != NIL)
396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412
	{
		Dart f1 = beta1(f) ;
		beta1unsew(e) ;
		beta1unsew(f) ;
		beta1sew(f, beta0(ee)) ;
		beta1sew(f1, e) ;
	}

	beta2unsew(d) ;
	beta2unsew(beta0(d)) ;
	beta2unsew(dd) ;
	beta2unsew(beta0(dd)) ;

	beta2sew(d, beta0(e)) ;		// sew faces
	beta2sew(e, beta0(d)) ;
	beta2sew(dd, beta0(ee)) ;	// to the boundary
	beta2sew(ee, beta0(dd)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
413 414 415 416 417 418 419
}

bool GMap2::collapseDegeneratedFace(Dart d)
{
	Dart e = phi1(d);				// Check if the face is a loop
	if (phi1(e) == d)				// Yes: it contains one or two edge(s)
	{
420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441
		Dart d2 = phi2(d) ;			// Check opposite edges
		Dart e2 = phi2(e) ;
		beta2unsew(d) ;
		beta2unsew(beta0(d)) ;
		if(d != e)
		{
			beta2unsew(e) ;
			beta2unsew(beta0(e)) ;
			beta2sew(d2, beta0(e2)) ;
			beta2sew(e2, beta0(d2)) ;
		}
		else
		{
			Dart d21 = beta1(d2) ;
			Dart d2N = phi1(d2) ;
			beta1unsew(d2) ;
			beta1unsew(d2N) ;
			beta1sew(d21, d2N) ;
			beta1sew(d2, beta0(d2)) ;
			GMap1::deleteFace(d2) ;
		}
		GMap1::deleteFace(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
442 443 444 445 446 447 448
		return true ;
	}
	return false ;
}

void GMap2::splitFace(Dart d, Dart e)
{
449 450 451 452 453
	assert(d != e && sameFace(d, e)) ;

	if(!sameOrientedFace(d, e))
		e = beta1(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
454 455 456 457 458 459
	Dart dprev = phi_1(d) ;
	Dart eprev = phi_1(e) ;

	beta2unsew(beta1(d)) ;
	beta2unsew(beta1(e)) ;

460 461 462 463 464
	GMap1::cutEdge(phi_1(d)) ;
	GMap1::cutEdge(phi_1(e)) ;
	GMap1::splitFace(phi_1(d), phi_1(e)) ;
	beta2sew(phi_1(d), beta1(e)) ;
	beta2sew(phi_1(e), beta1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
465 466 467

	beta2sew(beta0(dprev), beta0(beta2(dprev))) ;
	beta2sew(beta0(eprev), beta0(beta2(eprev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
468 469 470 471
}

bool GMap2::mergeFaces(Dart d)
{
472
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
473
	{
474 475 476 477 478 479
		Dart e = phi2(d) ;
		beta2unsew(d) ;
		beta2unsew(e) ;
		GMap1::mergeFaces(d, phi1(e)) ;
		GMap1::mergeFaces(e, phi1(d)) ;
		GMap1::deleteFace(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
480 481 482 483 484 485 486 487
		return true ;
	}
	return false ;
}

void GMap2::extractTrianglePair(Dart d)
{
	Dart e = phi2(d) ;
488 489 490 491

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

Pierre Kraemer's avatar
Pierre Kraemer committed
492 493
	Dart d1 = phi2(phi1(d)) ;
	Dart d2 = phi2(phi_1(d)) ;
494 495 496 497 498 499 500 501 502 503 504 505 506 507 508
	beta2unsew(d1) ;
	beta2unsew(beta0(d1)) ;
	beta2unsew(d2) ;
	beta2unsew(beta0(d2)) ;
	beta2sew(d1, beta0(d2)) ;
	beta2sew(d2, beta0(d1)) ;

	Dart e1 = phi2(phi1(e)) ;
	Dart e2 = phi2(phi_1(e)) ;
	beta2unsew(e1) ;
	beta2unsew(beta0(e1)) ;
	beta2unsew(e2) ;
	beta2unsew(beta0(e2)) ;
	beta2sew(e1, beta0(e2)) ;
	beta2sew(e2, beta0(e1)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
509 510 511 512 513
}

void GMap2::insertTrianglePair(Dart d, Dart v1, Dart v2)
{
	Dart e = phi2(d) ;
514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538

	assert(v1 != v2 && sameOrientedVertex(v1, v2)) ;
	assert(faceDegree(d) == 3 && faceDegree(phi2(d)) == 3) ;

	Dart vv1 = phi2(v1) ;
	beta2unsew(v1) ;
	beta2unsew(vv1) ;
	beta2sew(phi_1(d), beta0(v1)) ;
	beta2sew(beta1(d), v1) ;
	beta2sew(phi1(d), beta0(vv1)) ;
	beta2sew(beta0(phi1(d)), vv1) ;

	Dart vv2 = phi2(v2) ;
	beta2unsew(v2) ;
	beta2unsew(vv2) ;
	beta2sew(phi_1(e), beta0(v2)) ;
	beta2sew(beta1(e), v2) ;
	beta2sew(phi1(e), beta0(vv2)) ;
	beta2sew(beta0(phi1(e)), vv2) ;
}

void GMap2::unsewAroundVertex(Dart d)
{
	Dart it = d ;
	do
Pierre Kraemer's avatar
Pierre Kraemer committed
539
	{
540 541 542 543 544 545 546 547 548 549
		Dart temp = phi1(it) ;
		Dart e_1 = phi_1(it) ;

		do
		{
			unsewFaces(temp) ;
			temp = phi1(temp) ;
		} while(temp != e_1);

		it = alpha1(it);
Pierre Kraemer's avatar
Pierre Kraemer committed
550
	}
551
	while(it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
552 553 554 555
}

bool GMap2::mergeVolumes(Dart d, Dart e)
{
556 557
	assert(!isBoundaryMarked(d) && !isBoundaryMarked(e)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
558
	if (GMap2::isBoundaryFace(d) || GMap2::isBoundaryFace(e))
559 560
		return false;

Pierre Kraemer's avatar
Pierre Kraemer committed
561
	// First traversal of both faces to check the face sizes
562 563
	// and store their edges to efficiently access them further

Pierre Kraemer's avatar
Pierre Kraemer committed
564 565
	std::vector<Dart> dDarts;
	std::vector<Dart> eDarts;
566
	dDarts.reserve(16);		// usual faces have less than 16 edges
Pierre Kraemer's avatar
Pierre Kraemer committed
567 568 569
	eDarts.reserve(16);

	Dart dFit = d ;
570
	Dart eFit = phi1(e) ;	// must take phi1 because of the use
Pierre Kraemer's avatar
Pierre Kraemer committed
571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590
	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)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
591
		Dart d2 = phi2(*dIt);	// Search the faces adjacent to dNext and eNext
Pierre Kraemer's avatar
Pierre Kraemer committed
592
		Dart e2 = phi2(*eIt);
593 594 595 596 597 598
		beta2unsew(d2);		// Unlink the two adjacent faces from dNext and eNext
		beta2unsew(beta0(d2));
		beta2unsew(e2);
		beta2unsew(beta0(e2));
		beta2sew(d2, beta0(e2));	// Link the two adjacent faces together
		beta2sew(e2, beta0(d2));
Pierre Kraemer's avatar
Pierre Kraemer committed
599
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
600 601
	GMap1::deleteFace(d);		// Delete the two alone faces
	GMap1::deleteFace(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
602 603 604 605 606 607 608 609

	return true ;
}

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

Thomas's avatar
Thomas committed
610 611
bool GMap2::sameOrientedVertex(Dart d, Dart e)
{
612
	Dart it = d;
Thomas's avatar
Thomas committed
613 614
	do
	{
615
		if (it == e)	// Test equality with e
Thomas's avatar
Thomas committed
616
			return true;
617 618 619
		it = alpha1(it);
	} while (it != d);
	return false;		// None is equal to e => vertices are distinct
Thomas's avatar
Thomas committed
620 621
}

622 623 624 625 626 627 628 629 630 631 632
unsigned int GMap2::vertexDegree(Dart d)
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
	{
		++count ;
		it = alpha1(it) ;
	} while (it != d) ;
	return count ;
}
Thomas's avatar
Thomas committed
633

634
bool GMap2::isBoundaryVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
635
{
636
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
637 638
	do
	{
639 640 641 642 643
		if (isBoundaryMarked(it))
			return true ;
		it = alpha1(it) ;
	} while (it != d) ;
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
644 645
}

646
Dart GMap2::findBoundaryEdgeOfVertex(Dart d)
647
{
648
	Dart it = d ;
649 650
	do
	{
651 652 653 654 655
		if (isBoundaryMarked(it))
			return it ;
		it = alpha1(it) ;
	} while (it != d) ;
	return NIL ;
656 657
}

658 659 660
bool GMap2::isBoundaryFace(Dart d)
{
	Dart it = d ;
661 662
	do
	{
663
		if (isBoundaryMarked(beta2(it)))
664
			return true ;
665 666
		it = phi1(it) ;
	} while (it != d) ;
667 668 669
	return false ;
}

Thomas's avatar
Thomas committed
670 671 672 673 674 675 676 677 678
bool GMap2::sameOrientedVolume(Dart d, Dart e)
{
	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
679
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Thomas's avatar
Thomas committed
680
	{
681
		if (!isBoundaryMarked(*face) && !mark.isMarked(*face))		// Face has not been visited yet
Thomas's avatar
Thomas committed
682
		{
683
			Dart it = *face ;
Thomas's avatar
Thomas committed
684 685
			do
			{
686
				if(it == e)
Thomas's avatar
Thomas committed
687 688
					return true;

689 690 691
				mark.mark(it);						// Mark
				Dart adj = phi2(it);				// Get adjacent face
				if (!isBoundaryMarked(adj) && !mark.isMarked(adj))
Thomas's avatar
Thomas committed
692
					visitedFaces.push_back(adj);	// Add it
693 694
				it = phi1(it);
			} while(it != *face);
Thomas's avatar
Thomas committed
695 696 697 698 699
		}
	}
	return false;
}

700
unsigned int GMap2::volumeDegree(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
701
{
702 703
	unsigned int count = 0;
	DartMarkerStore mark(*this);		// Lock a marker
704

705 706 707 708
	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;
709 710

	// For every face added to the list
711
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
712
	{
713 714
		Dart df = visitedFaces[i];
		if (!isBoundaryMarked(df) && !mark.isMarked(df))		// Face has not been visited yet
715
		{
716 717
			++count;
			Dart it = df ;
718 719
			do
			{
720 721 722 723 724 725
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
				if ( !isBoundaryMarked(adj) && !mark.isMarked(adj) )
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
726 727
		}
	}
728 729 730 731 732 733 734 735 736 737 738 739 740

	return count;
}

bool GMap2::isTriangular()
{
	TraversorF<GMap2> t(*this) ;
	for(Dart d = t.begin(); d != t.end(); d = t.next())
	{
		if(faceDegree(d) != 3)
			return false ;
	}
	return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
741 742 743 744
}

bool GMap2::check()
{
745
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
746 747 748 749 750
	for(Dart d = begin(); d != end(); next(d))
	{
		Dart dd = beta0(d);
		if (beta0(dd) != d)	// beta0 involution ?
		{
751
			CGoGNout << "Check: beta0 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
752 753 754 755 756 757
			return false;
		}

		dd = beta1(d);
		if (beta1(dd) != d)	// beta1 involution ?
		{
758
			CGoGNout << "Check: beta1 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
759 760 761 762 763 764
			return false;
		}

		dd = beta2(d);
		if (beta2(dd) != d)	// beta2 involution ?
		{
765
			CGoGNout << "Check: beta2 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
766 767
			return false;
		}
768 769
		if(dd == d)
			CGoGNout << "Check (warning): beta2 has fix points" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
770 771
	}

772
	CGoGNout << "Check: topology ok" << CGoGNendl;
773

Pierre Kraemer's avatar
Pierre Kraemer committed
774 775 776
	return true;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797
bool GMap2::checkSimpleOrientedPath(std::vector<Dart>& vd)
{
	DartMarkerStore dm(*this) ;
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
		if(dm.isMarked(*it))
			return false ;
		dm.markOrbit(VERTEX, *it) ;

		std::vector<Dart>::iterator prev ;
		if(it == vd.begin())
			prev = vd.end() - 1 ;
		else
			prev = it - 1 ;

		if(!sameVertex(*it, phi1(*prev)))
			return false ;
	}
	return true ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
798 799 800 801
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
802
bool GMap2::foreach_dart_of_oriented_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
803
{
804
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
805 806
	do
	{
807
		if (f(it))
Pierre Kraemer's avatar
Pierre Kraemer committed
808
			return true;
809 810
		it = alpha1(it);
 	} while (it != d);
811
 	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
812 813
}

Sylvain Thery's avatar
Sylvain Thery committed
814
bool GMap2::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
815 816 817 818
{
	if (f(d))
		return true ;
	Dart e = beta0(d) ;
819 820 821 822 823 824
	if (f(e))
		return true ;
	e = beta2(d) ;
	if (f(e))
		return true ;
	e = beta0(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
825 826 827 828 829 830
	if (f(e))
		return true ;

	return false ;
}

831 832
bool GMap2::foreach_dart_of_oriented_volume(Dart d, FunctorType& f, unsigned int thread)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
833
	DartMarkerStore mark(*this, thread);	// Lock a marker
834 835
	bool found = false;				// Last functor return value

Pierre Kraemer's avatar
Pierre Kraemer committed
836 837
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
838 839 840
	visitedFaces.push_back(d);		// Start with the face of d

	// For every face added to the list
841
	for(unsigned int i = 0; !found && i < visitedFaces.size(); ++i)
842
	{
843
		if (!mark.isMarked(visitedFaces[i]))		// Face has not been visited yet
844 845
		{
			// Apply functor to the darts of the face
846
			found = foreach_dart_of_oriented_face(visitedFaces[i], f);
847 848 849 850 851

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
852
				Dart e = visitedFaces[i] ;
853 854
				do
				{
Pierre Kraemer's avatar
Pierre Kraemer committed
855 856
					mark.mark(e);					// Mark
					Dart adj = phi2(e);				// Get adjacent face
Pierre Kraemer's avatar
Pierre Kraemer committed
857
					if (!mark.isMarked(adj))
858
						visitedFaces.push_back(adj);	// Add it
Pierre Kraemer's avatar
Pierre Kraemer committed
859
					e = phi1(e);
860
				} while(e != visitedFaces[i]);
861 862 863 864 865 866
			}
		}
	}
	return found;
}

867 868 869 870 871
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/

unsigned int GMap2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
872
{
873
	assert(beta2(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
874

875 876
	Dart first = newEdge();		// First edge of the face that will fill the hole
	unsigned int countEdges = 1;
Pierre Kraemer's avatar
Pierre Kraemer committed
877

878 879
	beta2sew(d, beta0(first));	// sew the new edge to the hole
	beta2sew(first, beta0(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
880

881
	Dart prev = first ;
882 883 884
	Dart dNext = d;	// Turn around the hole
	Dart dPhi1;		// to complete the face
	do
Pierre Kraemer's avatar
Pierre Kraemer committed
885
	{
886 887
		dPhi1 = phi1(dNext) ;
		dNext = beta2(dPhi1) ;
888
		while(dNext != dPhi1 && dPhi1 != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
889
		{
890 891
			dPhi1 = beta1(dNext) ;	// Search and put in dNext
			dNext = beta2(dPhi1) ;	// the next dart of the hole
Pierre Kraemer's avatar
Pierre Kraemer committed
892
		}
893 894

		if (dPhi1 != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
895
		{
896 897
			Dart next = newEdge();	// Add a new edge there and link it to the face
			++countEdges;
898 899
			beta1sew(beta0(next), prev);	// the edge is linked to the face
			prev = next ;
900 901
			beta2sew(dNext, beta0(next));	// the face is linked to the hole
			beta2sew(next, beta0(dNext));
Pierre Kraemer's avatar
Pierre Kraemer committed
902
		}
903 904
	} while (dPhi1 != d);

905 906
	beta1sew(prev, beta0(first)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
907 908
	if(forboundary)
		boundaryMarkOrbit(FACE, phi2(d));
909 910 911 912 913 914 915 916 917 918 919

	return countEdges ;
}

void GMap2::closeMap()
{
	// Search the map for topological holes (fix points of phi2)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (beta2(d) == d)
			closeHole(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
920 921 922 923
	}
}

} // namespace CGoGN