Generator_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) 2011-2021 : 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 GENERATOR_Rn
#define GENERATOR_Rn
 
#include <stdexcept>
#include <exception>
#include <vector>
#include <cmath>
#include <set>
#include <unordered_set>
#include "polito_Export.h"
#include "Rn.h"
#include "Tracking.h"
#include "Point_Rn.h"
#include "HalfSpace_Rn.h"
 
 
class polito_EXPORT Generator_Rn {
  friend class Generator_Rn_SD;
 
 public:
  Generator_Rn() {}
 
  Generator_Rn(unsigned int n);
 
  Generator_Rn(const Generator_Rn& gn) {
    _coordinates = gn._coordinates;
    _supportFacets = gn._supportFacets;
  }
 
  ~Generator_Rn();
 
  int dimension() const {return _coordinates.size();}
 
  void setCoordinate(unsigned int i, double val) {_coordinates[i] = val;}
 
  double getCoordinate(unsigned int i) const {return _coordinates[i];}
 
  vector<double>::const_iterator begin() const {return _coordinates.begin();}
 
  vector<double>::const_iterator  end()  const {return _coordinates.end();}
 
  const vector<double>& vect() const {return _coordinates;}
 
  void setCoordinates(const vector<double>& vec) {_coordinates = vec;}
 
  void scalingFactor(double factor) {_coordinates *= factor;}
 
  void negate() { _coordinates = -1.*_coordinates; }
 
  bool isEqual1(const boost::shared_ptr<Generator_Rn>& gn, unsigned int RnDIM, double TOL2) {
    unsigned int i=0;
    double sum=0.;
    while (i < RnDIM) {
      sum = sum + fabs(getCoordinate(i) - gn->getCoordinate(i));
      if (sum > TOL2)
        return false;
      i++;
    }
    return true;
  }
 
  bool isEqual2(const boost::shared_ptr<Generator_Rn>& gn, unsigned int RnDIM, double TOL2) {
    unsigned int i=0;
    double sum=0.;
    while (i < RnDIM) {
      sum = sum + fabs(getCoordinate(i) - gn->getCoordinate(i)) * fabs(getCoordinate(i) - gn->getCoordinate(i));
      if (sum > TOL2)
        return false;
      i++;
    }
    return true;
  }
 
  bool isEqual2(const Generator_Rn& gn, unsigned int RnDIM, double TOL2) {
    unsigned int i=0;
    double sum=0.;
    while (i < RnDIM) {
      sum = sum + fabs(getCoordinate(i) - gn.getCoordinate(i)) * fabs(getCoordinate(i) - gn.getCoordinate(i));
      if (sum > TOL2)
        return false;
      i++;
    }
    return true;
  }
 
  // Facets //
  void clearFacets() {_supportFacets.clear();}
 
  void switchFacets(const std::vector< boost::shared_ptr<HalfSpace_Rn> >& tab) {
    _supportFacets.clear();
    _supportFacets = tab;
  }
 
  void setFacet(boost::shared_ptr<HalfSpace_Rn> F) {_supportFacets.push_back(F);}
 
  void importFacets(const std::set< boost::shared_ptr<HalfSpace_Rn> >& setOfFacets) {
    _supportFacets.clear();
    std::set< boost::shared_ptr<HalfSpace_Rn> >::const_iterator it;
    {for (it=setOfFacets.begin(); it!=setOfFacets.end(); ++it) {
      _supportFacets.push_back(*it);
    }}
  }
 
  void exportFacets(std::set< boost::shared_ptr<HalfSpace_Rn> >& setOfFacets) const {
    std::vector< boost::shared_ptr<HalfSpace_Rn> >::const_iterator it;
    {for (it=_supportFacets.begin(); it!=_supportFacets.end(); ++it) {
      setOfFacets.insert(*it);
    }}
  }
 
  void removeFacet(unsigned int i);
 
