gmap1.hpp 8.27 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
{
Pierre Kraemer's avatar
Pierre Kraemer committed
74
	return MAP::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 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
{
Pierre Kraemer's avatar
Pierre Kraemer committed
146
	MAP::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
{
Pierre Kraemer's avatar
Pierre Kraemer committed
152
	MAP::involutionUnsew<1>(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
153 154 155
}

/*! @name Topological Operators
156
 *  Topological operations on 1-G-maps
Pierre Kraemer's avatar
Pierre Kraemer committed
157 158
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
159 160
template <class MAP>
inline Dart GMap1<MAP>::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
161
{
Pierre Kraemer's avatar
Pierre Kraemer committed
162 163 164
	Dart dd = this->beta0(d) ;
	Dart e = this->newDart();
	Dart f = this->newDart();
Pierre Kraemer's avatar
Pierre Kraemer committed
165
	beta1sew(e, f) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
166 167 168
	this->beta0unsew(d) ;
	this->beta0sew(e, d) ;
	this->beta0sew(f, dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
169

Pierre Kraemer's avatar
Pierre Kraemer committed
170
	if (this->isBoundaryMarked2(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
171
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
172 173
		this->boundaryMark2(e);
		this->boundaryMark2(f);
Pierre Kraemer's avatar
Pierre Kraemer committed
174
	}
175

Pierre Kraemer's avatar
Pierre Kraemer committed
176
	if (this->isBoundaryMarked3(d))
177
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
178 179
		this->boundaryMark3(e);
		this->boundaryMark3(f);
180 181
	}

182
	return f ;
Pierre Kraemer's avatar
Pierre Kraemer committed
183 184
}

Pierre Kraemer's avatar
Pierre Kraemer committed
185 186
template <class MAP>
inline void GMap1<MAP>::uncutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
187
{
Pierre Kraemer's avatar
Pierre Kraemer committed
188
	Dart d0 = this->beta0(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
189
	Dart d1 = phi1(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
190 191 192 193 194 195
	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
196 197
}

Pierre Kraemer's avatar
Pierre Kraemer committed
198 199
template <class MAP>
inline void GMap1<MAP>::collapseEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
200 201
{
	Dart d1 = beta1(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
202
	Dart dd = this->beta0(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
203 204 205 206
	Dart dd1 = beta1(dd) ;
	beta1unsew(d) ;
	beta1unsew(dd) ;
	beta1sew(d1, dd1) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
207
	this->deleteEdge(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
208 209
}

Pierre Kraemer's avatar
Pierre Kraemer committed
210 211
template <class MAP>
inline void GMap1<MAP>::splitCycle(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
212
{
213
	assert(d != e && sameCycle(d, e)) ;
214

215
	if(!sameOrientedCycle(d, e))
216
		e = beta1(e) ;
217

Pierre Kraemer's avatar
Pierre Kraemer committed
218 219 220 221
	Dart d1 = beta1(d) ;
	Dart e1 = beta1(e) ;
	beta1unsew(d) ;
	beta1unsew(e) ;
222 223
	beta1sew(d, e1) ;
	beta1sew(e, d1) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
224 225
}

Pierre Kraemer's avatar
Pierre Kraemer committed
226 227
template <class MAP>
inline void GMap1<MAP>::mergeCycles(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
228
{
229
	assert(!sameCycle(d, e)) ;
230

Pierre Kraemer's avatar
Pierre Kraemer committed
231 232 233 234
	Dart d1 = beta1(d) ;
	Dart e1 = beta1(e) ;
	beta1unsew(d) ;
	beta1unsew(e) ;
235 236 237 238
	beta1sew(d, e1) ;
	beta1sew(e, d1) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
239 240
template <class MAP>
inline void GMap1<MAP>::linkCycles(Dart d, Dart e)
241
{
242
	assert(d != e && !sameCycle(d, e)) ;
243 244
	Dart d1 = beta1(d) ;
	Dart e1 = beta1(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
245 246
	Dart dd = this->newEdge() ;
	Dart ee = this->newEdge() ;
247 248 249
	beta1unsew(d) ;
	beta1unsew(e) ;
	beta1sew(d, dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
250
	beta1sew(e1, this->beta0(dd)) ;
251
	beta1sew(e, ee) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
252
	beta1sew(d1, this->beta0(ee)) ;
253 254 255 256 257 258
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
259 260
template <class MAP>
inline bool GMap1<MAP>::sameOrientedCycle(Dart d, Dart e) const
261 262 263 264 265 266 267 268 269 270 271
{
	Dart it = d ;
	do
	{
		if (it == e)
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
272 273
template <class MAP>
inline bool GMap1<MAP>::sameCycle(Dart d, Dart e) const
274 275 276 277 278 279
{
	Dart it = d ;
	do
	{
		if (it == e)
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
280
		it = this->beta0(it);
281 282 283 284 285 286 287
		if (it == e)
			return true ;
		it = beta1(it) ;
	} while (it != d) ;
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
288 289
template <class MAP>
inline unsigned int GMap1<MAP>::cycleDegree(Dart d) const
290 291 292 293 294 295 296 297 298 299 300
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
	{
		++count ;
		it = phi1(it) ;
	} while (it != d) ;
	return count ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
301 302
template <class MAP>
inline int GMap1<MAP>::checkCycleDegree(Dart d, unsigned int degree) const
303 304 305 306 307 308 309 310 311 312 313 314
{
	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
315 316
template <class MAP>
inline bool GMap1<MAP>::isCycleTriangle(Dart d) const
317 318
{
	return (phi1(d) != d) && (phi1(phi1(phi1(d))) == d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
319 320 321 322 323 324
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
325 326
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
327 328 329 330 331 332 333
{
	if (f(d)) return true;
	Dart d1 = beta1(d);
	if (d1 != d) return f(d1);
	return false;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
334 335
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
336 337
{
	if (f(d)) return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
338
	Dart d1 = this->beta0(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
339 340 341 342
	if (d1 != d) return f(d1);
	return false;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
343 344
template <class MAP>
inline bool GMap1<MAP>::foreach_dart_of_oriented_cc(Dart d, FunctorType& f, unsigned int /*thread*/) const
345 346 347 348 349 350 351 352 353 354 355
{
	Dart it = d ;
	do
	{
		if (f(it))
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
356 357
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
358
{
Pierre Kraemer's avatar
Pierre Kraemer committed
359
	return GMap1::foreach_dart_of_oriented_cc(d, f, thread) || GMap1::foreach_dart_of_oriented_cc(this->beta0(d), f, thread) ;
360 361
}

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