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-2020 : Delos Vincent
//
//     This program is free software: you can redistribute it and/or modify
//     it under the terms of the GNU 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 General Public License for more details.
//
//     You should have received a copy of the GNU 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() {
    if (_allFacesWithVertices.empty() == false)
      return _allFacesWithVertices;
    throw std::domain_error("FaceEnumeration::getFacesWithVertices() empty DS allFacesWithVertices.");
  }
 
  const std::vector< std::vector< ListOfFaces > >& getFacesWithFacets() {
    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);
 
  static void load(std::istream& this_stream, std::vector< std::vector< ListOfFaces > >& latt);
 
  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();
 
  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);
 
  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;
 
 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);
 
};
 
 
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 computeScalingFactorForInclusion(boost::shared_ptr<Polytope_Rn>& pol1, boost::shared_ptr<Polytope_Rn>& pol2, double& sfactor);
 
  static int scalingFactor(boost::shared_ptr<Polytope_Rn>& pol, double sfactor);
 
  static int scalingFactor(boost::shared_ptr<PolyhedralCone_Rn>& pol, double sfactor);
 
  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.);
 
  static int projectPolytopeOnCanonicalHyperplanes(
      const std::set< unsigned int >& listOfHyperplanes,
      const boost::shared_ptr<Polytope_Rn>& original_pol,
      boost::shared_ptr<Polytope_Rn>& proj_pol);
 
  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);
 
};
 
 
class polito_EXPORT DoubleDescriptionFromGenerators {
 
public:
 
  static int Compute(boost::shared_ptr<Polytope_Rn>& pol, double bb_size=1000.);
 
};
 
 
class NormedHS {
 
 public:
  NormedHS(const boost::numeric::ublas::vector<double>& nv, double cst, unsigned int nb) {
    _currentNormedVector = nv;
    _constant = cst;
    _numberOfNormedHS = nb;
  }
 
  const boost::numeric::ublas::vector<double>& getNormedVector() const {return _currentNormedVector;}
 
  double getConstant() const {return _constant;}
 
  double getNumberOfNormedHS() const {return _numberOfNormedHS;}
 
  void dump(std::ostream &this_ostream) const {
    this_ostream << "{" << _numberOfNormedHS << ": " << _constant << " " << _currentNormedVector << "}" << std::endl;
  }
 
 protected:
  boost::numeric::ublas::vector<double> _currentNormedVector;
  double _constant;
  unsigned int _numberOfNormedHS;
  
};
 
 
class SortHalfSpaces {
 
 public:
  SortHalfSpaces(boost::shared_ptr<Polytope_Rn>& pol);
 
  void dump(std::ostream &this_ostream, const std::vector< std::pair<double, NormedHS > >& listOfNormedVectors) const {
    std::vector< std::pair<double, NormedHS > >::const_iterator iteV = listOfNormedVectors.begin();
    for (; iteV != listOfNormedVectors.end(); ++iteV) {
      this_ostream << iteV->first << " ";
      iteV->second.dump(this_ostream);
    }
  }
  
};
 
 
class polito_EXPORT Visualization {
 
public:
 
  static void gnuplot2D(const boost::shared_ptr<Polytope_Rn>& polygon, const std::string& name, double col, std::ostream& out);
 
};
 
#endif // INC_POLY_ALGO