  boost::shared_ptr<HalfSpace_Rn> getFacet(unsigned int i) const {
    if (i < _supportFacets.size()) {
      return _supportFacets[i];
    }
    else {
      std::string errorMessage = Point_Rn::concatStrings(i, "Generator_Rn::getFacet");
      throw std::out_of_range(errorMessage);
    }
  }
 
  HalfSpace_Rn* getRawFacet(unsigned int i) {return _supportFacets[i].get();}
 
  bool isFacetInside(boost::shared_ptr<HalfSpace_Rn> F) const;
 
  unsigned int numberOfFacets() const {return _supportFacets.size();}
 
  // Computations //
  void makeDiff(const boost::shared_ptr<Generator_Rn>& gn1, const boost::shared_ptr<Generator_Rn>& gn2) {
    _coordinates = gn1->_coordinates - gn2->_coordinates;
  }
 
  void makeSum( const boost::shared_ptr<Generator_Rn>& gn1, const boost::shared_ptr<Generator_Rn>& gn2) {
    _coordinates = gn1->_coordinates + gn2->_coordinates;
  }
 
  void makeCoefSum(
      const boost::shared_ptr<Generator_Rn>& gn1,
      const boost::shared_ptr<Generator_Rn>& gn2,
      double coef1,
      double coef2) {
    _coordinates = coef1*gn1->_coordinates + coef2*gn2->_coordinates;
  }
 
  double getNormalDistance(const boost::shared_ptr<Generator_Rn>& gn1, double coef, unsigned int RnDIM) {
    double sum=0.;
    {for (unsigned int ii=0; ii<RnDIM; ++ii) {
      sum += (gn1->_coordinates[ii] - _coordinates[ii]*coef)*(gn1->_coordinates[ii] - _coordinates[ii]*coef);
    }}
    //std::cout << " (sum=" << sum << ") ";
    return sum;
  }
 
  double normalize() {
    double norm = norm_2(_coordinates);
    _coordinates = _coordinates / norm;
    return norm;
  }
 
  double distanceFrom(const Generator_Rn& P) {
    vector<double> distV = _coordinates;
    distV -= P._coordinates;
    double dist = norm_2(distV);
    return dist;
  }
 
  // Neighbour generators //
  unsigned int numberOfNeighbourGenerators() const { return _neighbourGenerators.size(); }
 
  void clearNeighbourGenerators() {_neighbourGenerators.clear();}
 
  boost::shared_ptr<Generator_Rn> getNeighbourGenerator(unsigned int i) const {
    if (i < _neighbourGenerators.size()) {
      return _neighbourGenerators[i];
    }
    else {
      std::string errorMessage = Point_Rn::concatStrings(i, "Generator_Rn::getNeighbourGenerator");
      throw std::out_of_range(errorMessage);
    }
  }
 
  void setNeighbourGenerator(boost::shared_ptr<Generator_Rn> G) {_neighbourGenerators.push_back(G);}
 
  // Streams //
  void dump(std::ostream &this_ostream) const {
    this_ostream << "[";
    //unsigned int RnDIM=Rn::getDimension();
    {for (unsigned int ii=0; ii<_coordinates.size(); ++ii) {
      this_ostream << getCoordinate(ii);
      if (ii != _coordinates.size()-1)
        this_ostream << ", ";
    }}
    this_ostream << "]";
  }
 
  void print()  const {
    dump(std::cout);
    std::cout << std::endl;
  }
 
 void load(std::istream &this_istream) {
    double val;
    for (unsigned int coord_count=0; coord_count<_coordinates.size(); coord_count++) {
      this_istream >> val;
      setCoordinate(coord_count, val);
    }
  }
 
  void save(std::ostream &this_ostream) const {
    for (unsigned int coord_count=0; coord_count<_coordinates.size(); coord_count++) {
      this_ostream << getCoordinate(coord_count) << " ";
    }
    //this_ostream << std::endl;
  }
 
 
 protected:
  vector<double> _coordinates;
  std::vector< boost::shared_ptr<HalfSpace_Rn> > _supportFacets;
  std::vector< boost::shared_ptr<Generator_Rn> > _neighbourGenerators;
 
};
 
 
 
