Voronoi_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-2022 : 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 VORONOI_Rn
#define VORONOI_Rn
 
#include <boost/shared_ptr.hpp>
#include <stdexcept>
#include <exception>
#include <iostream>
#include <utility>
#include <vector>
#include "Rn.h"
#include "Generator_Rn.h"
#include "HalfSpace_Rn.h"
#include "Polytope_Rn.h"
 
 
class Voronoi_Rn {
 
 public:
 
  enum TypeOfAlgorithm {
    Incremental = 0,              
    CellByCell = 1,               
    CellByCellDist = 2,           
    CellByCellDistNgb = 3,        
    CellByCellDistNgb_1pc = 4,    
    CellByCellDistNgb_10pc = 5,   
    CellByCellDistNgb_20pc = 6,   
    CellByCellDistNgb_30pc = 7,   
    CellByCellDistNgb_40pc = 8,   
    WithProperties = 10};         
 
  //Voronoi_Rn() { _inputSpace=0; }
 
  Voronoi_Rn(const boost::shared_ptr<Polytope_Rn>& inputSpace, const std::vector<Point_Rn>& listOfPoints);
 
  virtual ~Voronoi_Rn() {}
 
  virtual bool compute()=0;
 
  //virtual void updateFacetNeighbours(const std::vector< boost::shared_ptr<HalfSpace_Rn> >& allHalfSpaces,
      //boost::shared_ptr<Polytope_Rn> newVoronoiCell, unsigned int counter,
      //unsigned int newTruncationStep)=0;
 
 
  boost::shared_ptr<HalfSpace_Rn> computeMidPlane(std::vector<Point_Rn>::const_iterator seed1, std::vector<Point_Rn>::const_iterator seed2);
 
  const std::vector< boost::shared_ptr<Polytope_Rn> >& getVoronoiCells() const {return _listOfVoronoiCells;}
  std::vector< boost::shared_ptr<Polytope_Rn> > getVoronoiCells() {return _listOfVoronoiCells;}
 
  const std::vector< Point_Rn >& getListOfSeeds() const {return _listOfSeeds;}
 
  // CHECK POLYHEDRON
  bool checkTopologyAndGeometry() const;
 
  void dump(std::ostream& out) const;
 
  void gnuplot(std::ostream& out) const;
 
 protected:
  const boost::shared_ptr<Polytope_Rn>& _inputSpace;
  const std::vector< Point_Rn >& _listOfSeeds;
  std::vector< boost::shared_ptr<Polytope_Rn> > _listOfVoronoiCells;
};
 
class IncrementalVoronoi : public Voronoi_Rn {
 
 public:
  //IncrementalVoronoi() { _inputSpace=0; }
 
  IncrementalVoronoi(const boost::shared_ptr<Polytope_Rn>& is, const std::vector<Point_Rn>& lop):Voronoi_Rn(is,lop) {}
 
  virtual ~IncrementalVoronoi() {}
 
  virtual bool compute();
 
  //virtual void updateFacetNeighbours(const std::vector< boost::shared_ptr<HalfSpace_Rn> >& allHalfSpaces,
      //boost::shared_ptr<Polytope_Rn> newVoronoiCell, unsigned int counter,
      //unsigned int newTruncationStep) {}
 
};
 
class CellByCellVoronoi : public Voronoi_Rn {
 
 public:
  //CellByCellVoronoi() { _inputSpace=0; }
 
  CellByCellVoronoi(const boost::shared_ptr<Polytope_Rn>& is, const std::vector<Point_Rn>& lop):Voronoi_Rn(is,lop) {}
 
  virtual ~CellByCellVoronoi() {}
 
  virtual bool compute();
 
  //virtual void updateFacetNeighbours(const std::vector< boost::shared_ptr<HalfSpace_Rn> >& allHalfSpaces,
      //boost::shared_ptr<Polytope_Rn> newVoronoiCell, unsigned int counter,
      //unsigned int newTruncationStep) {}
 
};
 
// \class CellByCellVoronoiNgb
// \brief Computes the Voronoi diagram cell by cell and the neighbourhood relationships between them.
//class CellByCellVoronoiNgb : public CellByCellVoronoi {
 
