gmap1.hpp 9.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-2012, 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.unistra.fr/                                           *
Pierre Kraemer's avatar
Pierre Kraemer committed
21 22 23 24 25 26 27
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

namespace CGoGN
{

28 29
template <class MAP>
inline void GMap1<MAP>::init()
Pierre Kraemer's avatar
Pierre Kraemer committed
30
{
31
	MAP::addInvolution() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
32 33
}

34 35
template <class MAP>
inline GMap1<MAP>::GMap1() : GMap0<MAP>()
36 37 38 39
{
	init() ;
}

40 41
template <class MAP>
inline std::string GMap1<MAP>::mapTypeName() const
Pierre Kraemer's avatar
Pierre Kraemer committed
42 43 44 45
{
	return "GMap1";
}

46 47
template <class MAP>
inline unsigned int GMap1<MAP>::dimension() const
Pierre Kraemer's avatar
Pierre Kraemer committed
48 49 50 51
{
	return 1;
}

52 53
template <class MAP>
inline void GMap1<MAP>::clear(bool removeAttrib)
54
{
55
	ParentMap::clear(removeAttrib) ;
Sylvain Thery's avatar
Sylvain Thery committed
56 57
	if (removeAttrib)
		init() ;
58 59
}

60 61
template <class MAP>
inline void GMap1<MAP>::update_topo_shortcuts()
Sylvain Thery's avatar
Sylvain Thery committed
62
{
63 64
	ParentMap::update_topo_shortcuts();
//	m_beta1 = getRelation("beta1");
Sylvain Thery's avatar
Sylvain Thery committed
65 66
}

Pierre Kraemer's avatar
Pierre Kraemer committed
67 68 69 70
/*! @name Basic Topological Operators
 * Access and Modification
 *************************************************************************/

71 72
template <class MAP>
inline Dart GMap1<MAP>::beta1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
73
{
74
	return MAP::template getInvolution<1>(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
75 76
}

77
template <class MAP>
Pierre Kraemer's avatar
Pierre Kraemer committed
78
template <int N>
79
inline Dart GMap1<MAP>::beta(const Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
80 81 82 83 84 85
{
	assert( (N > 0) || !"negative parameters not allowed in template multi-beta");
	if (N<10)
	{
		switch(N)
		{
86 87 88
			case 0 : return this->beta0(d) ;
			case 1 : return beta1(d) ;
			default : assert(!"Wrong multi-beta relation value") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
89 90 91 92
		}
	}
	switch(N%10)
	{
93 94 95
		case 0 : return beta0(beta<N/10>(d)) ;
		case 1 : return beta1(beta<N/10>(d)) ;
		default : assert(!"Wrong multi-beta relation value") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
96 97 98
	}
}

99 100
template <class MAP>
inline Dart GMap1<MAP>::phi1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
101
{
102
	return beta1(this->beta0(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
103 104
}

105 106
template <class MAP>
inline Dart GMap1<MAP>::phi_1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
107
{
108
	return this->beta0(beta1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
109 110
}

111
template <class MAP>
Pierre Kraemer's avatar
Pierre Kraemer committed
112
template <int N>
113
inline Dart GMap1<MAP>::phi(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
{
	assert((N > 0) || !"negative parameters not allowed in template multi-phi");
	if (N < 10)
	{
		switch(N)
		{
		case 1 : return phi1(d) ;
		default : assert(!"Wrong multi-phi relation value") ; return d ;
		}
	}
	switch(N%10)
	{
	case 1 : return phi1(phi<N/10>(d)) ;
	default : assert(!"Wrong multi-phi relation value") ; return d ;
	}
}

131 132
template <class MAP>
inline Dart GMap1<MAP>::alpha1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
133
{
134
	return beta1(this->beta0(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
135 136
}

137 138
template <class MAP>
inline Dart GMap1<MAP>::alpha_1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
139
{
140
	return beta0(beta1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
141 142
}

143 144
template <class MAP>
inline void GMap1<MAP>::beta1sew(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
145
{
146
	MAP::template involutionSew<1>(d,e);
Pierre Kraemer's avatar
Pierre Kraemer committed
147 148
}

149 150
template <class MAP>
inline void GMap1<MAP>::beta1unsew(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
151
{
152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186
	MAP::template involutionUnsew<1>(d);
}

/*! @name Constructors and Destructors
 *  To generate or delete faces in a 1-G-map
 *************************************************************************/

template <class MAP>
Dart GMap1<MAP>::newCycle(unsigned int nbEdges)
{
	assert(nbEdges > 0 || !"Cannot create a face with no edge") ;

	Dart d0 = ParentMap::newEdge();	// create the first edge
	Dart dp = this->beta0(d0);		// store an extremity
	for (unsigned int i = 1; i < nbEdges; ++i)
	{
		Dart di = ParentMap::newEdge();	// create the next edge
		beta1sew(dp,di);
		dp = this->beta0(di);	// change the preceding
	}
	beta1sew(dp,d0);	// sew the last with the first
	return d0;
}

template <class MAP>
void GMap1<MAP>::deleteCycle(Dart d)
{
	Dart e = phi1(d);
	while (e != d)
	{
		Dart f = phi1(e);
		this->deleteEdge(e);
		e = f;
	}
	this->deleteEdge(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
187 188 189
}

/*! @name Topological Operators
190
 *  Topological operations on 1-G-maps
Pierre Kraemer's avatar
Pierre Kraemer committed
191 192
 *************************************************************************/

193 194
template <class MAP>
inline Dart GMap1<MAP>::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
195
{
196 197 198
	Dart dd = this->beta0(d) ;
	Dart e = this->newDart();
	Dart f = this->newDart();
199
	beta1sew(e, f) ;
200 201 202
	this->beta0unsew(d) ;
	this->beta0sew(e, d) ;
	this->beta0sew(f, dd) ;
203

204
	if (this->isBoundaryMarked2(d))
205
	{
206 207
		this->boundaryMark2(e);
		this->boundaryMark2(f);
208
	}
209

210
	if (this->isBoundaryMarked3(d))
211
	{
212 213
		this->boundaryMark3(e);
		this->boundaryMark3(f);
214 215
	}

216
	return f ;
217 218
}

219 220
template <class MAP>
inline void GMap1<MAP>::uncutEdge(Dart d)
221
{
222
	Dart d0 = this->beta0(d) ;
223
	Dart d1 = phi1(d) ;
224 225 226 227 228 229
	Dart d10 = this->beta0(d1) ;
	this->beta0unsew(d) ;
	this->beta0unsew(d10) ;
	this->beta0sew(d, d10) ;
	this->deleteDart(d0) ;
	this->deleteDart(d1) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
230 231
}

232 233
template <class MAP>
inline void GMap1<MAP>::collapseEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
234 235
{
	Dart d1 = beta1(d) ;
236
	Dart dd = this->beta0(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
237 238 239 240
	Dart dd1 = beta1(dd) ;
	beta1unsew(d) ;
	beta1unsew(dd) ;
	beta1sew(d1, dd1) ;
241
	this->deleteEdge(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
242 243
}

244 245
template <class MAP>
inline void GMap1<MAP>::splitCycle(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
246
{
247
	assert(d != e && sameCycle(d, e)) ;
248

249
	if(!sameOrientedCycle(d, e))
250
		e = beta1(e) ;
251

Pierre Kraemer's avatar
Pierre Kraemer committed
252 253 254 255
	Dart d1 = beta1(d) ;
	Dart e1 = beta1(e) ;
	beta1unsew(d) ;
	beta1unsew(e) ;
256 257
	beta1sew(d, e1) ;
	beta1sew(e, d1) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
258 259
}

260 261
template <class MAP>
inline void GMap1<MAP>::mergeCycles(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
262
{
263
	assert(!sameCycle(d, e)) ;
264

Pierre Kraemer's avatar
Pierre Kraemer committed
265 266 267 268
	Dart d1 = beta1(d) ;
	Dart e1 = beta1(e) ;
	beta1unsew(d) ;
	beta1unsew(e) ;
269 270 271 272
	beta1sew(d, e1) ;
	beta1sew(e, d1) ;
}

273 274
template <class MAP>
inline void GMap1<MAP>::linkCycles(Dart d, Dart e)
275
{
276
	assert(d != e && !sameCycle(d, e)) ;
277 278
	Dart d1 = beta1(d) ;
	Dart e1 = beta1(e) ;
279 280
	Dart dd = this->newEdge() ;
	Dart ee = this->newEdge() ;
281 282 283
	beta1unsew(d) ;
	beta1unsew(e) ;
	beta1sew(d, dd) ;
284
	beta1sew(e1, this->beta0(dd)) ;
285
	beta1sew(e, ee) ;
286
	beta1sew(d1, this->beta0(ee)) ;
287 288 289 290 291 292
}

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

293 294
template <class MAP>
inline bool GMap1<MAP>::sameOrientedCycle(Dart d, Dart e) const
295 296 297 298 299 300 301 302 303 304 305
{
	Dart it = d ;
	do
	{
		if (it == e)
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

306 307
template <class MAP>
inline bool GMap1<MAP>::sameCycle(Dart d, Dart e) const
308 309 310 311 312 313
{
	Dart it = d ;
	do
	{
		if (it == e)
			return true ;
314
		it = this->beta0(it);
315 316 317 318 319 320 321
		if (it == e)
			return true ;
		it = beta1(it) ;
	} while (it != d) ;
	return false ;
}

322 323
template <class MAP>
inline unsigned int GMap1<MAP>::cycleDegree(Dart d) const
324 325 326 327 328 329 330 331 332 333 334
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
	{
		++count ;
		it = phi1(it) ;
	} while (it != d) ;
	return count ;
}

335 336
template <class MAP>
inline int GMap1<MAP>::checkCycleDegree(Dart d, unsigned int degree) const
337 338 339 340 341 342 343 344 345 346 347 348
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
	{
		++count ;
		it = phi1(it) ;
	} while ((count<=degree) && (it != d)) ;

	return count-degree;
}

349 350
template <class MAP>
inline bool GMap1<MAP>::isCycleTriangle(Dart d) const
351 352
{
	return (phi1(d) != d) && (phi1(phi1(phi1(d))) == d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
353 354 355 356 357 358
}

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

359 360
template <class MAP>
inline bool GMap1<MAP>::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int /*thread*/) const
Pierre Kraemer's avatar
Pierre Kraemer committed
361 362 363 364 365 366 367
{
	if (f(d)) return true;
	Dart d1 = beta1(d);
	if (d1 != d) return f(d1);
	return false;
}

368 369
template <class MAP>
inline bool GMap1<MAP>::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int /*thread*/) const
Pierre Kraemer's avatar
Pierre Kraemer committed
370 371
{
	if (f(d)) return true;
372
	Dart d1 = this->beta0(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
373 374 375 376
	if (d1 != d) return f(d1);
	return false;
}

377 378
template <class MAP>
inline bool GMap1<MAP>::foreach_dart_of_oriented_cc(Dart d, FunctorType& f, unsigned int /*thread*/) const
379 380 381 382 383 384 385 386 387 388 389
{
	Dart it = d ;
	do
	{
		if (f(it))
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

390 391
template <class MAP>
inline bool GMap1<MAP>::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread) const
Sylvain Thery's avatar
Sylvain Thery committed
392
{
393
	return GMap1::foreach_dart_of_oriented_cc(d, f, thread) || GMap1::foreach_dart_of_oriented_cc(this->beta0(d), f, thread) ;
394 395
}

Pierre Kraemer's avatar
Pierre Kraemer committed
396
} // namespace CGoGN