class Generator_Rn_SD {
  friend class Generator_Rn;
 
 public:
 
  enum Status {
    // When just made as a copy of a Generator_Rn
    UNCHANGED,
    // When some half-spaces have been modified
    MODIFIED,
    // When it was created as the result of an operation
    CREATED,
    // When it was created as the result of an operation and then some half-spaces have been modified
    CREATED_AND_MODIFIED,
    // When it was deleted by an operation
    DELETED,
    UNKNOWN
  };
 
 Generator_Rn_SD(unsigned int n, unsigned int nb, Status st):_generatorNumber(nb),_status(st) {
    _coordinates.resize(n);
    _currentState = HalfSpace_Rn::hs_UNKNOWN;
    _scalarProduct = 0.;
  }
 
 Generator_Rn_SD(const boost::numeric::ublas::vector< double >& coordinates, unsigned int nb):_generatorNumber(nb) {
    _coordinates = coordinates;
    _currentState = HalfSpace_Rn::hs_UNKNOWN;
    _scalarProduct = 0.;
  }
 
  Generator_Rn_SD(const Generator_Rn_SD& gn):_generatorNumber(gn._generatorNumber),_status(gn._status) {
    _coordinates = gn._coordinates;
    _supportIntFacets = gn._supportIntFacets;
    _currentState = gn._currentState;
    _scalarProduct = gn._scalarProduct;
  }
 
  Generator_Rn_SD(const Generator_Rn& gn, unsigned int nb, Status st):_generatorNumber(nb),_status(st) {
    _coordinates = gn._coordinates;
    _currentState = HalfSpace_Rn::hs_UNKNOWN;
  }
 
  Generator_Rn_SD() {
    _currentState = HalfSpace_Rn::hs_UNKNOWN;
  }
 
  ~Generator_Rn_SD() {}
 
  int dimension() const {return _coordinates.size();}
 
  void init(unsigned int nb, Status st) {
    _supportIntFacets.clear();
    _fuzzyFacets.clear();
    _currentState = HalfSpace_Rn::hs_UNKNOWN;
    _generatorNumber = nb;
    _scalarProduct = 0.;
    _status = st;
  }
 
  boost::shared_ptr<Generator_Rn> makeGenerator_Rn() const {
    boost::shared_ptr<Generator_Rn> gn(new Generator_Rn( _coordinates.size() ));
    gn->_coordinates = _coordinates;
    return gn;
  }
 
  void setCoordinate(unsigned int i, double val) {_coordinates[i] = val;}
 
  double getCoordinate(unsigned int i) const {return _coordinates[i];}
 
   void setCoordinates(const vector<double>& vec) {_coordinates = vec;}
 
  void setGeneratorNumber(unsigned int gn) {_generatorNumber = gn;}
 
  unsigned int getGeneratorNumber() const {return _generatorNumber;}
 
  void setStatus(Status stu) {_status = stu;}
 
  Status  getStatus() const {return _status;}
  Status& getStatus()       {return _status;}
 
  void setState(HalfSpace_Rn::State ste) {_currentState = ste;}
  void setState(HalfSpace_Rn::State ste, double scalar_prod) {
    _currentState  = ste;
    _scalarProduct = scalar_prod;
  }
 
  void resetState() {_currentState = HalfSpace_Rn::hs_UNKNOWN;}
 
  HalfSpace_Rn::State getState() const {return _currentState;}
  double getScalarProduct() const {return _scalarProduct;}
  void setScalarProduct(double sp) {_scalarProduct = sp;}
 
  vector<double>::const_iterator begin() const {return _coordinates.begin();}
 
  vector<double>::const_iterator  end()  const {return _coordinates.end();}
 
  const vector<double>& vect() const {return _coordinates;}
 
  void negate() {_coordinates = -1.*_coordinates;}
 
