PolyhedralAlgorithms_Rn.h

Go to the documentation of this file.

// politopix allows to make computations on polytopes such as finding vertices, intersecting, Minkowski sums, ...
//     Copyright (C) 2015-2016 : Delos Vincent
//
//     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/>.
//
// I2M (UMR CNRS 5295 / University of Bordeaux)

#ifndef INC_POLY_ALGO
#define INC_POLY_ALGO

#include <boost/numeric/ublas/vector.hpp>
#include "polito_Export.h"
#include "Rn.h"
#include "Polytope_Rn.h"
#include "IO_Polytope.h"
#include "Generator_Rn.h"
#include "NormalFan_Rn.h"
#include "HalfSpace_Rn.h"
#include "PolyhedralCone_Rn.h"
#include "VolumeOfPolytopes_Rn.h"
#include "DoubleDescription_Rn.h"
#include "PolyhedralAlgorithms_Rn.h"
#include "GeometricObjectIterator_Rn.h"

using namespace std;

typedef std::vector< unsigned int > ListOfFaces;

class polito_EXPORT FaceEnumeration {

 public:

  FaceEnumeration(const boost::shared_ptr<Polytope_Rn>& A):_polytope(A) {}

  static void Compute(const boost::shared_ptr<Polytope_Rn>& A);

  static void Compute(const boost::shared_ptr<Polytope_Rn>& A, FaceEnumeration& FE);

  const std::vector< std::vector< ListOfFaces > >& getFacesWithVertices() throw (std::domain_error) {
    if (_allFacesWithVertices.empty() == false)
      return _allFacesWithVertices;
    throw std::domain_error("FaceEnumeration::getFacesWithVertices() empty DS allFacesWithVertices.");
  }

  const std::vector< std::vector< ListOfFaces > >& getFacesWithFacets() throw (std::domain_error) {
    if (_allFacesWithFacets.empty() == false)
      return _allFacesWithFacets;
    throw std::domain_error("FaceEnumeration::getFacesWithFacets() empty DS allFacesWithFacets.");
  }

  void clear() {_allFacesWithFacets.clear(); _allFacesWithVertices.clear();}

  void printFacesWithVerticesToSage(std::ostream &this_ostream) const;

  void printFacesWithVertices(std::ostream &this_ostream) const;

  void printFacesWithFacets(std::ostream &this_ostream) const;

  static void save(const std::string& filename, const std::vector< std::vector< ListOfFaces > >& latt);

  static void load(const std::string& filename, std::vector< std::vector< ListOfFaces > >& latt)
    throw (std::ios_base::failure);

  static void load(std::istream& this_stream, std::vector< std::vector< ListOfFaces > >& latt)
    throw (std::out_of_range);

  static void save(std::ostream& this_stream, const std::vector< std::vector< ListOfFaces > >& latt);

  void save(std::ostream& this_stream) const { save(this_stream, _allFacesWithVertices); }


 protected:
  static void ComputeWithFacets(const boost::shared_ptr<Polytope_Rn>& A, FaceEnumeration& FaceEnum);

  static void ComputeWithVertices(const boost::shared_ptr<Polytope_Rn>& A, FaceEnumeration& FaceEnum);

  std::vector< std::vector< ListOfFaces > > _allFacesWithFacets;

  std::vector< std::vector< ListOfFaces > > _allFacesWithVertices;

  const boost::shared_ptr<Polytope_Rn>& _polytope;

};


class polito_EXPORT MinkowskiSum {

 public:

  MinkowskiSum()
  {}

  MinkowskiSum(
      const boost::shared_ptr<Polytope_Rn>& A,
      const boost::shared_ptr<Polytope_Rn>& B):_firstOperand(A),_secondOperand(B)
  {}

  MinkowskiSum(
      const boost::shared_ptr<Polytope_Rn>& A,
      const boost::shared_ptr<Polytope_Rn>& B,
      boost::shared_ptr<Polytope_Rn>& C):_firstOperand(A),_secondOperand(B),_sum(C)
  { C = compute(); }

