src/lib-gmapkernel/g-map-generic/gmg-contract-and-remove.cc

Go to the documentation of this file.

/*
 * lib-gmapkernel : Un noyau de 3-G-cartes et des opérations.
 * Copyright (C) 2004, Moka Team, Université de Poitiers, Laboratoire SIC
 *               http://www.sic.sp2mi.univ-poitiers.fr/
 * Copyright (C) 2009, Guillaume Damiand, CNRS, LIRIS,
 *               guillaume.damiand@liris.cnrs.fr, http://liris.cnrs.fr/
 *
 * This file is part of lib-gmapkernel
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

//******************************************************************************
#include "g-map-generic.hh"
#include <deque>
using namespace std;
using namespace GMap3d;
//******************************************************************************
// Contractions et suppressions simultanées de cellules de dimension quelconque.
// Pour chaque cellule concernée, un marquage sur un brin incident à celle-ci
// indique l'opération à affectuer.
//
// dim == 3: contraction de volume
//           (précondition : volume de degré inférieur local égal à 2)
// dim == 2: contraction ou suppression de face
//           (pas de précondition pour la suppression)
//           (précondition contraction : face de degré inférieur local égal à 2)
// dim == 1: contraction ou suppression d'arête
//           (pas de précondition pour la contraction)
//           (précondition suppression: arête de degré inférieur local égal à 2)
// dim == 0: suppression de sommet
//           (précondition : sommet de degré inférieur local égal à 2)
//******************************************************************************
int CGMapGeneric::contractAndRemoveMarkedCells( int AMarkNumberC1,
                                                int AMarkNumberC2, 
                                                int AMarkNumberC3,
                                                int AMarkNumberS0,
                                                int AMarkNumberS1, 
                                                int AMarkNumberS2,
                                                bool ADeleteDarts )
{

  int marks[6]; // contiendra les 6 marques passées en paramètre
  //   - La dimension de la cellule concernée par l'opération
  //      de marque rangée dans la case i du tableau est (i+1)%4.

  int nbCellMarked = 0; // Indique le nombre cellules supprimées et contractées

  marks[0] = AMarkNumberC1;
  marks[1] = AMarkNumberC2;
  marks[2] = AMarkNumberC3;
  marks[3] = AMarkNumberS0;
  marks[4] = AMarkNumberS1;
  marks[5] = AMarkNumberS2;

  // On marque les brins de chaque cellule concernée par l'une des opérations
  for(int i=0 ; i<=5; i++)
    {
      if (marks[i]!=-1)
        {
          nbCellMarked += markIncidentCells(ORBIT_CELL[(i+1)%4], marks[i]);
        }
    }

  // On démarque les cellules qui ne respectent pas les préconditions de la suppression
  // ou de la contraction
  CDynamicCoverageAll cov(this);
  for ( ; cov.cont(); ++cov )
    {
      for(int i=0; i<=2; i++)
        {
          if (marks[i]!=-1)
            {
              if ( isMarked(*cov, marks[i]) )
                {
                  int cell = i+1;
                  if ( !canContract(*cov, cell) )
                    {
                      unmarkOrbit( *cov, ORBIT_CELL[cell], marks[i]);
                      nbCellMarked--;
                    }
                }
            }
        }
      for(int i=3; i<=5; i++)
        {
          if (marks[i]!= -1)
            {
              if ( isMarked(*cov, marks[i]) )
                {
                  int cell = (i+1)%4;
                  if ( !canRemove(*cov, cell) )
                    {
                      unmarkOrbit( *cov, ORBIT_CELL[cell], marks[i]);
                      nbCellMarked--;
                    }
                }
            }
        }
    }

  int firstMark; // La première marque rencontrée.
  int nbMark;
  int cell;
  
  // On démarque les cellules non disjointes
  for ( cov.reinit(); cov.cont(); ++cov )
    {
      firstMark = -1;
      nbMark = 0;
      
      for(int i=0; i<=5; i++)
        {
          if( marks[i] != -1 )
            if ( isMarked(*cov, marks[i]) )
              {
                ++nbMark;
                
                if ( firstMark==-1 ) firstMark = i;
                else
                  {
                    cell = (i+1)%4;
                    unmarkOrbit( *cov, ORBIT_CELL[cell], marks[i]);
                    nbCellMarked--;
                  }
              }
        }
      
      if ( nbMark>1 )
        {
          cell = (firstMark+1)%4;
          unmarkOrbit( *cov, ORBIT_CELL[cell], marks[firstMark]);
        }
    }

  // et on contracte ou supprime ce qui reste marqué
  CDart* current = NULL;
  CDart* t2 = NULL;

  for ( cov.reinit(); cov.cont(); ++cov )
    {
      for(int i=0; i<=1; i++)
        {
          int cell = (i+1)%4;
          if (marks[i] != -1)
            {
              if (  !(isMarked( *cov, marks[i]) || 
                      isMarked( *cov, marks[i+4]) )  &&
                    (isMarked( alpha(*cov, cell), marks[i]) || 
                     isMarked( alpha(*cov, cell), marks[i+4]))  )
                {
                  current = *cov;
                  t2 = alpha(current, cell);
                  
                  while (isMarked(t2, marks[i]) || isMarked(t2, marks[i+4]) )
                    {
                      if (isMarked(t2, marks[i]))
                          t2 = alpha(alpha(t2, cell-1), cell);
                      else 
                          t2 = alpha(alpha(t2, cell+1), cell);
                    }
                  
                  if ( t2 != alpha(current, cell) )
                    {
                      unsew(current, cell);
                      if ( !isFree(t2, cell) ) unsew(t2, cell);
                      if ( t2!=current ) sew(current, t2, cell);
                    }
                }
            }
        }
      if (AMarkNumberC3 != -1)
        {
          if (  !isMarked( *cov, AMarkNumberC3) &&
                isMarked( alpha(*cov, 3), AMarkNumberC3) )
            {
              current = *cov;
              t2 = alpha(current, 3);
              
              while (isMarked(t2, AMarkNumberC3))
                {
                  t2 = alpha(alpha(t2, 2), 3);
                }
              
              if ( t2 != alpha(current, 3) )
                {
                  unsew(current, 3);
                  if ( !isFree(t2, 3) ) unsew(t2, 3);
                  if ( t2!=current ) sew(current, t2, 3);
                }
            }
        }
      if (AMarkNumberS0 != -1)
        {
          if (  !isMarked( *cov, AMarkNumberS0) &&
                isMarked( alpha(*cov, 0), AMarkNumberS0) )
            {
              current = *cov;
              t2 = alpha(current, 0);
              
              while (isMarked(t2, AMarkNumberS0))
                {
                  t2 = alpha(alpha(t2, 1), 0);
                }
              
              if ( t2 != alpha(current, 0) )
                {
                  unsew(current, 0);
                  if ( !isFree(t2, 0) ) unsew(t2, 0);
                  if ( t2!=current ) sew(current, t2, 0);
                }
            }
        }
    }
  
  // on netoie si demandé
  if (ADeleteDarts)
    {
      for (cov.reinit(); cov.cont(); )
        {   
          for (int i=0; i<=5; i++)
            {
              if(marks[i] != -1)
                {
                  if ( isMarked(*cov, marks[i]) )
                    {           
                      delMapDart(*cov);
                      i=5;
                    }
                }
              if (i==5) ++cov;
            }
        }
    }
  return nbCellMarked;
}

---