Moka kernel
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
gmv-merge.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 <algorithm>
26 #include "g-map-vertex.hh"
27 #include "geometry.hh"
28 using namespace GMap3d;
29 //******************************************************************************
30 int CGMapVertex::mergeMarkedColinearEdges(int AMarkNumber, bool ADeleteDarts)
31 {
32  return mergeMarkedAlignedCells(1, AMarkNumber, ADeleteDarts);
33 }
34 //******************************************************************************
35 int CGMapVertex::mergeMarkedCoplanarFaces(int AMarkNumber, bool ADeleteDarts)
36 {
37  return mergeMarkedAlignedCells(2, AMarkNumber, ADeleteDarts);
38 }
39 //******************************************************************************
40 int CGMapVertex::mergeMarkedAlignedCells(int ADim,
41  int AMarkNumber, bool ADeleteDarts)
42 {
43  assert(ADim==1 || ADim==2);
44 
45  CDynamicCoverageAll it(this);
46 
47  int selected = getNewMark();
48  int treated = getNewMark();
49 
50  // Repérage des cellules de dimension ADim-1 sélectionnées incidentes à des
51  // cellules de dimension ADim alignées:
52 
53  markIncidentCells(ORBIT_CELL[ADim-1], AMarkNumber, selected);
54 
55  // Démarquage des cellules qui ne peuvent pas ou ne doivent pas être
56  // fusionnées:
57 
58  for (it.reinit(); it.cont(); ++it)
59  if (!isMarked(*it, treated))
60  {
61  if (isMarked(*it, selected))
62  {
63  bool possible =
64  !isFree(*it, ADim) && canMerge(*it, alpha(*it,ADim), ADim);
65 
66  if (possible)
67  {
68  CDart * side1 = *it;
69  CDart * side2 = alpha(*it,ADim);
70 
71  CVertex vector1 =
72  ADim==1 ? edgeVector(side1) : faceNormalVector(side1);
73 
74  CVertex vector2 =
75  ADim==1 ? edgeVector(side2) : faceNormalVector(side2);
76 
77  possible = CGeometry::areColinear(vector1, vector2);
78  }
79 
80  if (!possible)
81  unmarkOrbit(*it, ORBIT_CELL[ADim-1], selected);
82 
83  markOrbit(*it, ORBIT_CELL[ADim-1], treated);
84  }
85  else
86  setMark(*it, treated);
87  }
88 
89  negateMaskMark(treated);
90 
91  // Fusion effective:
92  int nbMerged = isolateMarkedCells(selected, ADim-1, ADeleteDarts, false);
93 
94  freeMark(treated);
95 
96  unmarkAll(selected);
97  freeMark(selected);
98 
99  return nbMerged;
100 }
101 //******************************************************************************
102 unsigned int CGMapVertex::simplify3DObject(int AMark0, int AMark1, int AMark2)
103 {
104  // Simplify a 3D map in its minimal form, without use shifting operations, and
105  // by keeping each cell homeomorphic to a ball.
106  // This method suppose that each cell is initially homeomorphic to a ball, and
107  // that there is no dangling cell.
108  // First we remove each degree two face, then each degree two edges, last each
109  // degree two vertex.
110  // std::cout<<"simplify3DObject(m0,m1,m2)"<<std::endl;
111  int toDelete = getNewMark();
112  int treated = getNewMark();
113  CDart* current = NULL;
114  CDart* t1 = NULL;
115  CDart* t2 = NULL;
116  std::stack<CDart*> FToTreat;
117  bool dangling = false;
118  unsigned int nbRemove = 0;
119 
120  int toDelete0 = (AMark0==-1?toDelete:AMark0);
121  int toDelete1 = (AMark1==-1?toDelete:AMark1);
122  int toDelete2 = (AMark2==-1?toDelete:AMark2);
123 
124  int indexVol = getNewDirectInfo();
125  int indexFace = getNewDirectInfo();
126  if ( indexVol!=-1 && indexFace!=-1 )
127  initUnionFindTreesFaceVolume(indexFace, indexVol);
128  else
129  {
130  std::cout<<"Not enough directInfo to use union-find trees."<<std::endl;
131  return 0;
132  }
133 
134  // 1) We remove faces.
135  CDynamicCoverageAll cov(this);
136  while ( cov.cont() )
137  {
138  dangling = false;
139  if ( ! FToTreat.empty() )
140  {
141  do
142  {
143  current = FToTreat.top();
144  FToTreat.pop();
145  if ( !isMarked(current, toDelete2) && isDanglingFace(current) )
146  dangling = true;
147  }
148  while ( !dangling && ! FToTreat.empty() );
149  }
150 
151  if ( !dangling )
152  current = cov++;
153 
154  if ( !isMarked(current,toDelete2) &&
155  (dangling || !isMarked(current, treated)) )
156  {
157  if ( !isFree3(current) )
158  {
159  // We remove dangling faces and degree two faces.
160  if ( dangling ||
161  findUnionFindTrees(current, indexVol)!=
162  findUnionFindTrees(alpha3(current),indexVol) )
163  {
164  // First we mark the current face.
165  CDynamicCoverage01 itFace(this, current);
166  for ( ; itFace.cont(); ++itFace )
167  {
168  setMark( *itFace, treated );
169  setMark( alpha3(*itFace), treated );
170  setMark( *itFace, toDelete2 );
171  setMark( alpha3(*itFace), toDelete2 );
172  }
173 
174  // Second, we push in the stack all the neighboors of the current
175  // face that become dangling after the removal.
176  // Moreover, we make the removal manually instead of calling
177  // remove(current, 2, false) for optimisation reasons.
178  for ( itFace.reinit(); itFace.cont(); ++itFace )
179  {
180  if (alpha23(*itFace)==alpha32(*itFace) &&
181  !isMarked(alpha2(*itFace), toDelete2) &&
182  !isFree3(alpha2(*itFace)) )
183  {
184  FToTreat.push(alpha2(*itFace));
185  }
186 
187  // Now we update alpha2
188  t1 = alpha(*itFace, 2);
189  if ( !isMarked(t1, toDelete2) )
190  {
191  t2 = *itFace;
192  while ( isMarked(t2, toDelete2) )
193  {
194  t2 = alpha32(t2);
195  }
196 
197  if ( t2 != alpha(t1, 2) )
198  {
199  unsew2(t1);
200  if (!isFree(t2, 2)) unsew2(t2);
201  if (t1!=t2) sew2(t1,t2);
202  }
203  }
204  }
205 
206  if ( !dangling )
207  mergeUnionFindTrees(current, alpha3(current), indexVol);
208  }
209  else
210  {
211  CDynamicCoverage01 itFace(this, current);
212  for ( ; itFace.cont(); ++itFace )
213  {
214  setMark( *itFace, treated );
215  setMark( alpha3(*itFace), treated );
216  }
217  }
218  }
219  else
220  {
221  CDynamicCoverage01 itFace(this, current);
222  for ( ; itFace.cont(); ++itFace )
223  {
224  setMark( *itFace, treated );
225  }
226  }
227  }
228  }
229  negateMaskMark(treated);
230  // assert( isWholeMapUnmarked(treated) );
231  save("after-remove-faces.moka");
232 
233  // 2) We remove edges.
234  cov.reinit();
235  while ( cov.cont() )
236  {
237  if ( ! FToTreat.empty() )
238  {
239  current = FToTreat.top();
240  FToTreat.pop();
241  dangling = true;
242  }
243  else
244  {
245  current = cov++;
246  dangling = false;
247  }
248 
249  if ( !isMarked(current, toDelete2) && !isMarked(current, toDelete1) &&
250  (dangling || !isMarked(current, treated)) )
251  {
252  if ( !isFree2(current) )
253  {
254  // We remove dangling edges and degree two edges.
255  if ( (alpha1(current) !=alpha2(current) ||
256  alpha01(current)!=alpha02(current)) &&
257  alpha23(current)==alpha32(current) &&
258  ( dangling ||
259  findUnionFindTrees(current, indexFace)!=
260  findUnionFindTrees(alpha2(current),indexFace)) )
261  {
262  // First we mark the current edge.
263  CDynamicCoverage02 itEdge(this, current);
264  for ( ; itEdge.cont(); ++itEdge )
265  {
266  setMark( *itEdge, treated );
267  setMark( *itEdge, toDelete1 );
268  setMark( alpha3(*itEdge), treated );
269  setMark( alpha3(*itEdge), toDelete1 );
270  }
271 
272  // Second, we push in the stack all the neighboors of the current
273  // edge that become dangling after the removal.
274  // Moreover, we make the removal manually instead of calling
275  // remove(current, 1, false) for optimisation reasons.
276  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
277  {
278  if ( alpha12(*itEdge)==alpha21(*itEdge) &&
279  !isMarked(alpha1(*itEdge), toDelete1) &&
280  !isFree2(alpha1(*itEdge)) )
281  {
282  FToTreat.push(alpha1(*itEdge));
283  }
284 
285  // Now we update alpha1
286  t1 = alpha(*itEdge, 1);
287  if ( !isMarked(t1, toDelete1) )
288  {
289  t2 = *itEdge;
290  while ( isMarked(t2, toDelete1) )
291  {
292  t2 = alpha21(t2);
293  }
294 
295  if ( t2 != alpha(t1, 1) )
296  {
297  unsew1(t1);
298  if (!isFree(t2, 1))
299  {
300  unsew1(t2);
301  }
302  if (t1!=t2)
303  {
304  sew1(t1, t2);
305  }
306  }
307  }
308  }
309 
310  if ( !dangling )
311  mergeUnionFindTrees(current, alpha2(current), indexFace);
312  }
313  else
314  {
315  CDynamicCoverage02 itEdge(this, current);
316  for ( ; itEdge.cont(); ++itEdge )
317  {
318  setMark( *itEdge, treated );
319  setMark( alpha3(*itEdge), treated );
320  }
321  }
322  }
323  else
324  {
325  CDynamicCoverage0 itEdge(this, current);
326  for ( ; itEdge.cont(); ++itEdge )
327  {
328  setMark( *itEdge, treated );
329  setMark( alpha3(*itEdge), treated );
330  }
331  }
332  }
333  }
334  negateMaskMark(treated);
335  save("after-remove-edges.moka");
336 
337  // 3) We remove vertices. This is simpler since a vertex can not be dangling.
338  cov.reinit();
339  while ( cov.cont() )
340  {
341  current = cov++;
342 
343  if ( !isMarked(current,treated) && !isMarked(current, toDelete2)
344  && !isMarked(current, toDelete1) && !isMarked(current, toDelete0) )
345  {
346  bool deleteVertex = true;
347  CStaticCoverage23 itVertex(this, current);
348  for ( ; itVertex.cont(); ++itVertex )
349  {
350  setMark( *itVertex, treated );
351  setMark( alpha1(*itVertex), treated );
352 
353  if ( isFree1(*itVertex) ||
354  alpha1 (*itVertex)==alpha2 (*itVertex) ||
355  alpha01(*itVertex)==alpha02(*itVertex) ||
356  alpha12(*itVertex)!=alpha21(*itVertex) )
357  deleteVertex = false;
358  }
359 
360  if ( deleteVertex )
361  {
362  // First we mark the current vertex.
363  for ( itVertex.reinit(); itVertex.cont(); ++itVertex )
364  {
365  setMark( *itVertex, toDelete0 );
366  setMark( alpha1(*itVertex), toDelete0 );
367  }
368 
369  // Second, we make the removal manually instead of calling
370  // remove(current, 0, false) for optimisation reasons.
371  for ( itVertex.reinit(); itVertex.cont(); ++itVertex )
372  {
373  t1 = alpha(*itVertex, 0);
374  if ( !isMarked(t1, toDelete0) )
375  {
376  t2 = *itVertex;
377  while ( isMarked(t2, toDelete0) )
378  {
379  t2 = alpha10(t2);
380  }
381 
382  if ( t2 != alpha(t1, 0) )
383  {
384  unsew0(t1);
385  if (!isFree(t2, 0)) unsew0(t2);
386  if (t1!=t2) sew0(t1, t2);
387  }
388  }
389  }
390  }
391  }
392  }
393 
394  save("after-all-removals.moka");
395 
396  // 4) We remove all the darts marked toDelete
397  for ( cov.reinit(); cov.cont(); )
398  {
399  current = cov++;
400 
401  unsetMark(current,treated);
402  if ( isMarked(current, toDelete) )
403  {
404  delMapDart(current);
405  }
406 
407  if ( isMarked(current, toDelete0) ||
408  isMarked(current, toDelete1) ||
409  isMarked(current, toDelete2) )
410  ++nbRemove;
411  }
412 
413  freeMark(toDelete);
414  freeMark(treated);
415 
416  freeDirectInfo(indexVol);
417  freeDirectInfo(indexFace);
418 
419  return nbRemove;
420 }
421 //******************************************************************************
422 unsigned int CGMapVertex::simplify3DObjectRemoval(unsigned int optosimplify)
423 {
424  // Simplify a 3D map in its minimal form, without use shifting operations,
425  // and by keeping each cell homeomorphic to a ball.
426  // This method suppose that each cell is initially homeomorphic to a ball,
427  // and that there is no dangling cell.
428  // First we remove each degree two face, then each degree two edge, last each
429  // degree two vertex.
430  if ( !(optosimplify & FACE_REMOVAL ||
431  optosimplify & EDGE_REMOVAL ||
432  optosimplify & VERTEX_REMOVAL ) )
433  return 0;
434 
435  int toDelete = getNewMark();
436  int treated = getNewMark();
437  CDart* current = NULL;
438  CDart* t1 = NULL;
439  CDart* t2 = NULL;
440  std::stack<CDart*> FToTreat;
441  bool dangling = false;
442  unsigned int nbRemove = 0;
443 
444  int indexVol = getNewDirectInfo();
445  int indexFace = getNewDirectInfo();
446  if ( indexVol!=-1 && indexFace!=-1 )
447  initUnionFindTreesFaceVolume(indexFace, indexVol);
448  else
449  {
450  std::cout<<"Not enough directInfo to use union-find trees."<<std::endl;
451  return 0;
452  }
453 
454  CDart* firstDeleteDart = NULL;
455 
456  // 1) We remove faces.
457  CDynamicCoverageAll cov(this);
458  if ( optosimplify & FACE_REMOVAL )
459  {
460  while ( cov.cont() )
461  {
462  dangling = false;
463  if ( ! FToTreat.empty() )
464  {
465  do
466  {
467  current = FToTreat.top();
468  FToTreat.pop();
469  if ( !isMarked(current, toDelete) && isDanglingFace(current) )
470  dangling = true;
471  }
472  while ( !dangling && ! FToTreat.empty() );
473  }
474 
475  if ( !dangling )
476  current = cov++;
477 
478  if ( !isMarked(current,toDelete) &&
479  (dangling || !isMarked(current, treated)) )
480  {
481  if ( !isFree3(current) )
482  {
483  // We remove dangling faces and degree two faces.
484  if ( dangling ||
485  findUnionFindTrees(current, indexVol)!=
486  findUnionFindTrees(alpha3(current),indexVol) )
487  {
488  // First we mark the current face.
489  CDynamicCoverage01 itFace(this, current);
490  for ( ; itFace.cont(); ++itFace )
491  {
492  setMark( *itFace, treated );
493  setMark( alpha3(*itFace), treated );
494  setMark( *itFace, toDelete );
495  setMark( alpha3(*itFace), toDelete );
496  }
497 
498  while ( cov.cont() && isMarked(*cov, treated) )
499  ++cov;
500 
501  // Second we manage vertex attributes, and remove darts
502  // from the list of darts.
503  for ( itFace.reinit(); itFace.cont(); ++itFace )
504  {
505  removeDartInList( *itFace );
506  removeDartInList( alpha3(*itFace) );
507  (*itFace)->setNext(alpha3(*itFace));
508  alpha3(*itFace)->setNext(firstDeleteDart);
509  firstDeleteDart=*itFace;
510 
511  if ( getVertex(*itFace)!=NULL )
512  {
513  CAttributeVertex * v = removeVertex(*itFace);
514 
515  if ( !isMarked(alpha2(*itFace), toDelete) )
516  setVertex(alpha2(*itFace), v);
517  else if (!isMarked(alpha32(*itFace), toDelete) )
518  setVertex(alpha32(*itFace), v);
519  else if (!isMarked(alpha12(*itFace), toDelete) )
520  setVertex(alpha12(*itFace), v);
521  else if (!isMarked(alpha312(*itFace), toDelete) )
522  setVertex(alpha312(*itFace), v);
523  else
524  delete v;
525  }
526 
527  t1=alpha3(*itFace);
528  if ( getVertex(t1)!=NULL )
529  {
530  CAttributeVertex * v = removeVertex(t1);
531 
532  if ( !isMarked(alpha2(t1), toDelete) )
533  setVertex(alpha2(t1), v);
534  else if (!isMarked(alpha32(t1), toDelete) )
535  setVertex(alpha32(t1), v);
536  else if (!isMarked(alpha12(t1), toDelete) )
537  setVertex(alpha12(t1), v);
538  else if (!isMarked(alpha312(t1), toDelete) )
539  setVertex(alpha312(t1), v);
540  else
541  delete v;
542  }
543  }
544 
545  // Third, we push in the stack all the neighboors of the current
546  // face that become dangling after the removal.
547  // Moreover, we make the removal manually instead of calling
548  // remove(current, 2, false) for optimisation reasons.
549  for ( itFace.reinit(); itFace.cont(); ++itFace )
550  {
551  if (alpha23(*itFace)==alpha32(*itFace) &&
552  !isMarked(alpha2(*itFace), toDelete) &&
553  !isFree3(alpha2(*itFace)) )
554  {
555  FToTreat.push(alpha2(*itFace));
556  }
557 
558  // Now we update alpha2
559  t1 = alpha(*itFace, 2);
560  if ( !isMarked(t1, toDelete) )
561  {
562  t2 = *itFace;
563  while ( isMarked(t2, toDelete) )
564  {
565  t2 = alpha32(t2);
566  }
567 
568  if ( t2 != alpha(t1, 2) )
569  {
570  unlinkAlpha2(t1);
571  if (!isFree(t2, 2)) unlinkAlpha2(t2);
572  if (t1!=t2) linkAlpha2(t1,t2);
573  }
574  }
575  }
576 
577  if ( !dangling )
578  mergeUnionFindTrees(current, alpha3(current), indexVol);
579  }
580  else
581  {
582  for ( CDynamicCoverage01 itFace(this, current);
583  itFace.cont(); ++itFace )
584  {
585  setMark( *itFace, treated );
586  setMark( alpha3(*itFace), treated );
587  }
588  }
589  }
590  else
591  {
592  for ( CDynamicCoverage01 itFace(this, current);
593  itFace.cont(); ++itFace )
594  {
595  setMark( *itFace, treated );
596  }
597  }
598  }
599  }
600  negateMaskMark(treated);
601  assert( isWholeMapUnmarked(treated) );
602  // save("after-remove-faces.moka");
603  }
604 
605  // 2) We remove edges.
606  if ( optosimplify & EDGE_REMOVAL )
607  {
608  cov.reinit();
609  while ( cov.cont() )
610  {
611  if ( ! FToTreat.empty() )
612  {
613  current = FToTreat.top();
614  FToTreat.pop();
615  dangling = true;
616  }
617  else
618  {
619  current = cov++;
620  dangling = false;
621  }
622 
623  if ( !isMarked(current, toDelete) &&
624  (dangling || !isMarked(current, treated)) )
625  {
626  if ( !isFree2(current) )
627  {
628  // We remove dangling edges and degree two edges.
629  if ( (alpha1(current) !=alpha2(current) ||
630  alpha01(current)!=alpha02(current)) &&
631  alpha23(current)==alpha32(current) &&
632  ( dangling ||
633  findUnionFindTrees(current, indexFace)!=
634  findUnionFindTrees(alpha2(current),indexFace)) )
635  {
636  // First we mark the current edge.
637  CDynamicCoverage02 itEdge(this, current);
638  for ( ; itEdge.cont(); ++itEdge )
639  {
640  setMark( *itEdge, treated );
641  setMark( *itEdge, toDelete );
642  setMark( alpha3(*itEdge), treated );
643  setMark( alpha3(*itEdge), toDelete );
644  }
645 
646  while ( cov.cont() && isMarked(*cov, treated) )
647  ++cov;
648 
649  // Second we manage vertex attributes, and remove darts
650  // from the list of darts.
651  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
652  {
653  removeDartInList( *itEdge );
654  if ( !isFree3(*itEdge) )
655  {
656  removeDartInList( alpha3(*itEdge) );
657  (*itEdge)->setNext(alpha3(*itEdge));
658  alpha3(*itEdge)->setNext(firstDeleteDart);
659  }
660  else
661  (*itEdge)->setNext(firstDeleteDart);
662  firstDeleteDart=*itEdge;
663 
664  if ( getVertex(*itEdge)!=NULL )
665  {
666  CAttributeVertex * v = removeVertex(*itEdge);
667 
668  if ( !isMarked(alpha1(*itEdge), toDelete) )
669  setVertex(alpha1(*itEdge), v);
670  else if ( !isMarked(alpha21(*itEdge), toDelete) )
671  setVertex(alpha21(*itEdge), v);
672  else
673  delete v;
674  }
675 
676  if ( !isFree3(*itEdge) )
677  {
678  t1=alpha3(*itEdge);
679  if ( getVertex(t1)!=NULL )
680  {
681  CAttributeVertex * v = removeVertex(t1);
682 
683  if ( !isMarked(alpha1(t1), toDelete) )
684  setVertex(alpha1(t1), v);
685  else if ( !isMarked(alpha21(t1), toDelete) )
686  setVertex(alpha21(t1), v);
687  else
688  delete v;
689  }
690  }
691  }
692 
693  // Third, we push in the stack all the neighboors of the current
694  // edge that become dangling after the removal.
695  // Moreover, we make the removal manually instead of calling
696  // remove(current, 1, false) for optimisation reasons.
697  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
698  {
699  if ( alpha12(*itEdge)==alpha21(*itEdge) &&
700  !isMarked(alpha1(*itEdge), toDelete) &&
701  !isFree2(alpha1(*itEdge)) )
702  {
703  FToTreat.push(alpha1(*itEdge));
704  }
705 
706  // Now we update alpha1
707  t1 = alpha(*itEdge, 1);
708  if ( !isMarked(t1, toDelete) )
709  {
710  t2 = *itEdge;
711  while ( isMarked(t2, toDelete) )
712  {
713  t2 = alpha21(t2);
714  }
715 
716  if ( t2 != alpha(t1, 1) )
717  {
718  unlinkAlpha1(t1);
719  if ( !isFree3(t1) ) unlinkAlpha1(alpha3(t1));
720  if (!isFree(t2, 1))
721  {
722  unlinkAlpha1(t2);
723  if ( !isFree3(t2) ) unlinkAlpha1(alpha3(t2));
724  }
725  if (t1!=t2)
726  {
727  linkAlpha1(t1, t2);
728  if ( !isFree3(t1) ) linkAlpha1(alpha3(t1), alpha3(t2));
729  }
730  }
731  }
732  }
733 
734  if ( !dangling )
735  mergeUnionFindTrees(current, alpha2(current), indexFace);
736  }
737  else
738  {
739  for ( CDynamicCoverage02 itEdge(this, current);
740  itEdge.cont(); ++itEdge )
741  {
742  setMark( *itEdge, treated );
743  setMark( alpha3(*itEdge), treated );
744  }
745  }
746  }
747  else
748  {
749  for ( CDynamicCoverage0 itEdge(this, current);
750  itEdge.cont(); ++itEdge )
751  {
752  setMark( *itEdge, treated );
753  setMark( alpha3(*itEdge), treated );
754  }
755  }
756  }
757  }
758  negateMaskMark(treated);
759  assert( isWholeMapUnmarked(treated) );
760  //save("after-remove-edges.moka");
761  }
762 
763  // 3) We remove vertices. This is simpler since a vertex can not be dangling.
764  if ( optosimplify & VERTEX_REMOVAL )
765  {
766  cov.reinit();
767  while ( cov.cont() )
768  {
769  current = cov++;
770 
771  if ( !isMarked(current,treated) )
772  {
773  bool deleteVertex = true;
774  CStaticCoverage23 itVertex(this, current);
775  for ( ; itVertex.cont(); ++itVertex )
776  {
777  setMark( *itVertex, treated );
778  setMark( alpha1(*itVertex), treated );
779 
780  if ( isFree1(*itVertex) ||
781  alpha1 (*itVertex)==alpha2 (*itVertex) ||
782  alpha01(*itVertex)==alpha02(*itVertex) ||
783  alpha12(*itVertex)!=alpha21(*itVertex) )
784  deleteVertex = false;
785  }
786 
787  if ( deleteVertex )
788  {
789  // First we mark the current vertex todelete.
790  for ( itVertex.reinit(); itVertex.cont(); ++itVertex )
791  {
792  setMark( *itVertex, toDelete );
793  setMark( alpha1(*itVertex), toDelete );
794  }
795 
796  while ( cov.cont() && isMarked(*cov, treated) )
797  ++cov;
798 
799  // Second we remove the darts from their list.
800  for ( itVertex.reinit(); itVertex.cont(); ++itVertex )
801  {
802  removeDartInList( *itVertex );
803  removeDartInList( alpha1(*itVertex) );
804  (*itVertex)->setNext(alpha1(*itVertex));
805  alpha1(*itVertex)->setNext(firstDeleteDart);
806  firstDeleteDart=*itVertex;
807 
808  if ( getVertex(*itVertex)!=NULL )
809  delVertex(*itVertex);
810  else if ( getVertex(alpha1(*itVertex))!=NULL )
811  delVertex(alpha1(*itVertex));
812  }
813 
814  // Second, we make the removal manually instead of calling
815  // remove(current, 0, false) for optimisation reasons.
816  for ( itVertex.reinit(); itVertex.cont(); ++itVertex )
817  {
818  t1 = alpha(*itVertex, 0);
819  if ( !isMarked(t1, toDelete) )
820  {
821  t2 = *itVertex;
822  while ( isMarked(t2, toDelete) )
823  {
824  t2 = alpha10(t2);
825  }
826 
827  if ( t2 != alpha(t1, 0) )
828  {
829  unlinkAlpha0(t1);
830  if (!isFree(t2, 0)) unlinkAlpha0(t2);
831  if (t1!=t2) linkAlpha0(t1, t2);
832  }
833  }
834  }
835  }
836  }
837  }
838  negateMaskMark(treated);
839  assert( isWholeMapUnmarked(treated) );
840  //save("after-all-removal.moka");
841  }
842 
843  // 4) We remove all the darts marked toDelete
844  while ( firstDeleteDart!=NULL )
845  {
846  t1 = firstDeleteDart->getNext();
847  delDart(firstDeleteDart);
848  firstDeleteDart = t1;
849  ++nbRemove;
850  }
851 
852  assert( isWholeMapUnmarked(toDelete) );
853  assert( isWholeMapUnmarked(treated) );
854 
855  freeMark(toDelete);
856  freeMark(treated);
857 
858  freeDirectInfo(indexVol);
859  freeDirectInfo(indexFace);
860 
861  return nbRemove;
862 }
863 //******************************************************************************
864 unsigned int CGMapVertex::simplify3DObjectContraction(unsigned int optosimplify)
865 {
866  if ( !(optosimplify & EDGE_CONTRACTION ||
867  optosimplify & FACE_CONTRACTION ||
868  optosimplify & VOLUME_CONTRACTION) )
869  return 0;
870 
871  // Simplify a 3D map in its minimal form, without use shifting operations,
872  // and by keeping each cell homeomorphic to a ball.
873  // This method suppose that each cell is initially homeomorphic to a ball,
874  // and that there is no dangling cell.
875  // First we contract each codegree two edge, then each codegree two face,
876  // last each codegree two volume.
877  // std::cout<<"simplify3DObjectContraction()"<<std::endl;
878  int toDelete = getNewMark();
879  int treated = getNewMark();
880  CDart* current = NULL;
881  CDart* t1 = NULL;
882  CDart* t2 = NULL;
883  std::stack<CDart*> FToTreat;
884  bool dangling = false;
885  unsigned int nbRemove = 0;
886 
887  int indexVertex = getNewDirectInfo();
888  int indexEdge = getNewDirectInfo();
889  if ( indexVertex!=-1 && indexEdge!=-1 )
890  initUnionFindTreesVerticesEdges(indexVertex, indexEdge);
891  else
892  {
893  std::cout<<"Not enough directInfo to use union-find trees."<<std::endl;
894  return 0;
895  }
896 
897  CDart* firstDeleteDart = NULL;
898 
899  // 1) We contract edges.
900  CDynamicCoverageAll cov(this);
901 
902  if ( optosimplify & EDGE_CONTRACTION )
903  {
904  while ( cov.cont() )
905  {
906  current = cov++;
907 
908  if ( !isMarked(current,toDelete) &&
909  !isMarked(current, treated) )
910  {
911  // We contract co-degree two edges.
912  bool toremove = true;
913  CDynamicCoverage23 itEdge(this, current);
914  for ( ; itEdge.cont(); ++itEdge)
915  {
916  assert ( !isFree0(*itEdge) );
917  if ( //isFree1(*itEdge) ||
918  alpha1(*itEdge)==alpha2(*itEdge) &&
919  alpha01(*itEdge)==alpha02(*itEdge) /* ||
920  alpha1(*itEdge)==alpha3(*itEdge) ||
921  alpha01(*itEdge)==alpha03(*itEdge)*/ )
922  toremove = false;
923 
924  setMark( *itEdge, treated );
925  setMark( alpha0(*itEdge), treated );
926  }
927 
928  if ( findUnionFindTrees(current, indexVertex)==
929  findUnionFindTrees(alpha0(current),indexVertex) )
930  toremove = false;
931 
932  if ( toremove )
933  {
934  // First we mark the current edge.
935  //CStaticCoverage23 itEdge(this, current);
936  //std::cout<<"edge contracted: ";
937  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
938  {
939  setMark( *itEdge, toDelete );
940  setMark( alpha0(*itEdge), toDelete );
941  //std::cout<<*itEdge<<", "<<alpha0(*itEdge)<<", ";
942  }
943  // std::cout<<std::endl;
944 
945  while ( cov.cont() && isMarked(*cov, treated) )
946  ++cov;
947 
948  std::vector<CDart*> vertex;
949  for (CDynamicCoverageVertex itvertex(this, current);
950  itvertex.cont(); ++itvertex)
951  {
952  vertex.push_back(*itvertex);
953  }
954  for (CDynamicCoverageVertex itvertex(this, alpha0(current));
955  itvertex.cont(); ++itvertex)
956  {
957  vertex.push_back(*itvertex);
958  }
959  std::sort(vertex.begin(), vertex.end());
960 
961  std::vector<std::vector<CDart*> > faces;
962  int markface = getNewMark();
963  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
964  if ( !isMarked(*itEdge, markface) )
965  {
966  faces.push_back(std::vector<CDart*>());
967  std::vector<std::vector<CDart*> >::iterator lastface=faces.end()-1;
968  for (CDynamicCoverageFace itface(this, *itEdge);
969  itface.cont(); ++itface)
970  {
971  (*lastface).push_back(*itface);
972  setMark(*itface, markface);
973  }
974  std::sort(lastface->begin(), lastface->end());
975  }
976 
977  /*std::vector<CDart*> volume;
978  for (CDynamicCoverageVolume itvol(this, current);
979  itvol.cont(); ++itvol)
980  {
981  volume.push_back(*itvol);
982  }*/
983 
984  // We manage attributes before to modify the map; otherwise
985  // it is too late.
986  // Attribute of the second vertex must be removed.
987  CAttributeVertex* secondvertex = removeVertex(alpha0(current));
988  //CVertex secondvertex = *findVertex(alpha0(current));
989 
990  // Attribute of the first vertex must be placed on a non delete dart
991  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
992  {
993  if ( getVertex(*itEdge)!=NULL )
994  {
995  CAttributeVertex * v = removeVertex(*itEdge);
996 
997  if ( !isMarked(alpha1(*itEdge), toDelete) )
998  setVertex(alpha1(*itEdge), v);
999  else if (!isMarked(alpha21(*itEdge), toDelete) )
1000  setVertex(alpha21(*itEdge), v);
1001  else if (!isMarked(alpha31(*itEdge), toDelete) )
1002  setVertex(alpha31(*itEdge), v);
1003  else if (!isMarked(alpha321(*itEdge), toDelete) )
1004  setVertex(alpha321(*itEdge), v);
1005  else if (!isMarked(alpha231(*itEdge), toDelete) )
1006  setVertex(alpha231(*itEdge), v);
1007  else
1008  {
1009  //assert(false);
1010  delete v;
1011  }
1012  break; // We can jump out of the for loop as the attribute is on
1013  // a safe dart.
1014  }
1015  }
1016 
1017  std::vector<std::pair<CDart*,CDart*> > sews;
1018  // Normalement pas la peine std::vector< CDart* > unsews;
1019 
1020  // We push in the stack all the neighboors of the current
1021  // edge that become co-dangling ??? after the removal.
1022  // Moreover, we make the removal manually instead of calling
1023  // contract(current, 1, false) for optimisation reasons.
1024  //for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
1025  for ( CDynamicCoverageEdge itEdge2(this,current); itEdge2.cont();
1026  ++itEdge2 )
1027  {
1028  // Now we update alpha1
1029  t1 = alpha(*itEdge2, 1);
1030  if ( !isMarked(t1, toDelete) )
1031  {
1032  t2 = *itEdge2;
1033  while ( isMarked(t2, toDelete) )
1034  {
1035  t2 = alpha01(t2);
1036  }
1037 
1038  //std::cout<<t1<<"--"<<alpha1(t1)<<" ";
1039  //std::cout<<t2<<"--"<<alpha1(t2)<<" ";
1040  if ( t2 != alpha(t1, 1) )
1041  {
1042  sews.push_back(std::pair<CDart*,CDart*>(t1,alpha1(t1)));
1043  //unsew1(t1);
1044  unlinkAlpha1(t1);
1045  if (!isFree(t2, 1))
1046  {
1047  sews.push_back(std::pair<CDart*,CDart*>(t2,alpha1(t2)));
1048  // unsew1(t2);
1049  unlinkAlpha1(t2);
1050  }
1051  if (t1!=t2 && !isMarked(t1, toDelete))
1052  {
1053  // Normalement pas la peine unsews.push_back(t1);
1054  // sew1(t1,t2);
1055  linkAlpha1(t1,t2);
1056  // std::cout<<"link1 "<<t1<<"--"<<t2<<" ";
1057  }
1058  }
1059  }
1060  }
1061  //std::cout<<std::endl;
1062 
1063  // We test if there is a disconnexion or disparition
1064  std::vector<CDart*>::iterator itcell, itcell2;
1065  std::vector<CDart*> cellafter;
1066  bool disconnection = false;
1067  itcell=vertex.begin();
1068  while( itcell!=vertex.end() && isMarked(*itcell, toDelete) )
1069  ++itcell;
1070 
1071  /*std::cout<<"v before: ";
1072  for (std::vector<CDart*>::iterator ittmp=vertex.begin();
1073  ittmp!=vertex.end(); ++ittmp)
1074  std::cout<<*ittmp<<", ";
1075  std::cout<<std::endl;*/
1076 
1077  if ( itcell==vertex.end() )
1078  {
1079  disconnection = true; // Case where vertex disapeared
1080  // std::cout<<"vertex disconnexion cas 1\n";
1081  }
1082  else
1083  {
1084  for (CDynamicCoverageVertex itv(this, *itcell);
1085  itv.cont(); ++itv)
1086  {
1087  cellafter.push_back(*itv);
1088  }
1089  std::sort(cellafter.begin(), cellafter.end() );
1090 
1091  /*std::cout<<"v after: ";
1092  for (std::vector<CDart*>::iterator ittmp=cellafter.begin();
1093  ittmp!=cellafter.end(); ++ittmp)
1094  std::cout<<*ittmp<<", ";
1095  std::cout<<std::endl;*/
1096 
1097  itcell2 = cellafter.begin();
1098  while ( !disconnection && itcell2!=cellafter.end() )
1099  {
1100  while ( itcell!=vertex.end() &&
1101  isMarked(*itcell, toDelete) )
1102  ++itcell;
1103 
1104  if ( itcell==vertex.end() )
1105  {
1106  //std::cout<<"vertex disconnexion cas 2\n";
1107  disconnection = true; // all darts after are not before
1108  }
1109  else if ( (*itcell)!=(*itcell2) )
1110  {
1111  //std::cout<<"vertex disconnexion cas 3 "<<*itcell<<" != "<<*itcell2<<std::endl;
1112  disconnection = true; // one dart before not find after
1113  }
1114  else
1115  {
1116  ++itcell;
1117  ++itcell2;
1118  }
1119  }
1120 
1121  if ( !disconnection )
1122  {
1123  while ( itcell!=vertex.end() &&
1124  isMarked(*itcell, toDelete) )
1125  ++itcell;
1126  if ( itcell!=vertex.end() )
1127  {
1128  disconnection = true; // all darts after are not before
1129  //std::cout<<"vertex disconnexion cas 4\n";
1130  }
1131  //else std::cout<<"No disconnection\n";
1132  }
1133  }
1134 
1135  //if ( disconnection ) std::cout<<"Disconnect vertex\n";
1136  vertex.clear();
1137  cellafter.clear();
1138  if ( !disconnection )
1139  {
1140  for ( std::vector<std::vector<CDart*> >::iterator itfaces=faces.begin(),
1141  itfacesend=faces.end(); itfaces!=itfacesend; ++itfaces )
1142  {
1143  itcell=(*itfaces).begin();
1144  while( itcell!=(*itfaces).end() && isMarked(*itcell, toDelete) )
1145  {
1146  unsetMark(*itcell, markface);
1147  ++itcell;
1148  }
1149 
1150  if ( itcell==(*itfaces).end() )
1151  {
1152  disconnection = true; // Case where face disapeared
1153  // std::cout<<"face disconnexion cas 1\n";
1154  }
1155  else
1156  {
1157  for (CDynamicCoverageFace itv(this, *itcell);
1158  itv.cont(); ++itv)
1159  {
1160  cellafter.push_back(*itv);
1161  }
1162  std::sort(cellafter.begin(), cellafter.end() );
1163 
1164  itcell2 = cellafter.begin();
1165  while ( !disconnection && itcell2!=cellafter.end() )
1166  {
1167  while ( itcell!=(*itfaces).end() &&
1168  isMarked(*itcell, toDelete) )
1169  {
1170  unsetMark(*itcell, markface);
1171  ++itcell;
1172  }
1173 
1174  if ( itcell==(*itfaces).end() )
1175  {
1176  // std::cout<<"face disconnexion cas 2\n";
1177  disconnection = true; // all darts after are not before
1178  }
1179  else if ( (*itcell)!=(*itcell2) )
1180  {
1181  unsetMark(*itcell, markface);
1182  // std::cout<<"face disconnection cas 3 "<<*itcell<<" != "<<*itcell2<<std::endl;
1183  disconnection = true; // one dart before not find after
1184  }
1185  else
1186  {
1187  unsetMark(*itcell, markface);
1188  ++itcell;
1189  ++itcell2;
1190  }
1191  }
1192 
1193  if ( !disconnection )
1194  {
1195  while ( itcell!=(*itfaces).end() &&
1196  isMarked(*itcell, toDelete) )
1197  {
1198  unsetMark(*itcell, markface);
1199  ++itcell;
1200  }
1201  if ( itcell!=(*itfaces).end() )
1202  {
1203  disconnection = true; // all darts after are not before
1204  //std::cout<<"face disconnexion cas 4\n";
1205  }
1206  // else std::cout<<"No disconnection\n";
1207  }
1208  }
1209  while ( itcell!=(*itfaces).end() )
1210  {
1211  unsetMark(*itcell, markface);
1212  ++itcell;
1213  }
1214  }
1215  }
1216  else
1217  { // If there is already a disconnection, we need only to erase mark
1218  for ( std::vector<std::vector<CDart*> >::iterator itfaces=faces.begin(),
1219  itfacesend=faces.end(); itfaces!=itfacesend; ++itfaces )
1220  {
1221  for ( itcell=(*itfaces).begin(); itcell!=(*itfaces).end();
1222  ++itcell )
1223  {
1224  unsetMark(*itcell, markface);
1225  }
1226  }
1227  }
1228  faces.clear();
1229  cellafter.clear();
1230  assert( isWholeMapUnmarked(markface) );
1231  freeMark(markface);
1232  /*if ( !disconnection )
1233  {
1234  for (itcell=volume.begin(); itcell!=volume.end(); ++itcell)
1235  {
1236  if ( !isMarked(*itcell, toDelete) )
1237  {
1238  if ( cellafter.empty() )
1239  for (CDynamicCoverageVolume itcell2(this, *itcell);
1240  itcell2.cont(); ++itcell2)
1241  {
1242  cellafter.insert(*itcell2);
1243  }
1244  else
1245  {
1246  if ( cellafter.find(*itcell)==cellafter.end() )
1247  {
1248  disconnection = true;
1249  std::cout<<"Disconnect volume\n";
1250  break;
1251  }
1252  }
1253  }
1254  }
1255  }
1256  volume.clear();
1257  if ( cellafter.empty() ) disconnection=true;
1258  else cellafter.clear();*/
1259 
1260  if ( !disconnection )
1261  {
1262  assert( findUnionFindTrees(current, indexVertex)!=
1263  findUnionFindTrees(alpha0(current),indexVertex) );
1264 
1265  // We remove darts from the list of darts.
1266  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
1267  {
1268  removeDartInList( *itEdge );
1269  removeDartInList( alpha0(*itEdge) );
1270  (*itEdge)->setNext(alpha0(*itEdge));
1271  alpha0(*itEdge)->setNext(firstDeleteDart);
1272  firstDeleteDart=*itEdge;
1273 
1274  //assert( getVertex(*itEdge)==NULL );
1275  //assert( getVertex(alpha0(*itEdge))==NULL );
1276  }
1277 
1278  if ( !dangling )
1279  mergeUnionFindTrees(current, alpha0(current), indexVertex);
1280  }
1281  else
1282  {
1283  //std::cout<<"Disconnection: we reput the alpha1.\n";
1284  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
1285  {
1286  unsetMark( *itEdge, toDelete );
1287  unsetMark( alpha0(*itEdge), toDelete );
1288  }
1289  /* Normalement pas la peine!! std::vector<CDart*>::iterator unsewsit;
1290  for ( unsewsit=unsews.begin(); unsewsit!=unsews.end();
1291  ++unsewsit )
1292  unlinkAlpha1(*unsewsit);*/
1293 
1294  std::vector<std::pair<CDart*,CDart*> >::iterator sewsit;
1295  for ( sewsit=sews.begin(); sewsit!=sews.end(); ++sewsit )
1296  {
1297  //std::cout<<(*sewsit).first<<"--"<<(*sewsit).second<<" ";
1298  if ( alpha1((*sewsit).first)!=((*sewsit).second) )
1299  {
1300  if ( !isFree1((*sewsit).first) )
1301  unlinkAlpha1((*sewsit).first);
1302  //unsew1((*sewsit).first);
1303  if ( !isFree1((*sewsit).second) )
1304  //unsew1((*sewsit).second);
1305  unlinkAlpha1((*sewsit).second);
1306  linkAlpha1/*sew1*/((*sewsit).first, (*sewsit).second);
1307  }
1308  }
1309  //std::cout<<std::endl;
1310 
1311  // And we reput the vertex attribute
1312  setVertex(alpha0(current), secondvertex);
1313  //updateVertex(alpha0(current), secondvertex);
1314  }
1315 
1316  sews.clear();
1317  /* assert(checkTopology());
1318  assert(checkEmbeddings(ORBIT_VERTEX, ATTRIBUTE_VERTEX, true));
1319  for( CDynamicCoverageAll cov2(this); cov2.cont(); ++cov2 )
1320  {
1321  assert( !isMarked(*cov2, toDelete) );
1322  assert( !isMarked(alpha0(*cov2), toDelete) );
1323  assert( !isMarked(alpha1(*cov2), toDelete) );
1324  assert( !isMarked(alpha2(*cov2), toDelete) );
1325  assert( !isMarked(alpha3(*cov2), toDelete) );
1326  }*/
1327  //save("in-contract-edges.moka");
1328  }
1329  }
1330  }
1331  negateMaskMark(treated);
1332  assert( isWholeMapUnmarked(treated) );
1333 
1334  // save("after-contract-edges.moka");
1335 
1336  assert(checkTopology());
1337  // assert(checkEmbeddings(ORBIT_VERTEX, ATTRIBUTE_VERTEX, true));
1338  }
1339 
1340  // 2) We contract faces.
1341  if ( false ) //optosimplify & FACE_CONTRACTION )
1342  {
1343  cov.reinit();
1344  while ( cov.cont() )
1345  {
1346  current = cov++;
1347 
1348  if ( !isMarked(current, toDelete) &&
1349  !isMarked(current, treated) )
1350  {
1351  /* std::cout<<"face:";
1352  for (CDynamicCoverage01 ittmp(this,current);ittmp.cont();++ittmp)
1353  std::cout<<*ittmp<<", ";
1354  std::cout<<std::endl; */
1355 
1356  // We contract co-degree two faces.
1357  if ( (alpha2(current) !=alpha1(current) ||
1358  alpha32(current)!=alpha31(current)) &&
1359  alpha10(current)==alpha01(current) &&
1360  findUnionFindTrees(current, indexEdge)!=
1361  findUnionFindTrees(alpha0(current),indexEdge) )
1362  {
1363  // First we mark the current face.
1364  CDynamicCoverage13 itFace(this, current);
1365  for ( ; itFace.cont(); ++itFace)
1366  {
1367  assert ( !isFree0(*itFace) );
1368  assert ( !isMarked(*itFace, treated) );
1369  assert ( !isMarked(alpha0(*itFace), treated) );
1370  setMark( *itFace, treated );
1371  setMark( alpha0(*itFace), treated );
1372  setMark( *itFace, toDelete );
1373  setMark( alpha0(*itFace), toDelete );
1374  }
1375 
1376  while ( cov.cont() && isMarked(*cov, treated) )
1377  ++cov;
1378 
1379  std::vector<CDart*> vertex;
1380  for (CDynamicCoverageVertex itvertex(this, current);
1381  itvertex.cont(); ++itvertex)
1382  {
1383  vertex.push_back(*itvertex);
1384  }
1385  std::vector<CDart*> vertex2;
1386  for (CDynamicCoverageVertex itvertex(this, alpha0(current));
1387  itvertex.cont(); ++itvertex)
1388  {
1389  vertex2.push_back(*itvertex);
1390  }
1391  /*std::vector<CDart*> face;
1392  for (CDynamicCoverageFace itface(this, current);
1393  itface.cont(); ++itface)
1394  {
1395  face.push_back(*itface);
1396  }
1397 
1398  std::vector<CDart*> volume;
1399  for (CDynamicCoverageVolume itvol(this, current);
1400  itvol.cont(); ++itvol)
1401  {
1402  volume.push_back(*itvol);
1403  }*/
1404 
1405  // We manage attributes before to modify the map; otherwise
1406  // it is too late.
1407  // Attribute of the second vertex must be removed.
1408  // CAttributeVertex* secondvertex = removeVertex(alpha0(current));
1409  //CVertex secondvertex = *findVertex(alpha0(current));
1410 
1411  // Attributes of the two vertices must be placed on a
1412  // non delete dart
1413  /*for ( itFace.reinit(); itFace.cont(); ++itFace )
1414  {
1415  if ( getVertex(*itFace)!=NULL )
1416  {
1417  CAttributeVertex * v = removeVertex(*itFace);
1418 
1419  if ( !isMarked(alpha1(*itFace), toDelete) )
1420  setVertex(alpha1(*itFace), v);
1421  else if (!isMarked(alpha21(*itFace), toDelete) )
1422  setVertex(alpha21(*itFace), v);
1423  else if (!isMarked(alpha31(*itFace), toDelete) )
1424  setVertex(alpha31(*itFace), v);
1425  else if (!isMarked(alpha321(*itFace), toDelete) )
1426  setVertex(alpha321(*itFace), v);
1427  else if (!isMarked(alpha231(*itFace), toDelete) )
1428  setVertex(alpha231(*itFace), v);
1429  else
1430  {
1431  assert(false);
1432  delete v;
1433  }
1434  }
1435  if ( getVertex(alpha0(*itFace))!=NULL )
1436  {
1437  CAttributeVertex * v = removeVertex(alpha0(*itFace));
1438 
1439  if ( !isMarked(alpha1(alpha0(*itFace)), toDelete) )
1440  setVertex(alpha1(alpha0(*itFace)), v);
1441  else if (!isMarked(alpha21(alpha0(*itFace)), toDelete) )
1442  setVertex(alpha21(alpha0(*itFace)), v);
1443  else if (!isMarked(alpha31(alpha0(*itFace)), toDelete) )
1444  setVertex(alpha31(alpha0(*itFace)), v);
1445  else if (!isMarked(alpha321(alpha0(*itFace)), toDelete) )
1446  setVertex(alpha321(alpha0(*itFace)), v);
1447  else if (!isMarked(alpha231(alpha0(*itFace)), toDelete) )
1448  setVertex(alpha231(alpha0(*itFace)), v);
1449  else
1450  {
1451  assert(false);
1452  delete v;
1453  }
1454  }
1455  }*/
1456 
1457  std::vector<std::pair<CDart*,CDart*> > sews;
1458  // Normalement pas la peine std::vector< CDart* > unsews;
1459 
1460  // We push in the stack all the neighboors of the current
1461  // edge that become co-dangling ??? after the removal.
1462  // Moreover, we make the removal manually instead of calling
1463  // contract(current, 1, false) for optimisation reasons.
1464  for ( itFace.reinit(); itFace.cont(); ++itFace )
1465  //for ( CDynamicCoverageFace itFace(this,current); itFace.cont(); ++itFace )
1466  {
1467  // Now we update alpha2
1468  t1 = alpha(*itFace, 2);
1469  if ( !isMarked(t1, toDelete) )
1470  {
1471  t2 = *itFace;
1472  while ( isMarked(t2, toDelete) )
1473  {
1474  t2 = alpha12(t2);
1475  }
1476 
1477  //std::cout<<t1<<"--"<<alpha1(t1)<<" ";
1478  //std::cout<<t2<<"--"<<alpha1(t2)<<" ";
1479  if ( t2 != alpha(t1, 2) )
1480  {
1481  sews.push_back(std::pair<CDart*,CDart*>(t1,alpha2(t1)));
1482  unsew2(t1); //unlinkAlpha2(t1);
1483  if (!isFree(t2, 2))
1484  {
1485  sews.push_back(std::pair<CDart*,CDart*>(t2,alpha2(t2)));
1486  unsew2(t2); //unlinkAlpha2(t2);
1487  }
1488  if (t1!=t2 && !isMarked(t1, toDelete))
1489  {
1490  // Normalement pas la peine unsews.push_back(t1);
1491  sew2(t1,t2); //linkAlpha2(t1,t2);
1492  // std::cout<<"link1 "<<t1<<"--"<<t2<<" ";
1493  }
1494  }
1495  }
1496  }
1497  //std::cout<<std::endl;
1498 
1499  // We test if there is a disconnexion or disparition
1500  std::vector<CDart*>::iterator itcell;
1501  std::set<CDart*> cellafter;
1502  bool disconnection = false;
1503  for (itcell=vertex.begin(); itcell!=vertex.end(); ++itcell)
1504  {
1505  if ( !isMarked(*itcell, toDelete) )
1506  {
1507  if ( cellafter.empty() )
1508  for (CDynamicCoverageVertex itcell2(this, *itcell);
1509  itcell2.cont(); ++itcell2)
1510  {
1511  cellafter.insert(*itcell2);
1512  }
1513  else
1514  {
1515  if ( cellafter.find(*itcell)==cellafter.end() )
1516  {
1517  disconnection = true;
1518  // std::cout<<"Disconnect vertex\n";
1519  break;
1520  }
1521  }
1522  }
1523  }
1524  vertex.clear();
1525  if ( cellafter.empty() ) disconnection=true;
1526  else cellafter.clear();
1527  for (itcell=vertex2.begin(); itcell!=vertex2.end(); ++itcell)
1528  {
1529  if ( !isMarked(*itcell, toDelete) )
1530  {
1531  if ( cellafter.empty() )
1532  for (CDynamicCoverageVertex itcell2(this, *itcell);
1533  itcell2.cont(); ++itcell2)
1534  {
1535  cellafter.insert(*itcell2);
1536  }
1537  else
1538  {
1539  if ( cellafter.find(*itcell)==cellafter.end() )
1540  {
1541  disconnection = true;
1542  // std::cout<<"Disconnect vertex\n";
1543  break;
1544  }
1545  }
1546  }
1547  }
1548  vertex2.clear();
1549  if ( cellafter.empty() ) disconnection=true;
1550  else cellafter.clear();
1551  /* if ( !disconnection )
1552  {
1553  for (itcell=face.begin(); itcell!=face.end(); ++itcell)
1554  {
1555  if ( !isMarked(*itcell, toDelete) )
1556  {
1557  if ( cellafter.empty() )
1558  for (CDynamicCoverageFace itcell2(this, *itcell);
1559  itcell2.cont(); ++itcell2)
1560  {
1561  cellafter.insert(*itcell2);
1562  }
1563  else
1564  {
1565  if ( cellafter.find(*itcell)==cellafter.end() )
1566  {
1567  disconnection = true;
1568  //std::cout<<"Disconnect face\n";
1569  break;
1570  }
1571  }
1572  }
1573  }
1574  }
1575  face.clear();
1576  if ( cellafter.empty() ) disconnection=true;
1577  else cellafter.clear();
1578  if ( !disconnection )
1579  {
1580  for (itcell=volume.begin(); itcell!=volume.end(); ++itcell)
1581  {
1582  if ( !isMarked(*itcell, toDelete) )
1583  {
1584  if ( cellafter.empty() )
1585  for (CDynamicCoverageVolume itcell2(this, *itcell);
1586  itcell2.cont(); ++itcell2)
1587  {
1588  cellafter.insert(*itcell2);
1589  }
1590  else
1591  {
1592  if ( cellafter.find(*itcell)==cellafter.end() )
1593  {
1594  disconnection = true;
1595  // std::cout<<"Disconnect volume\n";
1596  break;
1597  }
1598  }
1599  }
1600  }
1601  }
1602  volume.clear();
1603  if ( cellafter.empty() ) disconnection=true;
1604  else cellafter.clear(); */
1605 
1606  if ( !disconnection )
1607  {
1608  assert( findUnionFindTrees(current, indexEdge)!=
1609  findUnionFindTrees(alpha1(current),indexEdge) );
1610 
1611  // We remove darts from the list of darts.
1612  for ( itFace.reinit(); itFace.cont(); ++itFace )
1613  {
1614  removeDartInList( *itFace );
1615  removeDartInList( alpha0(*itFace) );
1616  (*itFace)->setNext(alpha0(*itFace));
1617  alpha0(*itFace)->setNext(firstDeleteDart);
1618  firstDeleteDart=*itFace;
1619 
1620  //assert( getVertex(*itFace)==NULL );
1621  //assert( getVertex(alpha0(*itFace))==NULL );
1622  }
1623 
1624  if ( !dangling )
1625  mergeUnionFindTrees(current, alpha1(current), indexEdge);
1626  }
1627  else
1628  {
1629  //std::cout<<"Disconnection: we reput the alpha1.\n";
1630  for ( itFace.reinit(); itFace.cont(); ++itFace )
1631  {
1632  unsetMark( *itFace, toDelete );
1633  unsetMark( alpha0(*itFace), toDelete );
1634  }
1635  /* Normalement pas la peine!! std::vector<CDart*>::iterator unsewsit;
1636  for ( unsewsit=unsews.begin(); unsewsit!=unsews.end();
1637  ++unsewsit )
1638  unlinkAlpha1(*unsewsit);*/
1639 
1640  std::vector<std::pair<CDart*,CDart*> >::iterator sewsit;
1641  for ( sewsit=sews.begin(); sewsit!=sews.end(); ++sewsit )
1642  {
1643  //std::cout<<(*sewsit).first<<"--"<<(*sewsit).second<<" ";
1644  if ( alpha2((*sewsit).first)!=((*sewsit).second) )
1645  {
1646  if ( !isFree2((*sewsit).first) )
1647  unsew2/*unlinkAlpha2*/((*sewsit).first);
1648  if ( !isFree2((*sewsit).second) )
1649  unsew2/*unlinkAlpha2*/((*sewsit).second);
1650  sew2/*linkAlpha2*/((*sewsit).first, (*sewsit).second);
1651  }
1652  }
1653  //std::cout<<std::endl;
1654 
1655  // And we reput the vertex attribute
1656  // setVertex(alpha0(current), secondvertex);
1657  //updateVertex(alpha(current), secondvertex);
1658  }
1659 
1660  sews.clear();
1661  /* assert(checkTopology());
1662  assert(checkEmbeddings(ORBIT_VERTEX, ATTRIBUTE_VERTEX, true));
1663  for( CDynamicCoverageAll cov2(this); cov2.cont(); ++cov2 )
1664  {
1665  assert( !isMarked(*cov2, toDelete) );
1666  assert( !isMarked(alpha0(*cov2), toDelete) );
1667  assert( !isMarked(alpha1(*cov2), toDelete) );
1668  assert( !isMarked(alpha2(*cov2), toDelete) );
1669  assert( !isMarked(alpha3(*cov2), toDelete) );
1670  }
1671  save("in-contract-faces.moka");*/
1672  }
1673  else
1674  {
1675  for ( CDynamicCoverageFace itFace(this, current);
1676  itFace.cont(); ++itFace )
1677  {
1678  setMark( *itFace, treated );
1679  }
1680  }
1681  }
1682  }
1683  negateMaskMark(treated);
1684  assert( isWholeMapUnmarked(treated) );
1685 
1686  // save("after-contract-faces.moka");
1687 
1688  assert(checkTopology());
1689  //assert(checkEmbeddings(ORBIT_VERTEX, ATTRIBUTE_VERTEX, true));
1690  }
1691 
1692  // 3) We contract volumes.
1693  // Not necessary for 3D objects that is already simplified by removal
1694  // operations. Indeed, we are sure there are exactly one volume which must
1695  // not be simplified...
1696  /* cov.reinit();
1697  while ( cov.cont() )
1698  {
1699  current = cov++;
1700 
1701  if ( !isMarked(current,treated) )
1702  {
1703  bool deleteVol= true;
1704  CStaticCoverage01 itVol(this, current);
1705  for ( ; itVol.cont(); ++itVol )
1706  {
1707  setMark( *itVol, treated );
1708  setMark( alpha2(*itVol), treated );
1709 
1710  if ( isFree2(*itVol) ||
1711  alpha2 (*itVol)==alpha1 (*itVol) ||
1712  alpha32(*itVol)==alpha31(*itVol) ||
1713  alpha21(*itVol)!=alpha12(*itVol) )
1714  deleteVol = false;
1715  }
1716 
1717  if ( deleteVol )
1718  {
1719  // First we mark the current vol todelete.
1720  for ( itVol.reinit(); itVol.cont(); ++itVol )
1721  {
1722  setMark( *itVol, toDelete );
1723  setMark( alpha2(*itVol), toDelete );
1724  }
1725 
1726  while ( cov.cont() && isMarked(*cov, treated) )
1727  ++cov;
1728 
1729  // Second we remove the darts from their list.
1730  for ( itVol.reinit(); itVol.cont(); ++itVol )
1731  {
1732  removeDartInList( *itVol );
1733  removeDartInList( alpha2(*itVol) );
1734  (*itVol)->setNext(alpha2(*itVol));
1735  alpha2(*itVol)->setNext(firstDeleteDart);
1736  firstDeleteDart=*itVol;
1737 
1738  if ( getVertex(*itVol)!=NULL )
1739  {
1740  CAttributeVertex * v = removeVertex(*itVol);
1741 
1742  if ( !isMarked(alpha3(*itVol), toDelete) )
1743  setVertex(alpha3(*itVol), v);
1744  else if ( !isMarked(alpha23(*itVol), toDelete) )
1745  setVertex(alpha23(*itVol), v);
1746  else
1747  delete v;
1748  }
1749  else if ( getVertex(alpha2(*itVol))!=NULL )
1750  {
1751  CAttributeVertex * v = removeVertex(alpha2(*itVol));
1752 
1753  if ( !isMarked(alpha3(*itVol), toDelete) )
1754  setVertex(alpha3(*itVol), v);
1755  else if ( !isMarked(alpha23(*itVol), toDelete) )
1756  setVertex(alpha23(*itVol), v);
1757  else
1758  delete v;
1759  }
1760  }
1761 
1762  // Second, we make the removal manually instead of calling
1763  // remove(current, 0, false) for optimisation reasons.
1764  for ( itVol.reinit(); itVol.cont(); ++itVol )
1765  {
1766  t1 = alpha(*itVol, 3);
1767  if ( !isMarked(t1, toDelete) )
1768  {
1769  t2 = *itVol;
1770  while ( isMarked(t2, toDelete) )
1771  {
1772  t2 = alpha23(t2);
1773  }
1774 
1775  if ( t2 != alpha(t1, 3) )
1776  {
1777  unlinkAlpha3(t1);
1778  if (!isFree(t2, 3)) unlinkAlpha3(t2);
1779  if (t1!=t2) linkAlpha3(t1, t2);
1780  }
1781  }
1782  }
1783  }
1784  }
1785  }
1786  */
1787 
1788  // 4) We remove all the darts marked toDelete
1789  while ( firstDeleteDart!=NULL )
1790  {
1791  t1 = firstDeleteDart->getNext();
1792  delDart(firstDeleteDart);
1793  firstDeleteDart = t1;
1794  ++nbRemove;
1795  }
1796 
1797  assert( isWholeMapUnmarked(toDelete) );
1798  assert( isWholeMapUnmarked(treated) );
1799 
1800  freeMark(toDelete);
1801  freeMark(treated);
1802 
1803  freeDirectInfo(indexVertex);
1804  freeDirectInfo(indexEdge);
1805 
1806  // save("after-simplification-3D-contraction.moka");
1807  assert(checkTopology());
1808  // assert(checkEmbeddings(ORBIT_VERTEX, ATTRIBUTE_VERTEX, true));
1809 
1810  return nbRemove;
1811 }
1812 //******************************************************************************
1813 unsigned int CGMapVertex::simplify3DObject(unsigned int optosimplify)
1814 {
1815  return simplify3DObjectRemoval(optosimplify) +
1816  simplify3DObjectContraction(optosimplify);
1817 }
1818 //******************************************************************************
1819 unsigned int CGMapVertex::simplify2DObject(int AMark0, int AMark1)
1820 {
1821  // Simplify a 2D map in its minimal form, without use shifting operations, and
1822  // by keeping each cell homeomorphic to a ball.
1823  // This method suppose that each cell is initially homeomorphic to a ball, and
1824  // that there is no dangling cell.
1825  // First we remove each degree two edges, last each degree two vertex.
1826  int toDelete = getNewMark();
1827  int treated = getNewMark();
1828  int cell = getNewMark();
1829  CDart* current = NULL;
1830  CDart* t1 = NULL;
1831  CDart* t2 = NULL;
1832  std::stack<CDart*> FToTreat;
1833  bool dangling = false;
1834  unsigned int nbRemove = 0;
1835 
1836  int toDelete0 = (AMark0==-1?toDelete:AMark0);
1837  int toDelete1 = (AMark1==-1?toDelete:AMark1);
1838 
1839  int indexFace = getNewDirectInfo();
1840  if ( indexFace!=-1 )
1841  initUnionFindTrees(indexFace, ORBIT_FACE);
1842  else
1843  {
1844  std::cout<<"Not enough directInfo to use union-find trees."<<std::endl;
1845  return 0;
1846  }
1847 
1848  // 1) We remove edges.
1849  CDynamicCoverageAll cov(this);
1850  while ( cov.cont() )
1851  {
1852  if ( ! FToTreat.empty() )
1853  {
1854  current = FToTreat.top();
1855  FToTreat.pop();
1856  dangling = true;
1857  }
1858  else
1859  {
1860  current = cov++;
1861  dangling = false;
1862  }
1863 
1864  if ( !isMarked(current, toDelete1) &&
1865  (dangling || !isMarked(current, treated)) )
1866  {
1867  if ( !isFree2(current) )
1868  {
1869  // We remove dangling edges and degree two edges.
1870  if ( (alpha1(current) !=alpha2(current) ||
1871  alpha01(current)!=alpha02(current)) &&
1872  alpha23(current)==alpha32(current) &&
1873  ( dangling ||
1874  findUnionFindTrees(current, indexFace)!=
1875  findUnionFindTrees(alpha2(current),indexFace)) )
1876  {
1877  // First we mark the current edge.
1878  CDynamicCoverage02 itEdge(this, current);
1879  for ( ; itEdge.cont(); ++itEdge )
1880  {
1881  setMark( *itEdge, treated );
1882  setMark( alpha3(*itEdge), treated );
1883  // setMark( *itEdge, cell );
1884  // setMark( alpha3(*itEdge), cell );
1885  setMark( *itEdge, toDelete1 );
1886  setMark( alpha3(*itEdge), toDelete1 );
1887  }
1888 
1889  // Second, we push in the stack all the neighboors of the current
1890  // edge that become dangling after the removal.
1891  // Moreover, we make the removal manually instead of calling
1892  // remove(current, 1, false) for optimisation reasons.
1893  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
1894  {
1895  if ( alpha12(*itEdge)==alpha21(*itEdge) &&
1896  !isMarked(alpha1(*itEdge), toDelete1) &&
1897  !isFree2(alpha1(*itEdge)) )
1898  //&& !isMarked(alpha1(*itEdge),toDelete) )
1899  {
1900  FToTreat.push(alpha1(*itEdge));
1901  }
1902 
1903  // Now we update alpha2
1904  t1 = alpha(*itEdge, 1);
1905  if ( !isMarked(t1, toDelete1) )
1906  {
1907  t2 = *itEdge;
1908  while ( isMarked(t2, toDelete1) )
1909  {
1910  t2 = alpha21(t2);
1911  }
1912 
1913  if ( t2 != alpha(t1, 1) )
1914  {
1915  unsew(t1, 1);
1916  if (!isFree(t2, 1)) unsew(t2, 1);
1917  if (t1!=t2) sew(t1, t2, 1);
1918  }
1919  }
1920  }
1921 
1922  if ( !dangling )
1923  mergeUnionFindTrees(current, alpha2(current), indexFace);
1924  }
1925  else
1926  {
1927  CDynamicCoverage02 itEdge(this, current);
1928  for ( ; itEdge.cont(); ++itEdge )
1929  {
1930  setMark( *itEdge, treated );
1931  setMark( alpha3(*itEdge), treated );
1932  }
1933  }
1934  }
1935  else
1936  {
1937  CDynamicCoverage0 itEdge(this, current);
1938  for ( ; itEdge.cont(); ++itEdge )
1939  {
1940  setMark( *itEdge, treated );
1941  setMark( alpha3(*itEdge), treated );
1942  }
1943  }
1944  }
1945  }
1946  negateMaskMark(treated);
1947 
1948  // 2) We remove vertices. This is simpler since a vertex can not be dangling.
1949  cov.reinit();
1950  while ( cov.cont() )
1951  {
1952  current = cov++;
1953 
1954  if ( !isMarked(current,treated) && !isMarked(current, toDelete1) &&
1955  !isMarked(current, toDelete0) )
1956  {
1957  bool deleteVertex = true;
1958  CStaticCoverage23 itVertex(this, current);
1959  for ( ; itVertex.cont(); ++itVertex )
1960  {
1961  setMark( *itVertex, treated );
1962  setMark( alpha1(*itVertex), treated );
1963 
1964  if ( isFree1(*itVertex) ||
1965  alpha0 (*itVertex)==alpha1 (*itVertex) ||
1966  alpha1 (*itVertex)==alpha2 (*itVertex) ||
1967  alpha01(*itVertex)==alpha02(*itVertex) ||
1968  alpha12(*itVertex)!=alpha21(*itVertex) )
1969  deleteVertex = false;
1970  }
1971 
1972  if ( deleteVertex )
1973  {
1974  // First we mark the current vertex.
1975  for ( itVertex.reinit(); itVertex.cont(); ++itVertex )
1976  {
1977  setMark( *itVertex, toDelete0 );
1978  setMark( alpha1(*itVertex), toDelete0 );
1979  }
1980 
1981  // Second, we make the removal manually instead of calling
1982  // remove(current, 0, false) for optimisation reasons.
1983  for ( itVertex.reinit(); itVertex.cont(); ++itVertex )
1984  {
1985  t1 = alpha(*itVertex, 0);
1986  if ( !isMarked(t1, toDelete0) )
1987  {
1988  t2 = *itVertex;
1989  while ( isMarked(t2, toDelete0) )
1990  {
1991  t2 = alpha10(t2);
1992  }
1993 
1994  if ( t2 != alpha(t1, 0) )
1995  {
1996  unsew(t1, 0);
1997  if (!isFree(t2, 0)) unsew(t2, 0);
1998  if (t1!=t2) sew(t1, t2, 0);
1999  }
2000  }
2001  }
2002  }
2003  }
2004  }
2005 
2006  // 4) We remove all the darts marked toDelete
2007  for ( cov.reinit(); cov.cont(); )
2008  {
2009  current = cov++;
2010 
2011  // assert(!isMarked(current,cell));
2012 
2013  unsetMark(current,treated);
2014  if ( isMarked(current, toDelete) )
2015  {
2016  delMapDart(current);
2017  }
2018 
2019  if ( isMarked(current, toDelete0) ||
2020  isMarked(current, toDelete1) )
2021  ++nbRemove;
2022  }
2023 
2024  freeMark(toDelete);
2025  freeMark(treated);
2026  freeMark(cell);
2027 
2028  freeDirectInfo(indexFace);
2029 
2030  return nbRemove;
2031 }
2032 //******************************************************************************
2033 unsigned int CGMapVertex::simplify2DObjectRemoval(unsigned int optosimplify)
2034 {
2035  // Simplify a 2D map in its minimal form, without use shifting operations,
2036  // and by keeping each cell homeomorphic to a ball.
2037  // This method suppose that each cell is initially homeomorphic to a ball,
2038  // and that there is no dangling cell.
2039  // First we remove each degree two edge, last each
2040  // degree two vertex.
2041  if ( !(optosimplify & EDGE_REMOVAL ||
2042  optosimplify & VERTEX_REMOVAL ) )
2043  return 0;
2044 
2045  int toDelete = getNewMark();
2046  int treated = getNewMark();
2047  CDart* current = NULL;
2048  CDart* t1 = NULL;
2049  CDart* t2 = NULL;
2050  std::stack<CDart*> FToTreat;
2051  bool dangling = false;
2052  unsigned int nbRemove = 0;
2053 
2054  int indexFace = getNewDirectInfo();
2055  if ( indexFace!=-1 )
2056  initUnionFindTrees(indexFace, ORBIT_FACE);
2057  else
2058  {
2059  std::cout<<"Not enough directInfo to use union-find trees."<<std::endl;
2060  return 0;
2061  }
2062 
2063  CDart* firstDeleteDart = NULL;
2064 
2065  // 1) We remove edges.
2066  CDynamicCoverageAll cov(this);
2067  if ( optosimplify & EDGE_REMOVAL )
2068  {
2069  cov.reinit();
2070  while ( cov.cont() )
2071  {
2072  if ( ! FToTreat.empty() )
2073  {
2074  current = FToTreat.top();
2075  FToTreat.pop();
2076  dangling = true;
2077  }
2078  else
2079  {
2080  current = cov++;
2081  dangling = false;
2082  }
2083 
2084  if ( !isMarked(current, toDelete) &&
2085  (dangling || !isMarked(current, treated)) )
2086  {
2087  if ( !isFree2(current) )
2088  {
2089  // We remove dangling edges and degree two edges.
2090  if ( (alpha1(current) !=alpha2(current) ||
2091  alpha01(current)!=alpha02(current)) &&
2092  alpha23(current)==alpha32(current) &&
2093  ( dangling ||
2094  findUnionFindTrees(current, indexFace)!=
2095  findUnionFindTrees(alpha2(current),indexFace)) )
2096  {
2097  // First we mark the current edge.
2098  CDynamicCoverage02 itEdge(this, current);
2099  for ( ; itEdge.cont(); ++itEdge )
2100  {
2101  setMark( *itEdge, treated );
2102  setMark( *itEdge, toDelete );
2103  setMark( alpha3(*itEdge), treated );
2104  setMark( alpha3(*itEdge), toDelete );
2105  }
2106 
2107  while ( cov.cont() && isMarked(*cov, treated) )
2108  ++cov;
2109 
2110  // Second we manage vertex attributes, and remove darts
2111  // from the list of darts.
2112  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
2113  {
2114  removeDartInList( *itEdge );
2115  if ( !isFree3(*itEdge) )
2116  {
2117  removeDartInList( alpha3(*itEdge) );
2118  (*itEdge)->setNext(alpha3(*itEdge));
2119  alpha3(*itEdge)->setNext(firstDeleteDart);
2120  }
2121  else
2122  (*itEdge)->setNext(firstDeleteDart);
2123  firstDeleteDart=*itEdge;
2124 
2125  if ( getVertex(*itEdge)!=NULL )
2126  {
2127  CAttributeVertex * v = removeVertex(*itEdge);
2128 
2129  if ( !isMarked(alpha1(*itEdge), toDelete) )
2130  setVertex(alpha1(*itEdge), v);
2131  else if ( !isMarked(alpha21(*itEdge), toDelete) )
2132  setVertex(alpha21(*itEdge), v);
2133  else
2134  delete v;
2135  }
2136 
2137  if ( !isFree3(*itEdge) )
2138  {
2139  t1=alpha3(*itEdge);
2140  if ( getVertex(t1)!=NULL )
2141  {
2142  CAttributeVertex * v = removeVertex(t1);
2143 
2144  if ( !isMarked(alpha1(t1), toDelete) )
2145  setVertex(alpha1(t1), v);
2146  else if ( !isMarked(alpha21(t1), toDelete) )
2147  setVertex(alpha21(t1), v);
2148  else
2149  delete v;
2150  }
2151  }
2152  }
2153 
2154  // Third, we push in the stack all the neighboors of the current
2155  // edge that become dangling after the removal.
2156  // Moreover, we make the removal manually instead of calling
2157  // remove(current, 1, false) for optimisation reasons.
2158  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
2159  {
2160  if ( alpha12(*itEdge)==alpha21(*itEdge) &&
2161  !isMarked(alpha1(*itEdge), toDelete) &&
2162  !isFree2(alpha1(*itEdge)) )
2163  {
2164  FToTreat.push(alpha1(*itEdge));
2165  }
2166 
2167  // Now we update alpha1
2168  t1 = alpha(*itEdge, 1);
2169  if ( !isMarked(t1, toDelete) )
2170  {
2171  t2 = *itEdge;
2172  while ( isMarked(t2, toDelete) )
2173  {
2174  t2 = alpha21(t2);
2175  }
2176 
2177  if ( t2 != alpha(t1, 1) )
2178  {
2179 
2180  //unsew1(t1);
2181  unlinkAlpha1(t1);
2182  if ( !isFree3(t1) ) unlinkAlpha1(alpha3(t1));
2183  if (!isFree(t2, 1))
2184  {
2185  //unsew1(t2);
2186  unlinkAlpha1(t2);
2187  if ( !isFree3(t2) ) unlinkAlpha1(alpha3(t2));
2188  }
2189  if (t1!=t2)
2190  {
2191  //sew1(t1, t2);
2192  linkAlpha1(t1, t2);
2193  if ( !isFree3(t1) ) linkAlpha1(alpha3(t1), alpha3(t2));
2194  }
2195  }
2196  }
2197  }
2198 
2199  if ( !dangling )
2200  mergeUnionFindTrees(current, alpha2(current), indexFace);
2201  }
2202  else
2203  {
2204  for ( CDynamicCoverage02 itEdge(this, current);
2205  itEdge.cont(); ++itEdge )
2206  {
2207  setMark( *itEdge, treated );
2208  setMark( alpha3(*itEdge), treated );
2209  }
2210  }
2211  }
2212  else
2213  {
2214  for ( CDynamicCoverage0 itEdge(this, current);
2215  itEdge.cont(); ++itEdge )
2216  {
2217  setMark( *itEdge, treated );
2218  setMark( alpha3(*itEdge), treated );
2219  }
2220  }
2221  }
2222  }
2223  negateMaskMark(treated);
2224  assert( isWholeMapUnmarked(treated) );
2225  //save("after-remove-edges.moka");
2226  }
2227 
2228  // 2) We remove vertices. This is simpler since a vertex can not be dangling.
2229  if ( optosimplify & VERTEX_REMOVAL )
2230  {
2231  cov.reinit();
2232  while ( cov.cont() )
2233  {
2234  current = cov++;
2235 
2236  if ( !isMarked(current,treated) )
2237  {
2238  assert( !isMarked(current, toDelete) );
2239  bool deleteVertex = true;
2240  CStaticCoverage23 itVertex(this, current);
2241  for ( ; itVertex.cont(); ++itVertex )
2242  {
2243  setMark( *itVertex, treated );
2244  setMark( alpha1(*itVertex), treated );
2245 
2246  if ( isFree1(*itVertex) ||
2247  alpha0 (*itVertex)==alpha1 (*itVertex) ||
2248  alpha1 (*itVertex)==alpha2 (*itVertex) ||
2249  alpha01(*itVertex)==alpha02(*itVertex) ||
2250  alpha12(*itVertex)!=alpha21(*itVertex) )
2251  deleteVertex = false;
2252  }
2253 
2254  if ( deleteVertex )
2255  {
2256  // First we mark the current vertex todelete.
2257  for ( itVertex.reinit(); itVertex.cont(); ++itVertex )
2258  {
2259  setMark( *itVertex, toDelete );
2260  setMark( alpha1(*itVertex), toDelete );
2261  }
2262 
2263  while ( cov.cont() && isMarked(*cov, treated) )
2264  ++cov;
2265 
2266  // Second we remove the darts from their list.
2267  for ( itVertex.reinit(); itVertex.cont(); ++itVertex )
2268  {
2269  removeDartInList( *itVertex );
2270  removeDartInList( alpha1(*itVertex) );
2271  (*itVertex)->setNext(alpha1(*itVertex));
2272  alpha1(*itVertex)->setNext(firstDeleteDart);
2273  firstDeleteDart=*itVertex;
2274 
2275  if ( getVertex(*itVertex)!=NULL )
2276  delVertex(*itVertex);
2277  else if ( getVertex(alpha1(*itVertex))!=NULL )
2278  delVertex(alpha1(*itVertex));
2279  }
2280 
2281  // Second, we make the removal manually instead of calling
2282  // remove(current, 0, false) for optimisation reasons.
2283  for ( itVertex.reinit(); itVertex.cont(); ++itVertex )
2284  {
2285  t1 = alpha(*itVertex, 0);
2286  if ( !isMarked(t1, toDelete) )
2287  {
2288  t2 = *itVertex;
2289  while ( isMarked(t2, toDelete) )
2290  {
2291  t2 = alpha10(t2);
2292  }
2293 
2294  if ( t2 != alpha(t1, 0) )
2295  {
2296  unlinkAlpha0(t1);
2297  //unsew0(t1);
2298  if (!isFree(t2, 0))
2299  //unsew0(t2);
2300  unlinkAlpha0(t2);
2301  if (t1!=t2)
2302  linkAlpha0(t1, t2);
2303  //sew0(t1, t2);
2304  }
2305  }
2306  }
2307  }
2308  }
2309  }
2310  negateMaskMark(treated);
2311  assert( isWholeMapUnmarked(treated) );
2312  //save("after-all-removal.moka");
2313  }
2314 
2315  // 4) We remove all the darts marked toDelete
2316  while ( firstDeleteDart!=NULL )
2317  {
2318  t1 = firstDeleteDart->getNext();
2319  delDart(firstDeleteDart);
2320  firstDeleteDart = t1;
2321  ++nbRemove;
2322  }
2323 
2324  assert( isWholeMapUnmarked(toDelete) );
2325  assert( isWholeMapUnmarked(treated) );
2326 
2327  freeMark(toDelete);
2328  freeMark(treated);
2329 
2330  freeDirectInfo(indexFace);
2331 
2332  return nbRemove;
2333 }
2334 //******************************************************************************
2335 unsigned int CGMapVertex::simplify2DObjectContraction(unsigned int optosimplify)
2336 {
2337  if ( !(optosimplify & EDGE_CONTRACTION ||
2338  optosimplify & FACE_CONTRACTION) )
2339  return 0;
2340 
2341  // Simplify a 2D map in its minimal form, without use shifting operations,
2342  // and by keeping each cell homeomorphic to a ball.
2343  // This method suppose that each cell is initially homeomorphic to a ball,
2344  // and that there is no dangling cell.
2345  // First we contract each codegree two edge, then each codegree two face,
2346  // last each codegree two volume.
2347  // std::cout<<"simplify3DObjectContraction()"<<std::endl;
2348  int toDelete = getNewMark();
2349  int treated = getNewMark();
2350  CDart* current = NULL;
2351  CDart* t1 = NULL;
2352  CDart* t2 = NULL;
2353  std::stack<CDart*> FToTreat;
2354  bool dangling = false;
2355  unsigned int nbRemove = 0;
2356 
2357  int indexVertex = getNewDirectInfo();
2358  int indexEdge = getNewDirectInfo();
2359  if ( indexVertex!=-1 && indexEdge!=-1 )
2360  initUnionFindTreesVerticesEdges(indexVertex, indexEdge);
2361  else
2362  {
2363  std::cout<<"Not enough directInfo to use union-find trees."<<std::endl;
2364  return 0;
2365  }
2366 
2367  CDart* firstDeleteDart = NULL;
2368 
2369  // 1) We contract edges.
2370  CDynamicCoverageAll cov(this);
2371 
2372  if ( optosimplify & EDGE_CONTRACTION )
2373  {
2374  while ( cov.cont() )
2375  {
2376  current = cov++;
2377  assert(isFree3(current));
2378 
2379  if ( !isMarked(current,toDelete) &&
2380  !isMarked(current, treated) )
2381  {
2382  // We contract co-degree two edges.
2383  if ((alpha1(current) !=alpha2(current) ||
2384  alpha01(current)!=alpha02(current)) &&
2385  findUnionFindTrees(current, indexVertex)!=
2386  findUnionFindTrees(alpha0(current),indexVertex) )
2387  {
2388  // First we mark the current edge.
2389  //CStaticCoverage23 itEdge(this, current);
2390  CDynamicCoverage23 itEdge(this, current);
2391  for ( ; itEdge.cont(); ++itEdge)
2392  {
2393  assert ( !isFree0(*itEdge) );
2394  setMark( *itEdge, treated );
2395  setMark( alpha0(*itEdge), treated );
2396  setMark( *itEdge, toDelete );
2397  setMark( alpha0(*itEdge), toDelete );
2398  }
2399 
2400  while ( cov.cont() && isMarked(*cov, treated) )
2401  ++cov;
2402 
2403  std::vector<CDart*> vertex;
2404  for (CDynamicCoverageVertex itvertex(this, current);
2405  itvertex.cont(); ++itvertex)
2406  {
2407  vertex.push_back(*itvertex);
2408  }
2409  for (CDynamicCoverageVertex itvertex(this, alpha0(current));
2410  itvertex.cont(); ++itvertex)
2411  {
2412  vertex.push_back(*itvertex);
2413  }
2414 
2415  std::vector<CDart*> face;
2416  for (CDynamicCoverageFace itface(this, current);
2417  itface.cont(); ++itface)
2418  {
2419  face.push_back(*itface);
2420  }
2421 
2422  // We manage attributes before to modify the map; otherwise
2423  // it is too late.
2424  // Attribute of the second vertex must be removed.
2425  CAttributeVertex* secondvertex = removeVertex(alpha0(current));
2426  //CVertex secondvertex = *findVertex(alpha0(current));
2427 
2428  // Attribute of the first vertex must be placed on a non delete dart
2429  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
2430  {
2431  if ( getVertex(*itEdge)!=NULL )
2432  {
2433  CAttributeVertex * v = removeVertex(*itEdge);
2434 
2435  if ( !isMarked(alpha1(*itEdge), toDelete) )
2436  setVertex(alpha1(*itEdge), v);
2437  else if (!isMarked(alpha21(*itEdge), toDelete) )
2438  setVertex(alpha21(*itEdge), v);
2439  else if (!isMarked(alpha31(*itEdge), toDelete) )
2440  setVertex(alpha31(*itEdge), v);
2441  else if (!isMarked(alpha321(*itEdge), toDelete) )
2442  setVertex(alpha321(*itEdge), v);
2443  else if (!isMarked(alpha231(*itEdge), toDelete) )
2444  setVertex(alpha231(*itEdge), v);
2445  else
2446  {
2447  assert(false);
2448  delete v;
2449  }
2450  break; // We can jump out of the for loop as the attribute is on
2451  // a safe dart.
2452  }
2453  }
2454 
2455  std::vector<std::pair<CDart*,CDart*> > sews;
2456  // Normalement pas la peine std::vector< CDart* > unsews;
2457 
2458  // We push in the stack all the neighboors of the current
2459  // edge that become co-dangling ??? after the removal.
2460  // Moreover, we make the removal manually instead of calling
2461  // contract(current, 1, false) for optimisation reasons.
2462  //for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
2463  for ( CDynamicCoverageEdge itEdge(this,current); itEdge.cont();
2464  ++itEdge )
2465  {
2466  // Now we update alpha1
2467  t1 = alpha(*itEdge, 1);
2468  if ( !isMarked(t1, toDelete) )
2469  {
2470  t2 = *itEdge;
2471  while ( isMarked(t2, toDelete) )
2472  {
2473  t2 = alpha01(t2);
2474  }
2475 
2476  //std::cout<<t1<<"--"<<alpha1(t1)<<" ";
2477  //std::cout<<t2<<"--"<<alpha1(t2)<<" ";
2478  if ( t2 != alpha(t1, 1) )
2479  {
2480  sews.push_back(std::pair<CDart*,CDart*>(t1,alpha1(t1)));
2481  //unsew1(t1);
2482  unlinkAlpha1(t1);
2483  if (!isFree(t2, 1))
2484  {
2485  sews.push_back(std::pair<CDart*,CDart*>(t2,alpha1(t2)));
2486  // unsew1(t2);
2487  unlinkAlpha1(t2);
2488  }
2489  if (t1!=t2 && !isMarked(t1, toDelete))
2490  {
2491  // Normalement pas la peine unsews.push_back(t1);
2492  // sew1(t1,t2);
2493  linkAlpha1(t1,t2);
2494  // std::cout<<"link1 "<<t1<<"--"<<t2<<" ";
2495  }
2496  }
2497  }
2498  }
2499  //std::cout<<std::endl;
2500 
2501  // We test if there is a disconnexion or disparition
2502  std::vector<CDart*>::iterator itcell;
2503  std::set<CDart*> cellafter;
2504  bool disconnection = false;
2505  for (itcell=vertex.begin(); itcell!=vertex.end(); ++itcell)
2506  {
2507  if ( !isMarked(*itcell, toDelete) )
2508  {
2509  if ( cellafter.empty() )
2510  for (CDynamicCoverageVertex itcell2(this, *itcell);
2511  itcell2.cont(); ++itcell2)
2512  {
2513  cellafter.insert(*itcell2);
2514  }
2515  else
2516  {
2517  if ( cellafter.find(*itcell)==cellafter.end() )
2518  {
2519  disconnection = true;
2520  // std::cout<<"Disconnect vertex\n";
2521  break;
2522  }
2523  }
2524  }
2525  }
2526  vertex.clear();
2527  if ( cellafter.empty() ) disconnection=true;
2528  else cellafter.clear();
2529  if ( !disconnection )
2530  {
2531  for (itcell=face.begin(); itcell!=face.end(); ++itcell)
2532  {
2533  if ( !isMarked(*itcell, toDelete) )
2534  {
2535  if ( cellafter.empty() )
2536  for (CDynamicCoverageFace itcell2(this, *itcell);
2537  itcell2.cont(); ++itcell2)
2538  {
2539  cellafter.insert(*itcell2);
2540  }
2541  else
2542  {
2543  if ( cellafter.find(*itcell)==cellafter.end() )
2544  {
2545  disconnection = true;
2546  //std::cout<<"Disconnect face\n";
2547  break;
2548  }
2549  }
2550  }
2551  }
2552  }
2553  face.clear();
2554  if ( cellafter.empty() ) disconnection=true;
2555  else cellafter.clear();
2556 
2557  if ( !disconnection )
2558  {
2559  assert( findUnionFindTrees(current, indexVertex)!=
2560  findUnionFindTrees(alpha0(current),indexVertex) );
2561 
2562  // We remove darts from the list of darts.
2563  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
2564  {
2565  removeDartInList( *itEdge );
2566  removeDartInList( alpha0(*itEdge) );
2567  (*itEdge)->setNext(alpha0(*itEdge));
2568  alpha0(*itEdge)->setNext(firstDeleteDart);
2569  firstDeleteDart=*itEdge;
2570 
2571  //assert( getVertex(*itEdge)==NULL );
2572  //assert( getVertex(alpha0(*itEdge))==NULL );
2573  }
2574 
2575  if ( !dangling )
2576  mergeUnionFindTrees(current, alpha0(current), indexVertex);
2577  }
2578  else
2579  {
2580  //std::cout<<"Disconnection: we reput the alpha1.\n";
2581  for ( itEdge.reinit(); itEdge.cont(); ++itEdge )
2582  {
2583  unsetMark( *itEdge, toDelete );
2584  unsetMark( alpha0(*itEdge), toDelete );
2585  }
2586  /* Normalement pas la peine!! std::vector<CDart*>::iterator unsewsit;
2587  for ( unsewsit=unsews.begin(); unsewsit!=unsews.end();
2588  ++unsewsit )
2589  unlinkAlpha1(*unsewsit);*/
2590 
2591  std::vector<std::pair<CDart*,CDart*> >::iterator sewsit;
2592  for ( sewsit=sews.begin(); sewsit!=sews.end(); ++sewsit )
2593  {
2594  //std::cout<<(*sewsit).first<<"--"<<(*sewsit).second<<" ";
2595  if ( alpha1((*sewsit).first)!=((*sewsit).second) )
2596  {
2597  if ( !isFree1((*sewsit).first) )
2598  unlinkAlpha1((*sewsit).first);
2599  //unsew1((*sewsit).first);
2600  if ( !isFree1((*sewsit).second) )
2601  //unsew1((*sewsit).second);
2602  unlinkAlpha1((*sewsit).second);
2603  linkAlpha1/*sew1*/((*sewsit).first, (*sewsit).second);
2604  }
2605  }
2606  //std::cout<<std::endl;
2607 
2608  // And we reput the vertex attribute
2609  setVertex(alpha0(current), secondvertex);
2610  //updateVertex(alpha0(current), secondvertex);
2611  }
2612 
2613  sews.clear();
2614  /* assert(checkTopology());
2615  assert(checkEmbeddings(ORBIT_VERTEX, ATTRIBUTE_VERTEX, true));
2616  for( CDynamicCoverageAll cov2(this); cov2.cont(); ++cov2 )
2617  {
2618  assert( !isMarked(*cov2, toDelete) );
2619  assert( !isMarked(alpha0(*cov2), toDelete) );
2620  assert( !isMarked(alpha1(*cov2), toDelete) );
2621  assert( !isMarked(alpha2(*cov2), toDelete) );
2622  assert( !isMarked(alpha3(*cov2), toDelete) );
2623  }*/
2624  //save("in-contract-edges.moka");
2625  }
2626  else
2627  {
2628  for ( CDynamicCoverage23 itEdge(this, current);
2629  itEdge.cont(); ++itEdge )
2630  {
2631  setMark( *itEdge, treated );
2632  setMark( alpha0(*itEdge), treated );
2633  }
2634  }
2635  }
2636  else
2637  {
2638  for ( CDynamicCoverage23 itEdge(this, current);
2639  itEdge.cont(); ++itEdge )
2640  {
2641  setMark( *itEdge, treated );
2642  setMark( alpha0(*itEdge), treated );
2643  }
2644  }
2645  }
2646  negateMaskMark(treated);
2647  assert( isWholeMapUnmarked(treated) );
2648 
2649  // save("after-contract-edges.moka");
2650 
2651  assert(checkTopology());
2652  assert(checkEmbeddings(ORBIT_VERTEX, ATTRIBUTE_VERTEX, true));
2653  }
2654 
2655  // 2) We contract faces.
2656  if ( false ) //optosimplify & FACE_CONTRACTION )
2657  {
2658  cov.reinit();
2659  while ( cov.cont() )
2660  {
2661  current = cov++;
2662 
2663  if ( !isMarked(current, toDelete) &&
2664  !isMarked(current, treated) )
2665  {
2666  /* std::cout<<"face:";
2667  for (CDynamicCoverage01 ittmp(this,current);ittmp.cont();++ittmp)
2668  std::cout<<*ittmp<<", ";
2669  std::cout<<std::endl; */
2670 
2671  // We contract co-degree two faces.
2672  if ( (alpha2(current) !=alpha1(current) ||
2673  alpha32(current)!=alpha31(current)) &&
2674  alpha10(current)==alpha01(current) &&
2675  findUnionFindTrees(current, indexEdge)!=
2676  findUnionFindTrees(alpha0(current),indexEdge) )
2677  {
2678  // First we mark the current face.
2679  CDynamicCoverage13 itFace(this, current);
2680  for ( ; itFace.cont(); ++itFace)
2681  {
2682  assert ( !isFree0(*itFace) );
2683  assert ( !isMarked(*itFace, treated) );
2684  assert ( !isMarked(alpha0(*itFace), treated) );
2685  setMark( *itFace, treated );
2686  setMark( alpha0(*itFace), treated );
2687  setMark( *itFace, toDelete );
2688  setMark( alpha0(*itFace), toDelete );
2689  }
2690 
2691  while ( cov.cont() && isMarked(*cov, treated) )
2692  ++cov;
2693 
2694  std::vector<CDart*> vertex;
2695  for (CDynamicCoverageVertex itvertex(this, current);
2696  itvertex.cont(); ++itvertex)
2697  {
2698  vertex.push_back(*itvertex);
2699  }
2700  std::vector<CDart*> vertex2;
2701  for (CDynamicCoverageVertex itvertex(this, alpha0(current));
2702  itvertex.cont(); ++itvertex)
2703  {
2704  vertex2.push_back(*itvertex);
2705  }
2706  /*std::vector<CDart*> face;
2707  for (CDynamicCoverageFace itface(this, current);
2708  itface.cont(); ++itface)
2709  {
2710  face.push_back(*itface);
2711  }
2712 
2713  std::vector<CDart*> volume;
2714  for (CDynamicCoverageVolume itvol(this, current);
2715  itvol.cont(); ++itvol)
2716  {
2717  volume.push_back(*itvol);
2718  }*/
2719 
2720  // We manage attributes before to modify the map; otherwise
2721  // it is too late.
2722  // Attribute of the second vertex must be removed.
2723  // CAttributeVertex* secondvertex = removeVertex(alpha0(current));
2724  //CVertex secondvertex = *findVertex(alpha0(current));
2725 
2726  // Attributes of the two vertices must be placed on a
2727  // non delete dart
2728  /*for ( itFace.reinit(); itFace.cont(); ++itFace )
2729  {
2730  if ( getVertex(*itFace)!=NULL )
2731  {
2732  CAttributeVertex * v = removeVertex(*itFace);
2733 
2734  if ( !isMarked(alpha1(*itFace), toDelete) )
2735  setVertex(alpha1(*itFace), v);
2736  else if (!isMarked(alpha21(*itFace), toDelete) )
2737  setVertex(alpha21(*itFace), v);
2738  else if (!isMarked(alpha31(*itFace), toDelete) )
2739  setVertex(alpha31(*itFace), v);
2740  else if (!isMarked(alpha321(*itFace), toDelete) )
2741  setVertex(alpha321(*itFace), v);
2742  else if (!isMarked(alpha231(*itFace), toDelete) )
2743  setVertex(alpha231(*itFace), v);
2744  else
2745  {
2746  assert(false);
2747  delete v;
2748  }
2749  }
2750  if ( getVertex(alpha0(*itFace))!=NULL )
2751  {
2752  CAttributeVertex * v = removeVertex(alpha0(*itFace));
2753 
2754  if ( !isMarked(alpha1(alpha0(*itFace)), toDelete) )
2755  setVertex(alpha1(alpha0(*itFace)), v);
2756  else if (!isMarked(alpha21(alpha0(*itFace)), toDelete) )
2757  setVertex(alpha21(alpha0(*itFace)), v);
2758  else if (!isMarked(alpha31(alpha0(*itFace)), toDelete) )
2759  setVertex(alpha31(alpha0(*itFace)), v);
2760  else if (!isMarked(alpha321(alpha0(*itFace)), toDelete) )
2761  setVertex(alpha321(alpha0(*itFace)), v);
2762  else if (!isMarked(alpha231(alpha0(*itFace)), toDelete) )
2763  setVertex(alpha231(alpha0(*itFace)), v);
2764  else
2765  {
2766  assert(false);
2767  delete v;
2768  }
2769  }
2770  }*/
2771 
2772  std::vector<std::pair<CDart*,CDart*> > sews;
2773  // Normalement pas la peine std::vector< CDart* > unsews;
2774 
2775  // We push in the stack all the neighboors of the current
2776  // edge that become co-dangling ??? after the removal.
2777  // Moreover, we make the removal manually instead of calling
2778  // contract(current, 1, false) for optimisation reasons.
2779  for ( itFace.reinit(); itFace.cont(); ++itFace )
2780  //for ( CDynamicCoverageFace itFace(this,current); itFace.cont(); ++itFace )
2781  {
2782  // Now we update alpha2
2783  t1 = alpha(*itFace, 2);
2784  if ( !isMarked(t1, toDelete) )
2785  {
2786  t2 = *itFace;
2787  while ( isMarked(t2, toDelete) )
2788  {
2789  t2 = alpha12(t2);
2790  }
2791 
2792  //std::cout<<t1<<"--"<<alpha1(t1)<<" ";
2793  //std::cout<<t2<<"--"<<alpha1(t2)<<" ";
2794  if ( t2 != alpha(t1, 2) )
2795  {
2796  sews.push_back(std::pair<CDart*,CDart*>(t1,alpha2(t1)));
2797  unsew2(t1); //unlinkAlpha2(t1);
2798  if (!isFree(t2, 2))
2799  {
2800  sews.push_back(std::pair<CDart*,CDart*>(t2,alpha2(t2)));
2801  unsew2(t2); //unlinkAlpha2(t2);
2802  }
2803  if (t1!=t2 && !isMarked(t1, toDelete))
2804  {
2805  // Normalement pas la peine unsews.push_back(t1);
2806  sew2(t1,t2); //linkAlpha2(t1,t2);
2807  // std::cout<<"link1 "<<t1<<"--"<<t2<<" ";
2808  }
2809  }
2810  }
2811  }
2812  //std::cout<<std::endl;
2813 
2814  // We test if there is a disconnexion or disparition
2815  std::vector<CDart*>::iterator itcell;
2816  std::set<CDart*> cellafter;
2817  bool disconnection = false;
2818  for (itcell=vertex.begin(); itcell!=vertex.end(); ++itcell)
2819  {
2820  if ( !isMarked(*itcell, toDelete) )
2821  {
2822  if ( cellafter.empty() )
2823  for (CDynamicCoverageVertex itcell2(this, *itcell);
2824  itcell2.cont(); ++itcell2)
2825  {
2826  cellafter.insert(*itcell2);
2827  }
2828  else
2829  {
2830  if ( cellafter.find(*itcell)==cellafter.end() )
2831  {
2832  disconnection = true;
2833  // std::cout<<"Disconnect vertex\n";
2834  break;
2835  }
2836  }
2837  }
2838  }
2839  vertex.clear();
2840  if ( cellafter.empty() ) disconnection=true;
2841  else cellafter.clear();
2842  for (itcell=vertex2.begin(); itcell!=vertex2.end(); ++itcell)
2843  {
2844  if ( !isMarked(*itcell, toDelete) )
2845  {
2846  if ( cellafter.empty() )
2847  for (CDynamicCoverageVertex itcell2(this, *itcell);
2848  itcell2.cont(); ++itcell2)
2849  {
2850  cellafter.insert(*itcell2);
2851  }
2852  else
2853  {
2854  if ( cellafter.find(*itcell)==cellafter.end() )
2855  {
2856  disconnection = true;
2857  // std::cout<<"Disconnect vertex\n";
2858  break;
2859  }
2860  }
2861  }
2862  }
2863  vertex2.clear();
2864  if ( cellafter.empty() ) disconnection=true;
2865  else cellafter.clear();
2866  /* if ( !disconnection )
2867  {
2868  for (itcell=face.begin(); itcell!=face.end(); ++itcell)
2869  {
2870  if ( !isMarked(*itcell, toDelete) )
2871  {
2872  if ( cellafter.empty() )
2873  for (CDynamicCoverageFace itcell2(this, *itcell);
2874  itcell2.cont(); ++itcell2)
2875  {
2876  cellafter.insert(*itcell2);
2877  }
2878  else
2879  {
2880  if ( cellafter.find(*itcell)==cellafter.end() )
2881  {
2882  disconnection = true;
2883  //std::cout<<"Disconnect face\n";
2884  break;
2885  }
2886  }
2887  }
2888  }
2889  }
2890  face.clear();
2891  if ( cellafter.empty() ) disconnection=true;
2892  else cellafter.clear();
2893  if ( !disconnection )
2894  {
2895  for (itcell=volume.begin(); itcell!=volume.end(); ++itcell)
2896  {
2897  if ( !isMarked(*itcell, toDelete) )
2898  {
2899  if ( cellafter.empty() )
2900  for (CDynamicCoverageVolume itcell2(this, *itcell);
2901  itcell2.cont(); ++itcell2)
2902  {
2903  cellafter.insert(*itcell2);
2904  }
2905  else
2906  {
2907  if ( cellafter.find(*itcell)==cellafter.end() )
2908  {
2909  disconnection = true;
2910  // std::cout<<"Disconnect volume\n";
2911  break;
2912  }
2913  }
2914  }
2915  }
2916  }
2917  volume.clear();
2918  if ( cellafter.empty() ) disconnection=true;
2919  else cellafter.clear(); */
2920 
2921  if ( !disconnection )
2922  {
2923  assert( findUnionFindTrees(current, indexEdge)!=
2924  findUnionFindTrees(alpha1(current),indexEdge) );
2925 
2926  // We remove darts from the list of darts.
2927  for ( itFace.reinit(); itFace.cont(); ++itFace )
2928  {
2929  removeDartInList( *itFace );
2930  removeDartInList( alpha0(*itFace) );
2931  (*itFace)->setNext(alpha0(*itFace));
2932  alpha0(*itFace)->setNext(firstDeleteDart);
2933  firstDeleteDart=*itFace;
2934 
2935  //assert( getVertex(*itFace)==NULL );
2936  //assert( getVertex(alpha0(*itFace))==NULL );
2937  }
2938 
2939  if ( !dangling )
2940  mergeUnionFindTrees(current, alpha1(current), indexEdge);
2941  }
2942  else
2943  {
2944  //std::cout<<"Disconnection: we reput the alpha1.\n";
2945  for ( itFace.reinit(); itFace.cont(); ++itFace )
2946  {
2947  unsetMark( *itFace, toDelete );
2948  unsetMark( alpha0(*itFace), toDelete );
2949  }
2950  /* Normalement pas la peine!! std::vector<CDart*>::iterator unsewsit;
2951  for ( unsewsit=unsews.begin(); unsewsit!=unsews.end();
2952  ++unsewsit )
2953  unlinkAlpha1(*unsewsit);*/
2954 
2955  std::vector<std::pair<CDart*,CDart*> >::iterator sewsit;
2956  for ( sewsit=sews.begin(); sewsit!=sews.end(); ++sewsit )
2957  {
2958  //std::cout<<(*sewsit).first<<"--"<<(*sewsit).second<<" ";
2959  if ( alpha2((*sewsit).first)!=((*sewsit).second) )
2960  {
2961  if ( !isFree2((*sewsit).first) )
2962  unsew2/*unlinkAlpha2*/((*sewsit).first);
2963  if ( !isFree2((*sewsit).second) )
2964  unsew2/*unlinkAlpha2*/((*sewsit).second);
2965  sew2/*linkAlpha2*/((*sewsit).first, (*sewsit).second);
2966  }
2967  }
2968  //std::cout<<std::endl;
2969 
2970  // And we reput the vertex attribute
2971  // setVertex(alpha0(current), secondvertex);
2972  //updateVertex(alpha(current), secondvertex);
2973  }
2974 
2975  sews.clear();
2976  /* assert(checkTopology());
2977  assert(checkEmbeddings(ORBIT_VERTEX, ATTRIBUTE_VERTEX, true));
2978  for( CDynamicCoverageAll cov2(this); cov2.cont(); ++cov2 )
2979  {
2980  assert( !isMarked(*cov2, toDelete) );
2981  assert( !isMarked(alpha0(*cov2), toDelete) );
2982  assert( !isMarked(alpha1(*cov2), toDelete) );
2983  assert( !isMarked(alpha2(*cov2), toDelete) );
2984  assert( !isMarked(alpha3(*cov2), toDelete) );
2985  }
2986  save("in-contract-faces.moka");*/
2987  }
2988  else
2989  {
2990  for ( CDynamicCoverageFace itFace(this, current);
2991  itFace.cont(); ++itFace )
2992  {
2993  setMark( *itFace, treated );
2994  }
2995  }
2996  }
2997  }
2998  negateMaskMark(treated);
2999  assert( isWholeMapUnmarked(treated) );
3000 
3001  // save("after-contract-faces.moka");
3002 
3003  assert(checkTopology());
3004  assert(checkEmbeddings(ORBIT_VERTEX, ATTRIBUTE_VERTEX, true));
3005  }
3006 
3007  // 4) We remove all the darts marked toDelete
3008  while ( firstDeleteDart!=NULL )
3009  {
3010  t1 = firstDeleteDart->getNext();
3011  delDart(firstDeleteDart);
3012  firstDeleteDart = t1;
3013  ++nbRemove;
3014  }
3015 
3016  assert( isWholeMapUnmarked(toDelete) );
3017  assert( isWholeMapUnmarked(treated) );
3018 
3019  freeMark(toDelete);
3020  freeMark(treated);
3021 
3022  freeDirectInfo(indexVertex);
3023  freeDirectInfo(indexEdge);
3024 
3025  // save("after-simplification-3D-contraction.moka");
3026  assert(checkTopology());
3027  assert(checkEmbeddings(ORBIT_VERTEX, ATTRIBUTE_VERTEX, true));
3028 
3029  return nbRemove;
3030 }
3031 //******************************************************************************
3032 unsigned int CGMapVertex::simplify2DObject(unsigned int optosimplify)
3033 {
3034  return simplify2DObjectRemoval(optosimplify) +
3035  simplify2DObjectContraction(optosimplify);
3036 }
3037 //******************************************************************************