  MinkowskiSum(
      const std::vector< boost::shared_ptr<Polytope_Rn> >& arrayOfPolytopes,
      boost::shared_ptr<Polytope_Rn>& C);

  MinkowskiSum(
      const boost::shared_ptr<Polytope_Rn>& A,
      const boost::shared_ptr<Polytope_Rn>& B,
      boost::shared_ptr<Polytope_Rn>& C,
      const std::vector< std::vector<int> >& genitorsOfGeneratorsA,
      const std::vector< std::vector<int> >& genitorsOfGeneratorsB,
      std::vector< std::vector<int> >& traceGenerators):_firstOperand(A),_secondOperand(B),_sum(C)
  {
    C = compute();
    traceGenerators.clear();
    //traceGenerators.resize(C->numberOfGenerators());
    unsigned int countOK=0;
    {for (unsigned int i=0; i<_MinkowskiDecomposition.size(); ++i) {
      if (_MinkowskiDecompositionOK[i] == true) {
        // vertex_i = vertex_a + vertex_b
        unsigned int a = _MinkowskiDecomposition[i].first;
        unsigned int b = _MinkowskiDecomposition[i].second;
        std::vector<int> genitorsAB;
        genitorsAB.insert(genitorsAB.end(), genitorsOfGeneratorsA[a].begin(), genitorsOfGeneratorsA[a].end());
        genitorsAB.insert(genitorsAB.end(), genitorsOfGeneratorsB[b].begin(), genitorsOfGeneratorsB[b].end());
        traceGenerators.push_back(genitorsAB);
        ++countOK;
      }
    }}
  }

  boost::shared_ptr<Polytope_Rn> rebuildSum(
      const std::set< unsigned int >& firstOperandCaps,
      const std::set< unsigned int >& secondOperandCaps,
      std::set< unsigned int >& newCaps,
      double bb_size=1000.);

 protected:
  boost::shared_ptr<Polytope_Rn> compute() throw (std::domain_error);

  void computeCommonRefinement(
      const std::vector< boost::shared_ptr<Generator_Rn> >& listOfGenerators_A,
      const std::vector< boost::shared_ptr<Generator_Rn> >& listOfGenerators_B,
      std::vector< boost::shared_ptr<Generator_Rn> >& listOfGenerators_C,
      const std::vector< boost::shared_ptr<PolyhedralCone_Rn> >& listOfDualCones_A,
      const std::vector< boost::shared_ptr<PolyhedralCone_Rn> >& listOfDualCones_B,
      std::vector< boost::shared_ptr<PolyhedralCone_Rn> >& listOfDualCones_C) throw (std::domain_error);

  void processNormalFan0();

  void processNormalFan1();

  void processNormalFan2();

  void computeCapHalfSpaces(
      const std::set< unsigned int >& firstOperandCaps,
      const std::set< unsigned int >& secondOperandCaps,
      std::set< unsigned int >& sumCaps) const throw (std::domain_error);

 protected:
  const boost::shared_ptr<Polytope_Rn> _firstOperand;
  const boost::shared_ptr<Polytope_Rn> _secondOperand;
  boost::shared_ptr<Polytope_Rn> _sum;

  // Give the relation between a vertex of A and all of its associated Minkowski vertices i.e. its polyhedrical cap
  // A2C[i] = [ c_u, c_v, ... ]  }
  //                             } => c_u = a_i + b_j
  // B2C[j] = [ c_u, c_w, ... ]  }
  std::vector< std::vector<unsigned int> > _A2C;
  std::vector< std::vector<unsigned int> > _B2C;

  std::vector< std::vector<unsigned int> > _neighboursA;
  std::vector< std::vector<unsigned int> > _neighboursB;

  // minkowskiVertices(i,j)==1 <=> a_i + b_j is a Minkowski vertex.