// public:
  //CellByCellVoronoiNgb() { _inputSpace=0; }
 
  //CellByCellVoronoiNgb(const boost::shared_ptr<Polytope_Rn>& is, const std::vector<Point_Rn>& lop):CellByCellVoronoi(is,lop) {}
 
  //virtual ~CellByCellVoronoiNgb() {}
 
  //virtual bool compute();
 
  //virtual void updateFacetNeighbours(
      //const std::vector< boost::shared_ptr<HalfSpace_Rn> >& allHalfSpaces,
      //boost::shared_ptr<Polytope_Rn> newVoronoiCell, unsigned int counter,
      //unsigned int newTruncationStep);
 
 //protected:
  //std::vector< std::vector< std::pair<unsigned int,unsigned int> > > _facetNeighbours;
 
//};
 
class CellByCellVoronoiDist : public CellByCellVoronoi {
 
 public:
  //CellByCellVoronoiDist() { _inputSpace=0; }
 
  CellByCellVoronoiDist(const boost::shared_ptr<Polytope_Rn>& is, const std::vector<Point_Rn>& lop):CellByCellVoronoi(is,lop) {
    _percentageOfSortedHalfSpaces = 100.;
  }
 
  CellByCellVoronoiDist(const boost::shared_ptr<Polytope_Rn>& is, const std::vector<Point_Rn>& lop, double percent):CellByCellVoronoi(is,lop) {
    _percentageOfSortedHalfSpaces = percent;
  }
 
  virtual ~CellByCellVoronoiDist() {}
 
  virtual bool compute();
 
  void processDistances(
      std::vector< std::pair< double, unsigned int > >& allDistances,
      std::vector<Point_Rn>::const_iterator newVoronoiSeed,
      boost::shared_ptr<Polytope_Rn> newVoronoiCell);
 
  void setAverageNumberOfNeighbours(double pc) { _percentageOfSortedHalfSpaces = pc; }
 
 protected:
  double _percentageOfSortedHalfSpaces;
  std::vector< boost::shared_ptr<HalfSpace_Rn> > _allHalfSpaces;
};
 
 
class CellByCellVoronoiDistNgb : public CellByCellVoronoiDist {
 
 public:
  //CellByCellVoronoiDistNgb() { _inputSpace=0; }
 
  CellByCellVoronoiDistNgb(const boost::shared_ptr<Polytope_Rn>& is, const std::vector<Point_Rn>& lop):CellByCellVoronoiDist(is,lop) {}
 
 CellByCellVoronoiDistNgb(const boost::shared_ptr<Polytope_Rn>& is, const std::vector<Point_Rn>& lop, double percent):CellByCellVoronoiDist(is,lop,percent) {}
 
  virtual ~CellByCellVoronoiDistNgb() {}
 
  virtual bool compute();
 
  virtual bool compute(std::vector< Point_Rn >::const_iterator iteBeg, std::vector< Point_Rn >::const_iterator iteEnd);
 
  const std::vector< std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>, unsigned int> > >&
    getFacetNeighbours() const { return _facetNeighbours;}
 
  virtual void allocateFacetNeighbours() { _facetNeighbours.resize(_listOfSeeds.size()); }
  void dumpFacetNeighbours(std::ostream &this_ostream) const;
 
  virtual void updateFacetNeighbours(
      const std::vector< std::pair< double, unsigned int > >& allDistances,
      boost::shared_ptr<Polytope_Rn> newVoronoiCell,
      unsigned int counter, unsigned int newTruncationStep);
 
  void dumpNgb(std::ostream &this_ostream) const {
    this_ostream << std::endl << "# NEIGHBOURS FOR EACH CELL" << std::endl;
    this_ostream << "Number of facets :" << _facetNeighbours.size() << std::endl;
    {
      for (unsigned int j = 0; j < _facetNeighbours.size(); ++j) {
        this_ostream << "Cell " << j << " :"  << std::endl;
        {
          for (unsigned int k = 0; k < _facetNeighbours[j].size(); ++k) {
            _facetNeighbours[j][k].first->dump(this_ostream);
            this_ostream << ", Ngb = " << _facetNeighbours[j][k].second;
            this_ostream << std::endl;
          }
        }
      } // for (unsigned int j = 0; j < _facetNeighbours.size(); ++j) {
    }
  }
 
 protected:
  std::vector< std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>, unsigned int> > > _facetNeighbours;
 
};
 
 
class NonConvexPolytope {
 