  bool isEqual1(const boost::shared_ptr<Generator_Rn_SD>& gn, unsigned int RnDIM, double TOL2) {
    unsigned int i=0;
    double sum=0.;
    while (i < RnDIM) {
      sum = sum + fabs(getCoordinate(i) - gn->getCoordinate(i));
      if (sum > TOL2)
        return false;
      i++;
    }
    return true;
  }
 
  bool isEqual2(const boost::shared_ptr<Generator_Rn_SD>& gn, unsigned int RnDIM, double TOL2) {
    unsigned int i=0;
    double sum=0.;
    while (i < RnDIM) {
      sum = sum + fabs(getCoordinate(i) - gn->getCoordinate(i)) * fabs(getCoordinate(i) - gn->getCoordinate(i));
      if (sum > TOL2)
        return false;
      i++;
    }
    return true;
  }
 
  bool fuzzyFacets() const {return !_fuzzyFacets.empty();}
  
  unsigned int fuzzyFacetsSize() const {return _fuzzyFacets.size();}
  
  void setFuzzyFacet(unsigned int F) {_fuzzyFacets.push_back(F);}
 
  void setFacet(unsigned int F) {_supportIntFacets.push_back(F);}
 
  void setFacets(const std::vector<unsigned int>& AF) {_supportIntFacets.insert(_supportIntFacets.end(), AF.begin(), AF.end());}
 
  void setAllFacets(const std::vector<unsigned int>& AF) {_supportIntFacets = AF;}
 
  const std::vector<unsigned int>& getAllFacets() {return _supportIntFacets;}
 
  void importFacets(const std::set< unsigned int >& setOfFacets) {
    _supportIntFacets.clear();
    std::set< unsigned int >::const_iterator it;
    {for (it=setOfFacets.begin(); it!=setOfFacets.end(); ++it) {
      _supportIntFacets.push_back(*it);
    }}
  }
 
  void exportFacets(std::set< unsigned int >& setOfFacets) const {
    std::vector< unsigned int >::const_iterator it;
    {for (it=_supportIntFacets.begin(); it!=_supportIntFacets.end(); ++it) {
      setOfFacets.insert(*it);
    }}
  }
 
  void removeFacet(unsigned int i) {
    std::vector< unsigned int >::iterator itRemove = _supportIntFacets.begin() + i;
    // Now, actually remove this element from the array
    _supportIntFacets.erase(itRemove);
  }
 
  unsigned int getFacet(unsigned int i) const {
    if (i < _supportIntFacets.size()) {
      return _supportIntFacets[i];
    }
    else {
      std::string errorMessage = Point_Rn::concatStrings(i, "Generator_Rn::getFacet");
      throw std::out_of_range(errorMessage);
    }
  }
 
  void removeCurrentLinearConstraint(unsigned int LC) {
    if (_supportIntFacets.empty())
      return;
    std::vector< unsigned int >::iterator itRemove = _supportIntFacets.begin();
    while (*itRemove != LC && itRemove != _supportIntFacets.end())
      ++itRemove;
    // Now, actually remove this element from the array if need be.
    if (itRemove != _supportIntFacets.end())
      _supportIntFacets.erase(itRemove);
    else {
      std::string errorMessage = Point_Rn::concatStrings(LC, "Generator_Rn_SD::removeCurrentLinearConstraint");
      throw std::invalid_argument(errorMessage);
    }
  }
 
  unsigned int getRawFacet(unsigned int i) {return _supportIntFacets[i];}
 
  bool isFacetInside(unsigned int F) const {
    std::vector< unsigned int >::const_iterator it = _supportIntFacets.begin();
    {for (; it!=_supportIntFacets.end(); ++it) {
      if (*it == F)
        return true;
    }}
    return false;
  }
 
  unsigned int numberOfFacets() const {return _supportIntFacets.size();}
 
  void orderFacets() { std::sort(_supportIntFacets.begin(), _supportIntFacets.end());}
 
