gmap1.hpp 9.61 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
{
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 <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::beta1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
73
{
Pierre Kraemer's avatar
Pierre Kraemer committed
74
	return MAP_IMPL::template getInvolution<1>(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
75 76
}

Pierre Kraemer's avatar
Pierre Kraemer committed
77
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
78
template <int N>
Pierre Kraemer's avatar
Pierre Kraemer committed
79
inline Dart GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
112
template <int N>
Pierre Kraemer's avatar
Pierre Kraemer committed
113
inline Dart GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::beta1sew(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
145
{
Pierre Kraemer's avatar
Pierre Kraemer committed
146
	MAP_IMPL::template involutionSew<1>(d,e);
Pierre Kraemer's avatar
Pierre Kraemer committed
147 148
}

Pierre Kraemer's avatar
Pierre Kraemer committed
149 150
template <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::beta1unsew(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
151
{
Pierre Kraemer's avatar
Pierre Kraemer committed
152
	MAP_IMPL::template involutionUnsew<1>(d);
153 154 155 156 157 158
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
159 160
template <typename MAP_IMPL>
Dart GMap1<MAP_IMPL>::newCycle(unsigned int nbEdges)
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
{
	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
176 177
template <typename MAP_IMPL>
void GMap1<MAP_IMPL>::deleteCycle(Dart d)
178 179 180 181 182 183 184 185 186
{
	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 <typename MAP_IMPL>
inline Dart GMap1<MAP_IMPL>::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->template isBoundaryMarked<2>(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
205
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
206 207
		this->template boundaryMark<2>(e);
		this->template boundaryMark<2>(f);
Pierre Kraemer's avatar
Pierre Kraemer committed
208
	}
209

Pierre Kraemer's avatar
Pierre Kraemer committed
210
	if (this->template isBoundaryMarked<3>(d))
211
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
212 213
		this->template boundaryMark<3>(e);
		this->template boundaryMark<3>(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 <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline void GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline bool GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline bool GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline unsigned int GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline int GMap1<MAP_IMPL>::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 <typename MAP_IMPL>
inline bool GMap1<MAP_IMPL>::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 <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
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 <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
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 <typename MAP_IMPL>
inline bool GMap1<MAP_IMPL>::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 <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
392
{
Pierre Kraemer's avatar
Pierre Kraemer committed
393
	return GMap1<MAP_IMPL>::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