gmap1.hpp 9.72 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
{

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

Pierre Kraemer's avatar
Pierre Kraemer committed
34 35
template <typename MAP_IMPL>
inline GMap1<MAP_IMPL>::GMap1() : GMap0<MAP_IMPL>()
36 37 38 39
{
	init() ;
}

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

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
60
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
61
inline unsigned int GMap1<MAP_IMPL>::getNbInvolutions() const
Sylvain Thery's avatar
Sylvain Thery committed
62
{
Pierre Kraemer's avatar
Pierre Kraemer committed
63 64 65 66 67 68 69
	return 1 + ParentMap::getNbInvolutions();
}

template <typename MAP_IMPL>
inline unsigned int GMap1<MAP_IMPL>::getNbPermutations() const
{
	return ParentMap::getNbPermutations();
Sylvain Thery's avatar
Sylvain Thery committed
70 71
}

Pierre Kraemer's avatar
Pierre Kraemer committed
72 73 74 75
/*! @name Basic Topological Operators
 * Access and Modification
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
76 77
template <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::beta1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
78
{
Pierre Kraemer's avatar
Pierre Kraemer committed
79
	return MAP_IMPL::template getInvolution<1>(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
80 81
}

Pierre Kraemer's avatar
Pierre Kraemer committed
82
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
83
template <int N>
Pierre Kraemer's avatar
Pierre Kraemer committed
84
inline Dart GMap1<MAP_IMPL>::beta(const Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
85 86 87 88 89 90
{
	assert( (N > 0) || !"negative parameters not allowed in template multi-beta");
	if (N<10)
	{
		switch(N)
		{
91 92 93
			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
94 95 96 97
		}
	}
	switch(N%10)
	{
98 99 100
		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
101 102 103
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
104 105
template <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::phi1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
106
{
107
	return beta1(this->beta0(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
108 109
}

Pierre Kraemer's avatar
Pierre Kraemer committed
110 111
template <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::phi_1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
112
{
113
	return this->beta0(beta1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
114 115
}

Pierre Kraemer's avatar
Pierre Kraemer committed
116
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
117
template <int N>
Pierre Kraemer's avatar
Pierre Kraemer committed
118
inline Dart GMap1<MAP_IMPL>::phi(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
{
	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 ;
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
136 137
template <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::alpha1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
138
{
139
	return beta1(this->beta0(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
140 141
}

Pierre Kraemer's avatar
Pierre Kraemer committed
142 143
template <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::alpha_1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
144
{
145
	return beta0(beta1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
146 147
}

Pierre Kraemer's avatar
Pierre Kraemer committed
148 149
template <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::beta1sew(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
150
{
Pierre Kraemer's avatar
Pierre Kraemer committed
151
	MAP_IMPL::template involutionSew<1>(d,e);
Pierre Kraemer's avatar
Pierre Kraemer committed
152 153
}

Pierre Kraemer's avatar
Pierre Kraemer committed
154 155
template <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::beta1unsew(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
156
{
Pierre Kraemer's avatar
Pierre Kraemer committed
157
	MAP_IMPL::template involutionUnsew<1>(d);
158 159 160 161 162 163
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
164 165
template <typename MAP_IMPL>
Dart GMap1<MAP_IMPL>::newCycle(unsigned int nbEdges)
166 167 168 169 170 171 172 173 174 175 176 177 178 179 180
{
	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;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
181 182
template <typename MAP_IMPL>
void GMap1<MAP_IMPL>::deleteCycle(Dart d)
183 184 185 186 187 188 189 190 191
{
	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
192 193 194
}

/*! @name Topological Operators
195
 *  Topological operations on 1-G-maps
Pierre Kraemer's avatar
Pierre Kraemer committed
196 197
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
198 199
template <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
200
{
201 202 203
	Dart dd = this->beta0(d) ;
	Dart e = this->newDart();
	Dart f = this->newDart();
204
	beta1sew(e, f) ;
205 206 207
	this->beta0unsew(d) ;
	this->beta0sew(e, d) ;
	this->beta0sew(f, dd) ;
208

Pierre Kraemer's avatar
Pierre Kraemer committed
209
	if (this->template isBoundaryMarked<2>(d))
210
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
211 212
		this->template boundaryMark<2>(e);
		this->template boundaryMark<2>(f);
213
	}
214

Pierre Kraemer's avatar
Pierre Kraemer committed
215
	if (this->template isBoundaryMarked<3>(d))
216
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
217 218
		this->template boundaryMark<3>(e);
		this->template boundaryMark<3>(f);
219 220
	}

221
	return f ;
222 223
}

Pierre Kraemer's avatar
Pierre Kraemer committed
224 225
template <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::uncutEdge(Dart d)
226
{
227
	Dart d0 = this->beta0(d) ;
228
	Dart d1 = phi1(d) ;
229 230 231 232 233 234
	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
235 236
}

Pierre Kraemer's avatar
Pierre Kraemer committed
237 238
template <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::collapseEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
239 240
{
	Dart d1 = beta1(d) ;
241
	Dart dd = this->beta0(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
242 243 244 245
	Dart dd1 = beta1(dd) ;
	beta1unsew(d) ;
	beta1unsew(dd) ;
	beta1sew(d1, dd1) ;
246
	this->deleteEdge(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
247 248
}

Pierre Kraemer's avatar
Pierre Kraemer committed
249 250
template <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::splitCycle(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
251
{
252
	assert(d != e && sameCycle(d, e)) ;
253

254
	if(!sameOrientedCycle(d, e))
255
		e = beta1(e) ;
256

Pierre Kraemer's avatar
Pierre Kraemer committed
257 258 259 260
	Dart d1 = beta1(d) ;
	Dart e1 = beta1(e) ;
	beta1unsew(d) ;
	beta1unsew(e) ;
261 262
	beta1sew(d, e1) ;
	beta1sew(e, d1) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
263 264
}

Pierre Kraemer's avatar
Pierre Kraemer committed
265 266
template <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::mergeCycles(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
267
{
268
	assert(!sameCycle(d, e)) ;
269

Pierre Kraemer's avatar
Pierre Kraemer committed
270 271 272 273
	Dart d1 = beta1(d) ;
	Dart e1 = beta1(e) ;
	beta1unsew(d) ;
	beta1unsew(e) ;
274 275 276 277
	beta1sew(d, e1) ;
	beta1sew(e, d1) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
278 279
template <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::linkCycles(Dart d, Dart e)
280
{
281
	assert(d != e && !sameCycle(d, e)) ;
282 283
	Dart d1 = beta1(d) ;
	Dart e1 = beta1(e) ;
284 285
	Dart dd = this->newEdge() ;
	Dart ee = this->newEdge() ;
286 287 288
	beta1unsew(d) ;
	beta1unsew(e) ;
	beta1sew(d, dd) ;
289
	beta1sew(e1, this->beta0(dd)) ;
290
	beta1sew(e, ee) ;
291
	beta1sew(d1, this->beta0(ee)) ;
292 293 294 295 296 297
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
298 299
template <typename MAP_IMPL>
inline bool GMap1<MAP_IMPL>::sameOrientedCycle(Dart d, Dart e) const
300 301 302 303 304 305 306 307 308 309 310
{
	Dart it = d ;
	do
	{
		if (it == e)
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
311 312
template <typename MAP_IMPL>
inline bool GMap1<MAP_IMPL>::sameCycle(Dart d, Dart e) const
313 314 315 316 317 318
{
	Dart it = d ;
	do
	{
		if (it == e)
			return true ;
319
		it = this->beta0(it);
320 321 322 323 324 325 326
		if (it == e)
			return true ;
		it = beta1(it) ;
	} while (it != d) ;
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
327 328
template <typename MAP_IMPL>
inline unsigned int GMap1<MAP_IMPL>::cycleDegree(Dart d) const
329 330 331 332 333 334 335 336 337 338 339
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
	{
		++count ;
		it = phi1(it) ;
	} while (it != d) ;
	return count ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
340 341
template <typename MAP_IMPL>
inline int GMap1<MAP_IMPL>::checkCycleDegree(Dart d, unsigned int degree) const
342 343 344 345 346 347 348 349 350 351 352 353
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
	{
		++count ;
		it = phi1(it) ;
	} while ((count<=degree) && (it != d)) ;

	return count-degree;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
354 355
template <typename MAP_IMPL>
inline bool GMap1<MAP_IMPL>::isCycleTriangle(Dart d) const
356 357
{
	return (phi1(d) != d) && (phi1(phi1(phi1(d))) == d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
358 359 360 361 362 363
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
364 365
template <typename MAP_IMPL>
inline bool GMap1<MAP_IMPL>::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int /*thread*/) const
Pierre Kraemer's avatar
Pierre Kraemer committed
366 367 368 369 370 371 372
{
	if (f(d)) return true;
	Dart d1 = beta1(d);
	if (d1 != d) return f(d1);
	return false;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
373 374
template <typename MAP_IMPL>
inline bool GMap1<MAP_IMPL>::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int /*thread*/) const
Pierre Kraemer's avatar
Pierre Kraemer committed
375 376
{
	if (f(d)) return true;
377
	Dart d1 = this->beta0(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
378 379 380 381
	if (d1 != d) return f(d1);
	return false;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
382 383
template <typename MAP_IMPL>
inline bool GMap1<MAP_IMPL>::foreach_dart_of_oriented_cc(Dart d, FunctorType& f, unsigned int /*thread*/) const
384 385 386 387 388 389 390 391 392 393 394
{
	Dart it = d ;
	do
	{
		if (f(it))
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
395 396
template <typename MAP_IMPL>
inline bool GMap1<MAP_IMPL>::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread) const
Sylvain Thery's avatar
Sylvain Thery committed
397
{
Pierre Kraemer's avatar
Pierre Kraemer committed
398
	return GMap1<MAP_IMPL>::foreach_dart_of_oriented_cc(d, f, thread) || GMap1::foreach_dart_of_oriented_cc(this->beta0(d), f, thread) ;
399 400
}

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