  //  MinkowskiDecomposition[k] = (a_i, b_j) <=> c_k = a_i + b_j is a Minkowski vertex.
  // To store each Minkowski vertex decomposition
  std::vector< std::pair< unsigned int, unsigned int > > _MinkowskiDecomposition;
  std::vector< bool > _MinkowskiDecompositionOK;

  std::vector< boost::shared_ptr<PolyhedralCone_Rn> > _NF_Cones;
  std::vector< boost::shared_ptr<Generator_Rn> >      _NF_Vertices;

};


class polito_EXPORT PseudoSumWithoutCaps : public MinkowskiSum {

public:

  PseudoSumWithoutCaps(
     const boost::shared_ptr<Polytope_Rn>& A,
     const boost::shared_ptr<Polytope_Rn>& B,
     boost::shared_ptr<Polytope_Rn>& C,
     const std::set< unsigned int >& firstOperandCaps,
     const std::set< unsigned int >& secondOperandCaps,
     std::set< unsigned int >& newCaps,
     double bb_size=1000.):MinkowskiSum(A,B,C)
   { C = rebuildSum(firstOperandCaps, secondOperandCaps, newCaps, bb_size); }


protected:

  boost::shared_ptr<Polytope_Rn> rebuildSum(
      const std::set< unsigned int >& firstOperandCaps,
      const std::set< unsigned int >& secondOperandCaps,
      std::set< unsigned int >& newCaps,
      double bb_size=1000.);

  void computeCapHalfSpaces(
      const std::set< unsigned int >& firstOperandCaps,
      const std::set< unsigned int >& secondOperandCaps,
      std::set< unsigned int >& sumCaps) throw (std::domain_error);

};


class polito_EXPORT PseudoIntersectionWithoutCaps {

public:

  PseudoIntersectionWithoutCaps(
     const boost::shared_ptr<Polytope_Rn>& A,
     const boost::shared_ptr<Polytope_Rn>& B,
     boost::shared_ptr<Polytope_Rn>& C,
     const std::set< unsigned int >& firstOperandCaps,
     const std::set< unsigned int >& secondOperandCaps,
     std::set< unsigned int >& newCaps,
     double bb_size=1000.);

};


class polito_EXPORT TopGeomTools {

public:

  static int Translate(boost::shared_ptr<Polytope_Rn>& pol, const boost::numeric::ublas::vector<double>& v2t);

  static int GravityCenter(boost::shared_ptr<Polytope_Rn>& pol, boost::numeric::ublas::vector<double>& gravity_center);

  static int scalingFactor(boost::shared_ptr<Polytope_Rn>& pol, double factor);

  static int PolarPolytope(
      const boost::shared_ptr<Polytope_Rn>& original_pol,
      boost::shared_ptr<Polytope_Rn>& polar_pol,
      bool forceComputation = true, double bb_size=1000.) throw (invalid_argument);

  static int projectPolytopeOnCanonicalHyperplanes(
      const std::set< unsigned int >& listOfHyperplanes,
      const boost::shared_ptr<Polytope_Rn>& original_pol,
      boost::shared_ptr<Polytope_Rn>& proj_pol) throw (invalid_argument);

  static int extrudeInCanonicalDirections(
      const std::set< unsigned int >& originalSpaceDirections,
      unsigned int dimensionOfTotalSpace,
      const boost::shared_ptr<Polytope_Rn>& original_polytope,
      boost::shared_ptr<PolyhedralCone_Rn>& extruded_polyhedron) throw (invalid_argument);

};


class polito_EXPORT DoubleDescriptionFromGenerators {

public:

  static int Compute(boost::shared_ptr<Polytope_Rn>& pol, double bb_size=1000.)
    throw (invalid_argument, out_of_range, ios_base::failure, logic_error);

};


class polito_EXPORT Visualization {

public:

  static void gnuplot2D(const boost::shared_ptr<Polytope_Rn>& polygon, const std::string& name, double col, std::ostream& out) throw (std::domain_error);

};

#endif // INC_POLY_ALGO