 public:
 
  NonConvexPolytope() {}
 
  virtual ~NonConvexPolytope() {}
 
  void addFacetAndItsVertices(boost::shared_ptr<HalfSpace_Rn> hs, std::vector< boost::shared_ptr<Generator_Rn> >& listOfGen) {
    _listOfHalfSpaces.push_back(hs);
    _listOfGeneratorsPerFacet.push_back(listOfGen);
  }
 
  const std::vector< boost::shared_ptr<HalfSpace_Rn> >& getListOfHalfSpaces() const {return _listOfHalfSpaces;}
 
  const std::vector< std::vector< boost::shared_ptr<Generator_Rn> > >& getListOfGeneratorsPerFacet() const {return _listOfGeneratorsPerFacet;}
 
  void dump(std::ostream &this_ostream) const {
    this_ostream << std::endl << "# NON CONVEX POLYTOPE" << std::endl;
    this_ostream << "Number of facets : " << _listOfHalfSpaces.size() << std::endl;
    for (unsigned int j = 0; j < _listOfHalfSpaces.size(); ++j) {
      this_ostream << "Facet " << j << " :"  << std::endl;
      _listOfHalfSpaces[j]->dump(this_ostream);
      this_ostream << std::endl;
      {
        for (unsigned int k = 0; k < _listOfGeneratorsPerFacet[j].size(); ++k) {
          _listOfGeneratorsPerFacet[j][k]->dump(this_ostream);
          this_ostream << " ";
        }
        this_ostream << std::endl;
      }
    }
  }
 
 protected:
  std::vector< boost::shared_ptr<HalfSpace_Rn> > _listOfHalfSpaces;
  std::vector< std::vector< boost::shared_ptr<Generator_Rn> > > _listOfGeneratorsPerFacet;
 
};
 
 
class VoronoiWithProperties : public CellByCellVoronoiDistNgb {
 
 public:
 
 VoronoiWithProperties(const boost::shared_ptr<Polytope_Rn>& is, const std::vector<Point_Rn>& lop, const std::vector<int>& listOfProp, double percent):CellByCellVoronoiDistNgb(is,lop,percent) {
    _listOfSeedProperties = listOfProp;
    allocateFacetNeighbours();
  }
 
  virtual ~VoronoiWithProperties() {}
 
  void allocateFacetNeighbours() { _facetNeighbours.resize(_listOfSeeds.size()); }
 
  void dumpNeighbours(std::ostream &this_ostream) const;
  void dumpFacetNeighbours(std::ostream &this_ostream) const;
 
  void addHalfSpaceAndNeighbour(unsigned int cellCounter, boost::shared_ptr<HalfSpace_Rn> hs, unsigned int ngbCell) {
    std::pair< boost::shared_ptr<HalfSpace_Rn>, unsigned int > curHalfspace_ngbPolytope(hs, ngbCell);
    _facetNeighbours[cellCounter].push_back(curHalfspace_ngbPolytope);
  }
 
  // Non-convex geometry //
  unsigned int numberOfNonConvexPolytope() const { return _listOfNonConvexPolytopes.size(); }
 
  boost::shared_ptr< NonConvexPolytope > getNonConvexPolytope(unsigned int idx) { return _listOfNonConvexPolytopes[idx]; }
 
  unsigned int getNonConvexPolytopeProperty(unsigned int idx) { return _listOfNonConvexPolytopeProperties[idx]; }
 
  // Unite different Voronoi cells or polytopes which share at least one common facet.
  //virtual bool compute();
 
  bool fuseCellsWithSameProperty();
 
  bool fuseCellsWithSameProperty(std::vector< std::vector< unsigned int > >& newListOfNonConvexPolytopes);
 
  bool fuseCellsWithSameProperty(std::vector< std::vector< boost::shared_ptr<Polytope_Rn> > >& newListOfNonConvexPolytopes);
 
 protected:
  void propagate(std::vector< bool >& listOfAlreadyProcessedSeeds, unsigned int nbCell, unsigned int nbProperty);
 
 protected:
  std::vector< int > _listOfSeedProperties;
  std::vector< boost::shared_ptr< NonConvexPolytope > > _listOfNonConvexPolytopes;
  std::vector< int > _listOfNonConvexPolytopeProperties;
 
};
 
#endif // VORONOI_Rn