map1.hpp 8.33 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
28
29
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

namespace CGoGN
{

/// INLINE FUNCTIONS

Pierre Kraemer's avatar
Pierre Kraemer committed
30
31
template <typename MAP_IMPL>
inline void Map1<MAP_IMPL>::init()
Pierre Kraemer's avatar
Pierre Kraemer committed
32
{
Pierre Kraemer's avatar
Pierre Kraemer committed
33
	MAP_IMPL::addPermutation() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
34
35
}

Pierre Kraemer's avatar
Pierre Kraemer committed
36
37
template <typename MAP_IMPL>
inline Map1<MAP_IMPL>::Map1() : MapCommon<MAP_IMPL>()
38
39
40
41
{
	init() ;
}

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

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
62
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
63
inline unsigned int Map1<MAP_IMPL>::getNbInvolutions() const
Sylvain Thery's avatar
Sylvain Thery committed
64
{
Pierre Kraemer's avatar
Pierre Kraemer committed
65
66
67
68
69
70
71
	return 0;
}

template <typename MAP_IMPL>
inline unsigned int Map1<MAP_IMPL>::getNbPermutations() const
{
	return 1;
Sylvain Thery's avatar
Sylvain Thery committed
72
73
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
78
79
template <typename MAP_IMPL>
inline Dart Map1<MAP_IMPL>::phi1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
80
{
Pierre Kraemer's avatar
Pierre Kraemer committed
81
	return MAP_IMPL::template getPermutation<0>(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
82
83
}

Pierre Kraemer's avatar
Pierre Kraemer committed
84
85
template <typename MAP_IMPL>
inline Dart Map1<MAP_IMPL>::phi_1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
86
{
Pierre Kraemer's avatar
Pierre Kraemer committed
87
	return MAP_IMPL::template getPermutationInv<0>(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
88
89
}

Pierre Kraemer's avatar
Pierre Kraemer committed
90
template <typename MAP_IMPL>
Pierre Kraemer's avatar
Pierre Kraemer committed
91
template <int N>
Pierre Kraemer's avatar
Pierre Kraemer committed
92
inline Dart Map1<MAP_IMPL>::phi(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
{
	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
110
111
template <typename MAP_IMPL>
inline Dart Map1<MAP_IMPL>::alpha1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
112
113
114
115
{
	return phi1(d) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
116
117
template <typename MAP_IMPL>
inline Dart Map1<MAP_IMPL>::alpha_1(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
118
119
120
121
{
	return phi_1(d) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
122
123
template <typename MAP_IMPL>
inline void Map1<MAP_IMPL>::phi1sew(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
124
{
Pierre Kraemer's avatar
Pierre Kraemer committed
125
	MAP_IMPL::template permutationSew<0>(d,e);
Pierre Kraemer's avatar
Pierre Kraemer committed
126
127
}

Pierre Kraemer's avatar
Pierre Kraemer committed
128
129
template <typename MAP_IMPL>
inline void Map1<MAP_IMPL>::phi1unsew(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
130
{
Pierre Kraemer's avatar
Pierre Kraemer committed
131
	MAP_IMPL::template permutationUnsew<0>(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
132
133
}

134
135
136
137
/*! @name Generator and Deletor
 *  To generate or delete faces in a 1-map
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
138
139
template <typename MAP_IMPL>
Dart Map1<MAP_IMPL>::newCycle(unsigned int nbEdges)
140
141
142
143
{
	assert(nbEdges > 0 || !"Cannot create a face with no edge") ;
	Dart d = this->newDart() ;	// Create the first edge
	for (unsigned int i = 1 ; i < nbEdges ; ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
144
		Map1<MAP_IMPL>::cutEdge(d) ;		// Subdivide nbEdges-1 times this edge
145
146
147
	return d ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
148
149
template <typename MAP_IMPL>
void Map1<MAP_IMPL>::deleteCycle(Dart d)
150
151
152
153
154
155
156
157
158
159
160
{
	Dart e = phi1(d) ;
	while (e != d)
	{
		Dart f = phi1(e) ;
		this->deleteDart(e) ;
		e = f ;
	}
	this->deleteDart(d) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
161
162
163
164
/*! @name Topological Operators
 *  Topological operations on 1-maps
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
165
166
template <typename MAP_IMPL>
inline Dart Map1<MAP_IMPL>::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
167
{
168
	Dart e = this->newDart() ;	// Create a new dart
169
	phi1sew(d, e) ;				// Insert dart e between d and phi1(d)
Sylvain Thery's avatar
Sylvain Thery committed
170

Pierre Kraemer's avatar
Pierre Kraemer committed
171
172
	if (this->template isBoundaryMarked<2>(d))
		this->template boundaryMark<2>(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
173

Pierre Kraemer's avatar
Pierre Kraemer committed
174
175
	if (this->template isBoundaryMarked<3>(d))
		this->template boundaryMark<3>(e);
176

Pierre Kraemer's avatar
Pierre Kraemer committed
177
	return e ;
Pierre Kraemer's avatar
Pierre Kraemer committed
178
179
}

Pierre Kraemer's avatar
Pierre Kraemer committed
180
181
template <typename MAP_IMPL>
inline void Map1<MAP_IMPL>::uncutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
182
183
{
	Dart d1 = phi1(d) ;
184
	phi1unsew(d) ;			// Dart d is linked to the successor of its successor
185
	this->deleteDart(d1) ;	// Dart d1 is erased
Pierre Kraemer's avatar
Pierre Kraemer committed
186
187
}

Pierre Kraemer's avatar
Pierre Kraemer committed
188
189
template <typename MAP_IMPL>
inline void Map1<MAP_IMPL>::collapseEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
190
191
{
	phi1unsew(phi_1(d)) ;	// Dart before d is linked to its successor
192
	this->deleteDart(d) ;	// Dart d is erased
Pierre Kraemer's avatar
Pierre Kraemer committed
193
194
}

Pierre Kraemer's avatar
Pierre Kraemer committed
195
196
template <typename MAP_IMPL>
inline void Map1<MAP_IMPL>::splitCycle(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
197
{
198
199
	assert(d != e && sameCycle(d, e)) ;
	phi1sew(phi_1(d), phi_1(e)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
200
201
}

Pierre Kraemer's avatar
Pierre Kraemer committed
202
203
template <typename MAP_IMPL>
inline void Map1<MAP_IMPL>::mergeCycles(Dart d, Dart e)
Thomas's avatar
Thomas committed
204
{
205
206
	assert(!sameCycle(d, e)) ;
	phi1sew(phi_1(d), phi_1(e)) ;
Thomas's avatar
Thomas committed
207
208
}

Pierre Kraemer's avatar
Pierre Kraemer committed
209
210
template <typename MAP_IMPL>
inline void Map1<MAP_IMPL>::linkCycles(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
211
{
212
	assert(d != e && !sameCycle(d, e)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
213
214
	Map1<MAP_IMPL>::cutEdge(phi_1(d));		// cut the edge before d (insert a new dart before d)
	Map1<MAP_IMPL>::cutEdge(phi_1(e));		// cut the edge before e (insert a new dart before e)
215
	phi1sew(phi_1(d), phi_1(e)) ;	// phi1sew between the 2 new inserted darts
Pierre Kraemer's avatar
Pierre Kraemer committed
216
217
}

Pierre Kraemer's avatar
Pierre Kraemer committed
218
219
template <typename MAP_IMPL>
void Map1<MAP_IMPL>::reverseCycle(Dart d)
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
{
	Dart e = phi1(d) ;			// Dart e is the first edge of the new face
	if (e == d) return ;		// Only one edge: nothing to do
	if (phi1(e) == d) return ;	// Only two edges: nothing to do

	phi1unsew(d) ;				// Detach e from the face of d

	Dart dNext = phi1(d) ;		// While the face of d contains more than two edges
	while (dNext != d)
	{
		phi1unsew(d) ;			// Unsew the edge after d
		phi1sew(e, dNext) ;		// Sew it after e (thus in reverse order)
		dNext = phi1(d) ;
	}
	phi1sew(e, d) ;				// Sew the last edge
}

Pierre Kraemer's avatar
Pierre Kraemer committed
237
238
239
240
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
241
242
template <typename MAP_IMPL>
inline bool Map1<MAP_IMPL>::sameCycle(Dart d, Dart e) const
Pierre Kraemer's avatar
Pierre Kraemer committed
243
{
244
245
246
247
248
249
250
251
252
253
	Dart it = d ;
	do
	{
		if(it == e)
			return true ;
		it = phi1(it) ;
	} while(it != d) ;
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
254
255
template <typename MAP_IMPL>
inline unsigned int Map1<MAP_IMPL>::cycleDegree(Dart d) const
256
257
258
259
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
260
    {
261
262
263
264
265
266
		++count ;
		it = phi1(it) ;
	} while (it != d) ;
	return count ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
267
268
template <typename MAP_IMPL>
inline int Map1<MAP_IMPL>::checkCycleDegree(Dart d, unsigned int degree) const
269
270
271
272
273
274
275
276
277
278
279
280
{
	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
281
282
template <typename MAP_IMPL>
inline bool Map1<MAP_IMPL>::isCycleTriangle(Dart d) const
283
284
{
	return (phi1(d) != d) && (phi1(phi1(phi1(d))) == d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
285
286
287
288
289
290
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
291
292
template <typename MAP_IMPL>
inline bool Map1<MAP_IMPL>::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int /*thread*/) const
Pierre Kraemer's avatar
Pierre Kraemer committed
293
294
295
296
{
	return f(d) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
297
298
template <typename MAP_IMPL>
inline bool Map1<MAP_IMPL>::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int /*thread*/) const
Pierre Kraemer's avatar
Pierre Kraemer committed
299
300
301
302
{
	return f(d) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
303
304
template <typename MAP_IMPL>
inline bool Map1<MAP_IMPL>::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int /*thread*/) const
305
306
307
308
309
310
311
312
313
314
315
{
	Dart it = d ;
	do
	{
		if (f(it))
			return true ;
		it = phi1(it) ;
	} while (it != d) ;
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
316
317

} // namespace CGoGN