  std::vector<unsigned int>::const_iterator facetsBegin() const {return _supportIntFacets.begin();}
 
  std::vector<unsigned int>::const_iterator facetsEnd()   const {return _supportIntFacets.end();}
 
  std::vector<unsigned int>::const_iterator fuzzyFacetsBegin() const {return _fuzzyFacets.begin();}
 
  std::vector<unsigned int>::const_iterator fuzzyFacetsEnd()   const {return _fuzzyFacets.end();}
 
  void makeDiff(const boost::shared_ptr<Generator_Rn_SD>& gn1, const boost::shared_ptr<Generator_Rn_SD>& gn2) {
    _coordinates = gn1->_coordinates - gn2->_coordinates;
  }
 
  void makeSum( const boost::shared_ptr<Generator_Rn_SD>& gn1, const boost::shared_ptr<Generator_Rn_SD>& gn2) {
    _coordinates = gn1->_coordinates + gn2->_coordinates;
  }
 
  void makeCoefSum(
      const boost::shared_ptr<Generator_Rn_SD>& gn1,
      const boost::shared_ptr<Generator_Rn_SD>& gn2,
      double coef1,
      double coef2) {
    _coordinates = coef1*gn1->_coordinates + coef2*gn2->_coordinates;
  }
 
  double getNormalDistance(const boost::shared_ptr<Generator_Rn_SD>& gn1, double coef, unsigned int RnDIM) {
    double sum=0.;
    {for (unsigned int ii=0; ii<RnDIM; ++ii) {
      sum += (gn1->_coordinates[ii] - _coordinates[ii]*coef)*(gn1->_coordinates[ii] - _coordinates[ii]*coef);
    }}
    //std::cout << " (sum=" << sum << ") ";
    return sum;
  }
 
  double normalize() {
    double norm = norm_2(_coordinates);
    _coordinates = _coordinates / norm;
    return norm;
  }
 
  double distanceFrom(const Generator_Rn_SD& P) {
    vector<double> distV = _coordinates;
    distV -= P._coordinates;
    double dist = norm_2(distV);
    return dist;
  }
 
  void dump(std::ostream &this_ostream) const {
    this_ostream << "(" << _generatorNumber << " [";
    //unsigned int RnDIM=Rn::getDimension();
    {for (unsigned int ii=0; ii<_coordinates.size(); ++ii) {
      this_ostream << getCoordinate(ii);
      if (ii != _coordinates.size()-1)
        this_ostream << " ";
    }}
    this_ostream << "] {";
    std::copy(_supportIntFacets.begin(), _supportIntFacets.end(), std::ostream_iterator<unsigned int>(this_ostream, " ") );
    this_ostream << "} ";
    this_ostream << HalfSpace_Rn::getStateAsText(_currentState) << " // ";
    std::copy(_fuzzyFacets.begin(), _fuzzyFacets.end(), std::ostream_iterator<unsigned int>(this_ostream, " ") );
    this_ostream << "\\\\ )";
  }
 
  void load(std::istream &this_istream) {
    double val;
    for (unsigned int coord_count=0; coord_count<_coordinates.size(); coord_count++) {
      this_istream >> val;
      setCoordinate(coord_count, val);
    }
  }
 
  void save(std::ostream &this_ostream) const {
    for (unsigned int coord_count=0; coord_count<_coordinates.size(); coord_count++) {
      this_ostream << getCoordinate(coord_count) << " ";
    }
    //this_ostream << std::endl;
  }
 
 
 protected:
  boost::numeric::ublas::vector< double > _coordinates;
  std::vector< unsigned int > _supportIntFacets;
  std::vector< unsigned int > _fuzzyFacets;
  // The list of neighbours that share an edge with the current generator when it is a vertex.
  //std::unordered_set< unsigned int > _neighbourGeneratorNumbers;
  unsigned int _generatorNumber;
  Status _status;
  HalfSpace_Rn::State _currentState;
  double _scalarProduct;
 
};
 
 
#endif // GENERATOR_Rn