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-2017 : 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 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() throw (std::length_error)=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 throw (std::domain_error);

  void dump(std::ostream& out) const;

  void gnuplot(std::ostream& out) const throw (std::domain_error);

 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() throw (std::length_error);

  //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() throw (std::length_error);

  //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() throw (std::length_error);

  //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() throw (std::length_error);

  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) {}

  virtual ~CellByCellVoronoiDistNgb() {}

  virtual bool compute() throw (std::length_error);

  virtual bool compute(
      std::vector< Point_Rn >::const_iterator iteBeg,
      std::vector< Point_Rn >::const_iterator iteEnd) throw (std::length_error);

  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);

 protected:
  std::vector< std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>, unsigned int> > > _facetNeighbours;

};

class VoronoiWithProperties {

 public:
  VoronoiWithProperties() {}

  VoronoiWithProperties(
      const std::vector< Point_Rn >& listOfSeeds,
      const std::vector< boost::shared_ptr<Polytope_Rn> >& listOfCells,
      const std::vector<int>& listOfProp) {
    _listOfSeeds = listOfSeeds;
    _listOfVoronoiCells = listOfCells;
    _listOfSeedProperties = listOfProp;
    allocateFacetNeighbours();
  }

  VoronoiWithProperties(const CellByCellVoronoiDistNgb& CBCVDN, const std::vector<int>& listOfProp) {
    _listOfSeeds = CBCVDN.getListOfSeeds();
    _facetNeighbours = CBCVDN.getFacetNeighbours();
    _listOfVoronoiCells = CBCVDN.getVoronoiCells();
    _listOfSeedProperties = listOfProp;
  }

  virtual ~VoronoiWithProperties() {}

  static void loadProp(const std::string& filename, std::vector<int>& propList) throw (std::ios_base::failure);

  void loadCell(const std::string& filename) throw (std::ios_base::failure);

  void loadSeeds(const std::string& filename) throw (std::ios_base::failure);

  void loadSeeds(const std::vector<Point_Rn>& listOfPoints3D) {_listOfSeeds = listOfPoints3D;}

  void loadProperties(const std::string& filename) throw (std::ios_base::failure);

  void loadFacetNeighbours(const std::string& filename) throw (std::length_error,std::ios_base::failure);

  //void dumpFacetNeighbours(std::ostream &this_ostream);

  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);
  }

  // Unite different Voronoi cells or polytopes which share at least one common facet.
  //virtual bool compute() throw (std::length_error);

  bool fuseCellsWithSameProperty(std::vector< std::vector< unsigned int > >& newListOfNonConvexPolytopes) throw (std::length_error);

  bool fuseCellsWithSameProperty(std::vector< std::vector< boost::shared_ptr<Polytope_Rn> > >& newListOfNonConvexPolytopes) throw (std::length_error);

 protected:
  std::vector< Point_Rn > _listOfSeeds;
  std::vector< boost::shared_ptr<Polytope_Rn> > _listOfVoronoiCells;
  std::vector< std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>, unsigned int> > > _facetNeighbours;
  std::vector<int> _listOfSeedProperties;

};

#endif // VORONOI_Rn