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
{

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
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";
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
52 53
template <class MAP>
inline void GMap1<MAP>::clear(bool removeAttrib)
54
{
Pierre Kraemer's avatar
Pierre Kraemer committed
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 61
template <class MAP>
inline void GMap1<MAP>::update_topo_shortcuts()
Sylvain Thery's avatar
Sylvain Thery committed
62
{
Pierre Kraemer's avatar
Pierre Kraemer committed
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
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
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
}

Pierre Kraemer's avatar
Pierre Kraemer committed
77
template <class MAP>
Pierre Kraemer's avatar
Pierre Kraemer committed
78
template <int N>
Pierre Kraemer's avatar
Pierre Kraemer committed
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)
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
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)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
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
	}
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
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
}

Pierre Kraemer's avatar
Pierre Kraemer committed
111
template <class MAP>
Pierre Kraemer's avatar
Pierre Kraemer committed
112
template <int N>
Pierre Kraemer's avatar
Pierre Kraemer committed
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 ;
	}
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
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
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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
 *************************************************************************/

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

Pierre Kraemer's avatar
Pierre Kraemer committed
204
	if (this->isBoundaryMarked2(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
205
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
206 207
		this->boundaryMark2(e);
		this->boundaryMark2(f);
Pierre Kraemer's avatar
Pierre Kraemer committed
208
	}
209

Pierre Kraemer's avatar
Pierre Kraemer committed
210
	if (this->isBoundaryMarked3(d))
211
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
212 213
		this->boundaryMark3(e);
		this->boundaryMark3(f);
214 215
	}

216
	return f ;
Pierre Kraemer's avatar
Pierre Kraemer committed
217 218
}

Pierre Kraemer's avatar
Pierre Kraemer committed
219 220
template <class MAP>
inline void GMap1<MAP>::uncutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
221
{
Pierre Kraemer's avatar
Pierre Kraemer committed
222
	Dart d0 = this->beta0(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
223
	Dart d1 = phi1(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
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
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
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) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
241
	this->deleteEdge(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
242 243
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
279 280
	Dart dd = this->newEdge() ;
	Dart ee = this->newEdge() ;
281 282 283
	beta1unsew(d) ;
	beta1unsew(e) ;
	beta1sew(d, dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
284
	beta1sew(e1, this->beta0(dd)) ;
285
	beta1sew(e, ee) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
286
	beta1sew(d1, this->beta0(ee)) ;
287 288 289 290 291 292
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
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 ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
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 ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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 ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
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;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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;
Pierre Kraemer's avatar
Pierre Kraemer committed
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;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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 ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
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
{
Pierre Kraemer's avatar
Pierre Kraemer committed
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