Moka kernel
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
gmg-insertion.cc
Go to the documentation of this file.
1 /*
2  * lib-gmapkernel : Un noyau de 3-G-cartes et des opérations.
3  * Copyright (C) 2004, Moka Team, Université de Poitiers, Laboratoire SIC
4  * http://www.sic.sp2mi.univ-poitiers.fr/
5  * Copyright (C) 2009, Guillaume Damiand, CNRS, LIRIS,
6  * guillaume.damiand@liris.cnrs.fr, http://liris.cnrs.fr/
7  *
8  * This file is part of lib-gmapkernel
9  *
10  * This program is free software: you can redistribute it and/or modify
11  * it under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation, either version 3 of the License, or
13  * (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU Lesser General Public License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this program. If not, see <http://www.gnu.org/licenses/>.
22  */
23 
24 //******************************************************************************
25 #include "g-map-generic.hh"
26 using namespace std;
27 using namespace GMap3d;
28 //******************************************************************************
29 CDart * CGMapGeneric::insertVertex(CDart * ADart)
30 {
31  assert(ADart!=NULL);
32 
33  bool closed = !isFree0(ADart);
34  int treated = getNewMark();
35 
36  CDynamicCoverage23 it(this, ADart);
37 
38  for (; it.cont(); setMark(*it, treated), ++it)
39  {
40  CDart * d0 = alpha0(*it);
41  CDart * n1 = addMapDart();
42  CDart * n2 = addMapDart();
43 
44  linkAlpha0(*it, n1);
45  if (closed) linkAlpha0(d0 , n2);
46 
47  linkAlpha1(n1, n2);
48 
49  if (!isFree2(*it) && isMarked(alpha2(*it), treated))
50  {
51  linkAlpha2(n1, alpha20(*it));
52  linkAlpha2(n2, alpha21(n1 ));
53  }
54 
55  if (!isFree3(*it) && isMarked(alpha3(*it), treated))
56  {
57  linkAlpha3(n1, alpha30(*it));
58  linkAlpha3(n2, alpha31(n1 ));
59  }
60  }
61 
62  unmarkOrbit(ADart, ORBIT_23, treated);
63  freeMark(treated);
64 
65  return alpha0(ADart);
66 }
67 //******************************************************************************
68 int CGMapGeneric::insertVertexOnMarkedEdges(int AMarkNumber)
69 {
70  CDynamicCoverageAll it(this);
71  int nbInserted = 0;
72  int treated = getNewMark();
73 
74  for (; it.cont(); ++it)
75  if (!isMarked(*it, treated))
76  {
77  if (isMarked(*it, AMarkNumber))
78  {
79  markOrbit(*it, ORBIT_EDGE, treated);
80 
81  CDart * newVertex= insertVertex(*it);
82  markOrbit(newVertex, ORBIT_VERTEX, treated);
83  ++nbInserted;
84  }
85  else
86  setMark(*it, treated);
87  }
88 
89  negateMaskMark(treated);
90  freeMark(treated);
91 
92  return nbInserted;
93 }
94 //******************************************************************************
95 CDart * CGMapGeneric::insertEdge(CDart * ADart1, CDart * ADart2)
96 {
97  assert(ADart1!=NULL && ADart2!=NULL);
98 
99  // Première demi-face:
100  CDart * n1 = addMapDart();
101  CDart * n2 = addMapDart();
102 
103  linkAlpha0(n1,n2);
104 
105  CDart * dd1 = isFree1(ADart1) ? NULL : alpha1(ADart1);
106  CDart * dd2 = isFree1(ADart2) ? NULL : alpha1(ADart2);
107 
108  linkAlpha1(ADart1,n1); linkAlpha1(ADart2,n2);
109 
110  if (dd1!=NULL || dd2!=NULL)
111  {
112  CDart * nn1=addMapDart();
113  CDart * nn2=addMapDart();
114 
115  linkAlpha0(nn1,nn2);
116  linkAlpha2(n1,nn1); linkAlpha2(n2,nn2);
117 
118  if (dd1!=NULL) linkAlpha1(dd1,nn1);
119  if (dd2!=NULL) linkAlpha1(dd2,nn2);
120  }
121 
122  // Éventuellement, deuxième demi-face:
123  if (!isFree3(ADart1))
124  {
125  n1=addMapDart(); n2=addMapDart();
126  linkAlpha0(n1,n2);
127  linkAlpha3(n1,alpha1(ADart1)); linkAlpha3(n2,alpha1(ADart2));
128 
129  if (dd1!=NULL) unlinkAlpha1(alpha3(ADart1));
130  if (dd2!=NULL) unlinkAlpha1(alpha3(ADart2));
131 
132  linkAlpha1(n1,alpha3(ADart1)); linkAlpha1(n2,alpha3(ADart2));
133  if (dd1!=NULL || dd2!=NULL)
134  {
135  CDart * nn1=addMapDart();
136  CDart * nn2=addMapDart();
137 
138  linkAlpha0(nn1,nn2);
139  linkAlpha2(n1,nn1); linkAlpha2(n2,nn2);
140 
141  if (dd1!=NULL) linkAlpha1(alpha3(dd1),nn1);
142  if (dd2!=NULL) linkAlpha1(alpha3(dd2),nn2);
143 
144  linkAlpha3(alpha1(dd1),nn1); linkAlpha3(alpha1(dd2),nn2);
145  }
146  }
147 
148  return alpha1(ADart1);
149 }
150 //******************************************************************************
151 int CGMapGeneric::insertEdgeOnMarkedFaces(int AMarkNumber,
152  bool ANoCrossedFace,
153  bool /*ANoTwoEdgesFace*/)
154 {
155  CDynamicCoverageAll it(this);
156  int nbInserted = 0;
157  int treated = getNewMark();
158  int mark = getNewMark();
159 
160  for (; it.cont(); ++it)
161  if (!isMarked(*it, treated))
162  {
163  if (!isMarked(*it, AMarkNumber))
164  setMark(*it, treated);
165  else
166  {
167  // Pour chaque face non traitée, faire:
168  markOrbit(*it, ORBIT_FACE, treated);
169 
170  // Retrouver deux sommets sélectionnés de la face:
171  bool canInsert = true;
172  CDart * d1 = NULL, * d2 = NULL;
173 
174  CDynamicCoverageFace cov(this, *it);
175 
176  for (; cov.cont() && canInsert; ++cov)
177  if (isMarked(*cov, AMarkNumber) && !isMarked(*cov, mark))
178  {
179  if (ANoCrossedFace)
180  markOrbit(*cov, ORBIT_13, mark);
181 
182  if (d1==NULL)
183  d1= *cov;
184  else if (d2==NULL)
185  d2= *cov;
186  else
187  canInsert = false; // trop de sommets sélectionnés
188  }
189 
190  if (ANoCrossedFace)
191  unmarkOrbit(*it, ORBIT_FACE, mark);
192 
193  canInsert &= (d2!=NULL);
194 
195  if (canInsert && ANoCrossedFace && !isSameOrbit(d1,d2,ORBIT_01))
196  d2 = alpha3(d2);
197 
198  if (canInsert && belongToSameOrientedOrbit(d1, d2, ORBIT_01))
199  d2 = alpha1(d2);
200 
201  // Insertion effective:
202  if (canInsert)
203  {
204  CDart * newEdge = insertEdge(d1,d2);
205  markOrbit(newEdge, ORBIT_EDGE, treated);
206  ++nbInserted;
207  }
208  }
209  }
210 
211  negateMaskMark(treated);
212  freeMark(treated);
213  freeMark(mark);
214 
215  return nbInserted;
216 }
217 //******************************************************************************
218 #define IS_MARKED_EDGE(D) \
219  ( \
220  isMarked(D, AMarkNumber) || isMarked(alpha0(D), AMarkNumber) || \
221  ( \
222  ANoCrossedVolume && !isFree2(D) && \
223  (isMarked(alpha2(D), AMarkNumber) || isMarked(alpha20(D), AMarkNumber)) \
224  ) \
225  )
226 
227 #define IS_VALID_EDGE(D) \
228  (ANoCrossedVolume || isFree2(D) || \
229  (!isMarked( D , AMarkNumber) && !isMarked(alpha0 (D), AMarkNumber)) || \
230  (!isMarked(alpha2(D), AMarkNumber) && !isMarked(alpha02(D), AMarkNumber)))
231 
232 #define IS_ON_SAME_EDGE(D1,D2) \
233  ((D1)==(D2) || (ANoCrossedVolume && ((D1)==alpha2(D2))))
234 //******************************************************************************
235 // Méthode protégée!
236 bool CGMapGeneric::turnAroundVertex(CDart * ADart, bool ANoCrossedVolume,
237  int AMarkNumber,
238  CDart * & ANext, bool & ACrossed)
239 {
240  assert(ADart!=NULL);
241  assert(IS_MARKED_EDGE(ADart));
242 
243  bool firstDirection = true;
244  bool validVertex = true;
245 
246  ANext = NULL;
247 
248  for (CDynamicCoverage12 cov(this, ADart); validVertex && cov.cont(); ++cov)
249  {
250  if (cov.prevOperationType() == OP_JUMP)
251  firstDirection = false;
252 
253  if (IS_MARKED_EDGE(*cov) && !IS_ON_SAME_EDGE(*cov, ADart) &&
254  (ANext==NULL || !IS_ON_SAME_EDGE(*cov, ANext)))
255  {
256  validVertex = ANext==NULL && IS_VALID_EDGE(*cov);
257 
258  if (validVertex)
259  {
260  ACrossed =
261  cov.prevOperationType() ==
262  (firstDirection ? OP_ALPHAJ : OP_ALPHAI);
263 
264  if (ACrossed && !isFree2(*cov) && IS_MARKED_EDGE(alpha2(*cov)))
265  {
266  ACrossed = false;
267  ANext = alpha2(*cov);
268  }
269  else
270  ANext = *cov;
271  }
272  else
273  ANext = NULL;
274  }
275  }
276 
277  return validVertex;
278 }
279 //******************************************************************************
280 bool CGMapGeneric::canInsertFace(CDart * ADart, int AMarkNumber,
281  bool ANoCrossedVolume,
282  bool ANoTwoEdgesFace,
283  bool ANoTwoFacesVolume)
284 {
285  assert(ADart!=NULL);
286  assert(isMarked(ADart, AMarkNumber));
287 
288  /* On suit le chemin donné par les arêtes sélectionnées du volume en vérifiant
289  * à chaque sommet qu'il n'y alpha pas plus de 2 arêtes sélectionnées
290  * incidentes au sommet:
291  */
292 
293  CDart * current = ADart;
294  int nbVertices = 0;
295 
296  bool firstDirection = true;
297  bool finished = false;
298  bool canInsert = IS_VALID_EDGE(current);
299  bool sameFace[2] = { true, true };
300 
301  // On part d'un côté, puis de l'autre:
302 
303  while (canInsert && !finished)
304  {
305  // Pour chaque arête du chemin:
306  // On tourne autour du sommet:
307  ++nbVertices;
308 
309  // On tourne autour du sommet courant:
310  CDart * next;
311  bool crossed;
312 
313  canInsert = turnAroundVertex(current, ANoCrossedVolume, AMarkNumber,
314  next, crossed);
315  if (next!=NULL)
316  {
317  sameFace[0] =
318  sameFace[crossed ? 1 : 0] && isSameOrbit(alpha1 (next), current, ORBIT_2);
319 
320  sameFace[1] =
321  sameFace[crossed ? 0 : 1] && isSameOrbit(alpha21(next), current, ORBIT_2);
322  }
323 
324  if (canInsert)
325  {
326  if (next==NULL || isFree0(next))
327  {
328  // On essaie de repartir dans l'autre sens:
329  finished = !firstDirection || isFree0(ADart);
330  firstDirection = false;
331  current = alpha0(ADart);
332  }
333  else
334  {
335  // On continue notre bonhomme de chemin:
336  current = alpha0(next);
337 
338  if (IS_ON_SAME_EDGE(current, ADart))
339  finished = true;
340  }
341  }
342  }
343 
344  // Résultat (si firstDirection vaut 'vrai', c'est que la face est fermée):
345  bool enoughEdges = !ANoTwoEdgesFace || nbVertices >= (firstDirection ? 3 : 2);
346  bool enoughFaces = !ANoTwoFacesVolume || (!sameFace[0] && !sameFace[1]);
347 
348  return canInsert && enoughEdges && enoughFaces;
349 }
350 //******************************************************************************
351 CDart * CGMapGeneric::insertFace(CDart * ADart, int AMarkNumber,
352  bool ANoCrossedVolume)
353 {
354  assert(ADart!=NULL);
355  assert(canInsertFace(ADart, AMarkNumber, ANoCrossedVolume));
356 
357  // On suit le chemin donné par les arêtes sélectionnées du volume:
358  bool firstDirection = true ;
359  bool finished = false;
360  bool turnedAround = false; // dernière opération: tourner autour d'un sommet
361  bool jumped = false; // dernière opération: sauter au sommet suivant
362 
363  CDart * prev = NULL, * current = ADart, * next;
364 
365  // On part d'un côté, puis de l'autre:
366 
367  while (!finished)
368  {
369  assert(!turnedAround || !jumped);
370 
371  // Pour chaque brin du chemin:
372 
373  // 1) Recherche du brin suivant:
374  if (turnedAround)
375  {
376  // On passe au sommet suivant:
377  next = isFree0(current) ? NULL : alpha0(current);
378  }
379  else
380  {
381  // On tourne autour du sommet:
382  bool crossed;
383  turnAroundVertex(current, ANoCrossedVolume,
384  AMarkNumber, next, crossed);
385 
386  if (next!=NULL && crossed && ANoCrossedVolume)
387  {
388  assert(!isFree2(current));
389  current = alpha2(current);
390  if (prev!=NULL)
391  {
392  assert(!isFree2(prev));
393  prev = alpha2(prev);
394  }
395  }
396  }
397 
398  // 2) Création d'une partie de la nouvelle face:
399  CDart * d1 = current;
400  CDart * d2 = isFree2(d1) ? NULL : alpha2(d1);
401  CDart * n1 = addMapDart();
402  CDart * n2 = addMapDart();
403 
404  if (d2!=NULL)
405  {
406  unlinkAlpha2(d1);
407  linkAlpha2(d2,n2);
408  }
409 
410  linkAlpha3(n1,n2);
411  linkAlpha2(d1,n1);
412 
413  if (turnedAround)
414  {
415  linkAlpha1(alpha2 (d1), alpha2 (prev));
416  linkAlpha1(alpha23(d1), alpha23(prev));
417  }
418 
419  if (jumped)
420  {
421  linkAlpha0(n1, alpha02 (d1));
422  linkAlpha0(n2, alpha023(d1));
423  }
424 
425  // 3) Passage au brin suivant:
426  if (next==NULL)
427  {
428  // On essaie de repartir dans l'autre sens:
429  finished = !firstDirection || isFree0(ADart);
430  firstDirection = false;
431  turnedAround = false;
432  jumped = true;
433  prev = ADart;
434  current = alpha0(ADart);
435  }
436  else
437  if (IS_ON_SAME_EDGE(next, ADart))
438  finished = true;
439  else
440  {
441  prev = current; jumped = turnedAround;
442  current = next ; turnedAround = !turnedAround;
443  }
444  }
445 
446  // Dernière 0-couture (si la face est fermée):
447  if (firstDirection)
448  {
449  assert(!isFree2(next));
450  linkAlpha0(alpha2 (ADart), alpha02 (ADart));
451  linkAlpha0(alpha23(ADart), alpha023(ADart));
452  }
453 
454  return alpha2(ADart);
455 }
456 //******************************************************************************
457 #undef IS_ON_SAME_EDGE
458 #undef IS_VALID_EDGE
459 #undef IS_MARKED_EDGE
460 //******************************************************************************
461 int CGMapGeneric::insertFaceOnMarkedVolumes(int AMarkNumber,
462  bool ANoCrossedVolume,
463  bool ANoTwoEdgesFace,
464  bool ANoTwoFacesVolume)
465 {
466  CDynamicCoverageAll it(this);
467  int nbInserted = 0;
468  int treated = getNewMark();
469 
470  for (; it.cont(); ++it)
471  if (!isMarked(*it, treated))
472  {
473  if (isMarked(*it, AMarkNumber))
474  {
475  // Marquage de l'ensemble de la "face" sélectionnée:
476  stack<CDart *> toTreat; toTreat.push(*it);
477 
478  while (!toTreat.empty())
479  {
480  CDart * dart = toTreat.top(); toTreat.pop();
481 
482  for (CDynamicCoverage12 cov(this, dart); cov.cont(); ++cov)
483  if (!isMarked(*cov, treated))
484  {
485  if (!isFree0(*cov) && !isMarked(alpha0(*cov), treated) &&
486  (isMarked(*cov, AMarkNumber) ||
487  isMarked(alpha0(*cov), AMarkNumber)))
488  toTreat.push(alpha0(*cov));
489 
490  setMark( *cov , treated);
491  setMark(alpha2(*cov), treated);
492  }
493  }
494 
495  // Tentative d'insertion de face:
496  if (canInsertFace(*it, AMarkNumber, ANoCrossedVolume,
497  ANoTwoEdgesFace, ANoTwoFacesVolume))
498  {
499  CDart * newFace = insertFace(*it, AMarkNumber, ANoCrossedVolume);
500 
501  markOrbit(newFace, ORBIT_FACE, treated);
502  ++nbInserted;
503  }
504  }
505  else
506  setMark(*it, treated);
507  }
508 
509  negateMaskMark(treated);
510  freeMark(treated);
511 
512  return nbInserted;
513 }
514 //******************************************************************************