36 const std::vector<Point_Rn>& listOfSeeds):_inputSpace(inputSpace),_listOfSeeds(listOfSeeds) {
40 boost::shared_ptr<HalfSpace_Rn>
Voronoi_Rn::computeMidPlane(std::vector<Point_Rn>::const_iterator iteSeed1, std::vector<Point_Rn>::const_iterator iteSeed2) {
41 unsigned int dimension = iteSeed1->dimension();
42 boost::shared_ptr<HalfSpace_Rn> HS;
44 double sum_square = 0.;
45 for (
unsigned int coord_count=0; coord_count<dimension; coord_count++) {
46 HS->setCoefficient(coord_count, iteSeed1->getCoordinate(coord_count)-iteSeed2->getCoordinate(coord_count));
47 double sq = iteSeed1->getCoordinate(coord_count)*iteSeed1->getCoordinate(coord_count);
48 sq -= iteSeed2->getCoordinate(coord_count)*iteSeed2->getCoordinate(coord_count);
52 HS->setConstant(-sum_square);
63 out << std::endl <<
"#VORONOI DIAGRAM" << std::endl;
65 std::vector< boost::shared_ptr<Polytope_Rn> >::const_iterator itePC=
_listOfVoronoiCells.begin();
67 out <<
"# Cell "<< nb << std::endl;
84 throw std::domain_error(
"Voronoi_Rn::gnuplot(std::ostream& out) dimension is not 2 ");
87 std::vector< boost::shared_ptr<Polytope_Rn> >::const_iterator iteVC=_listOfVoronoiCells.begin();
88 {
for (; iteVC!=_listOfVoronoiCells.end(); ++iteVC) {
89 double frac = (double)nb / (
double)(*iteVC)->numberOfGenerators();
90 std::ostringstream stream_;
92 std::string valString = stream_.str();
101 throw std::length_error(
"IncrementalVoronoi::compute() needs seeds as input!");
115 unsigned int counter = 0;
116 {
for (std::vector<Point_Rn>::const_iterator newVoronoiSeed = (
_listOfSeeds.begin()+1); newVoronoiSeed!=
_listOfSeeds.end(); ++newVoronoiSeed) {
119 std::cout << std::endl;
120 std::cout <<
"Seed " << newVoronoiSeed-
_listOfSeeds.begin() <<
": ";
121 (newVoronoiSeed)->save(std::cout);
122 std::cout << std::endl;
129 unsigned int newTruncationStep = newVoronoiCell->numberOfHalfSpaces();
130 {
for (std::vector<Point_Rn>::const_iterator processedSeed =
_listOfSeeds.begin(); processedSeed!=newVoronoiSeed; ++processedSeed) {
132 boost::shared_ptr<HalfSpace_Rn> HS =
computeMidPlane(newVoronoiSeed, processedSeed);
133 newVoronoiCell->addHalfSpace(HS);
139 boost::shared_ptr<PolyhedralCone_Rn>,
142 DD(newVoronoiCell, lexmin_ite, NRP, newTruncationStep);
148 std::vector<Point_Rn>::const_iterator processedSeed;
149 std::vector< boost::shared_ptr<Polytope_Rn> >::iterator oldVoronoiCell;
160 boost::shared_ptr<HalfSpace_Rn> HS =
computeMidPlane(processedSeed, newVoronoiSeed);
161 unsigned int oldTruncationStep = (*oldVoronoiCell)->numberOfHalfSpaces();
162 (*oldVoronoiCell)->addHalfSpace(HS);
164 constIteratorOfListOfGeometricObjects< boost::shared_ptr<HalfSpace_Rn> > lexmin_ite2((*oldVoronoiCell)->getListOfHalfSpaces());
167 boost::shared_ptr<PolyhedralCone_Rn>,
168 constIteratorOfListOfGeometricObjects< boost::shared_ptr<HalfSpace_Rn> >,
170 DD2(*oldVoronoiCell, lexmin_ite2, NRP2, oldTruncationStep);
191 throw std::length_error(
"CellByCellVoronoi::compute() needs seeds as input!");
201 unsigned int counter = 0;
202 {
for (std::vector<Point_Rn>::const_iterator newVoronoiSeed =
_listOfSeeds.begin(); newVoronoiSeed!=
_listOfSeeds.end(); ++newVoronoiSeed) {
205 std::cout << std::endl;
206 std::cout <<
"Seed " << newVoronoiSeed-
_listOfSeeds.begin() <<
": ";
207 (newVoronoiSeed)->save(std::cout);
208 std::cout << std::endl;
215 unsigned int newTruncationStep = newVoronoiCell->numberOfHalfSpaces();
216 {
for (std::vector<Point_Rn>::const_iterator currentSeed =
_listOfSeeds.begin(); currentSeed!=
_listOfSeeds.end(); ++currentSeed) {
217 if (currentSeed != newVoronoiSeed) {
219 boost::shared_ptr<HalfSpace_Rn> HS =
computeMidPlane(newVoronoiSeed, currentSeed);
220 newVoronoiCell->addHalfSpace(HS);
227 boost::shared_ptr<PolyhedralCone_Rn>,
230 DD(newVoronoiCell, lexmin_ite, NRP, newTruncationStep);
380 bool operator() (std::pair<double, unsigned int> pt1, std::pair<double, unsigned int> pt2) {
return (pt1.first < pt2.first);}
384 std::vector< std::pair< double, unsigned int > >& allDistances,
385 std::vector<Point_Rn>::const_iterator newVoronoiSeed,
386 boost::shared_ptr<Polytope_Rn> newVoronoiCell)
389 allDistances.clear();
390 std::pair< double, unsigned int > v;
393 unsigned int distCounter = 0;
394 {
for (std::vector<Point_Rn>::const_iterator currentSeed =
_listOfSeeds.begin(); currentSeed!=
_listOfSeeds.end(); ++currentSeed) {
395 if (currentSeed != newVoronoiSeed) {
396 boost::numeric::ublas::vector<double> v1 = currentSeed->vect();
397 v1 -= newVoronoiSeed->vect();
398 allDistances[distCounter].first = norm_2(v1);
401 allDistances[distCounter].first = 0.;
404 allDistances[distCounter].second = distCounter;
413 std::partial_sort(allDistances.begin(), allDistances.begin()+nbOfSortedSeeds, allDistances.end(),
thisSortOnFirstCoord);
427 for (iteHSnewVoronoiSeed.begin(); iteHSnewVoronoiSeed.end()!=
true; iteHSnewVoronoiSeed.next())
429 {
for (
unsigned int i=1; i<allDistances.size(); ++i) {
431 std::vector<Point_Rn>::const_iterator currentSeed =
_listOfSeeds.begin()+allDistances[i].second;
433 boost::shared_ptr<HalfSpace_Rn> HS =
computeMidPlane(newVoronoiSeed, currentSeed);
434 newVoronoiCell->addHalfSpace(HS);
442 throw std::length_error(
"CellByCellVoronoiDist::compute() needs seeds as input!");
452 unsigned int counter = 0;
453 {
for (std::vector<Point_Rn>::const_iterator newVoronoiSeed =
_listOfSeeds.begin(); newVoronoiSeed!=
_listOfSeeds.end(); ++newVoronoiSeed) {
456 std::cout << std::endl;
457 std::cout <<
"Seed " << newVoronoiSeed-
_listOfSeeds.begin() <<
": ";
458 (newVoronoiSeed)->save(std::cout);
459 std::cout << std::endl;
466 unsigned int newTruncationStep = newVoronoiCell->numberOfHalfSpaces();
469 std::vector< std::pair< double, unsigned int > > allDistances;
476 boost::shared_ptr<PolyhedralCone_Rn>,
479 DD(newVoronoiCell, lexmin_ite, NRP, newTruncationStep);
499 std::vector< Point_Rn >::const_iterator iteBeg =
_listOfSeeds.begin();
500 std::vector< Point_Rn >::const_iterator iteEnd =
_listOfSeeds.end();
505 std::vector< Point_Rn >::const_iterator iteBeg,
506 std::vector< Point_Rn >::const_iterator iteEnd)
throw (std::length_error) {
508 if (_listOfSeeds.empty() ==
true)
509 throw std::length_error(
"CellByCellVoronoiDistNgb::compute() needs seeds as input!");
511 if (_listOfSeeds.size() == 1) {
513 boost::shared_ptr<Polytope_Rn> is(
new Polytope_Rn( *_inputSpace ));
514 _listOfVoronoiCells[0] = is;
518 allocateFacetNeighbours();
521 unsigned int counter = iteBeg - _listOfSeeds.begin();
522 {
for (std::vector<Point_Rn>::const_iterator newVoronoiSeed = iteBeg; newVoronoiSeed!=iteEnd; ++newVoronoiSeed) {
525 std::cout << std::endl;
526 std::cout <<
"Seed " << newVoronoiSeed-_listOfSeeds.begin() <<
": ";
527 (newVoronoiSeed)->save(std::cout);
528 std::cout << std::endl;
534 boost::shared_ptr<Polytope_Rn> newVoronoiCell(
new Polytope_Rn(*_inputSpace));
535 unsigned int newTruncationStep = newVoronoiCell->numberOfHalfSpaces();
538 std::vector< std::pair< double, unsigned int > > allDistances;
539 processDistances(allDistances, newVoronoiSeed, newVoronoiCell);
545 boost::shared_ptr<PolyhedralCone_Rn>,
548 DD(newVoronoiCell, lexmin_ite, NRP, newTruncationStep);
550 _listOfVoronoiCells[counter] = newVoronoiCell;
557 updateFacetNeighbours(allDistances, newVoronoiCell, counter, newTruncationStep);
574 std::vector< std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>,
unsigned int> > >::const_iterator iteSeed;
576 unsigned int cellCounter = 0;
578 this_ostream << iteSeed->size() <<
" ";
579 std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>,
unsigned int> >::const_iterator iteCurHS_NgbNb;
580 for (iteCurHS_NgbNb=iteSeed->begin(); iteCurHS_NgbNb!=iteSeed->end(); ++iteCurHS_NgbNb) {
581 this_ostream <<
_listOfVoronoiCells[cellCounter]->getHalfSpaceNumber(iteCurHS_NgbNb->first) <<
" " << iteCurHS_NgbNb->second <<
" ";
583 this_ostream << std::endl;
589 const std::vector< std::pair< double, unsigned int > >& allDistances,
590 boost::shared_ptr<Polytope_Rn> newVoronoiCell,
591 unsigned int counter,
unsigned int newTruncationStep) {
593 {
for (iteHS_Vorcell.begin(); iteHS_Vorcell.end()!=
true; iteHS_Vorcell.next()) {
595 std::vector< boost::shared_ptr<HalfSpace_Rn> >::const_iterator iteAll;
596 unsigned int hs_all_counter = newTruncationStep;
598 if (iteHS_Vorcell.current() == *iteAll) {
606 unsigned int ngbSeedNumber = allDistances[hs_all_counter-newTruncationStep+1].second;
607 std::pair< boost::shared_ptr<HalfSpace_Rn>,
unsigned int > curHalfspace_ngbPolytope(iteHS_Vorcell.current(), ngbSeedNumber);
619 std::ifstream file(filename.c_str(), std::ifstream::in);
621 std::string s(
"VoronoiWithProperties::loadProp() Unable to open ");
624 throw std::ios_base::failure(s);
629 unsigned int numberOfSeeds, counter=0;
631 std::getline(file, line);
632 std::istringstream iline(line);
633 iline >> numberOfSeeds;
634 while (counter != numberOfSeeds) {
635 std::getline(file, line);
636 std::istringstream iline2(line);
638 propList.push_back(prop);
645 std::ifstream file(filename.c_str(), std::ifstream::in);
647 std::string s(
"VoronoiWithProperties::loadProperties() Unable to open ");
650 throw std::ios_base::failure(s);
653 _listOfSeedProperties.clear();
655 unsigned int numberOfSeeds, counter=0;
657 std::getline(file, line);
658 std::istringstream iline(line);
659 iline >> numberOfSeeds;
660 while (counter != numberOfSeeds) {
661 std::getline(file, line);
662 std::istringstream iline2(line);
664 _listOfSeedProperties.push_back(prop);
671 boost::shared_ptr<Polytope_Rn> listOfPointsAsVDesc(
new Polytope_Rn());
674 {
for (iteGN.begin(); iteGN.end()!=
true; iteGN.next()) {
676 iteGN.current()->getCoordinate(0),
677 iteGN.current()->getCoordinate(1),
678 iteGN.current()->getCoordinate(2)) );
683 boost::shared_ptr<Polytope_Rn> thisCell(
new Polytope_Rn());
685 _listOfVoronoiCells.push_back(thisCell);
689 std::ifstream file(filename.c_str(), std::ifstream::in);
691 std::string s(
"VoronoiWithProperties::loadFacetNeighbours() Unable to open ");
694 throw std::ios_base::failure(s);
696 if (_listOfVoronoiCells.empty() ==
true)
697 throw std::length_error(
"VoronoiWithProperties::loadFacetNeighbours() needs polytopes!");
699 allocateFacetNeighbours();
700 unsigned int numberOfSeeds, cellCounter = 0;
702 std::getline(file, line);
703 std::istringstream iline(line);
704 iline >> numberOfSeeds;
706 while (cellCounter != numberOfSeeds) {
707 unsigned int nbnbNgb, nbFacet, nbNgb;
708 std::getline(file, line);
709 std::istringstream iline2(line);
711 for (
unsigned int coord_count=0; coord_count<nbnbNgb; coord_count++) {
714 addHalfSpaceAndNeighbour(cellCounter, _listOfVoronoiCells[cellCounter]->getHalfSpace(nbFacet), nbNgb);
722 std::vector< std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>,
unsigned int> > >::const_iterator iteSeed;
724 unsigned int cellCounter = 0;
727 std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>,
unsigned int> >::const_iterator iteCurHS_NgbNb;
728 for (iteCurHS_NgbNb=iteSeed->begin(); iteCurHS_NgbNb!=iteSeed->end(); ++iteCurHS_NgbNb) {
729 this_ostream << iteCurHS_NgbNb->second <<
" ";
731 this_ostream << std::endl;
737 std::vector< std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>,
unsigned int> > >::const_iterator iteSeed;
739 unsigned int cellCounter = 0;
741 this_ostream << iteSeed->size() <<
" ";
742 std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>,
unsigned int> >::const_iterator iteCurHS_NgbNb;
743 for (iteCurHS_NgbNb=iteSeed->begin(); iteCurHS_NgbNb!=iteSeed->end(); ++iteCurHS_NgbNb) {
744 this_ostream <<
_listOfVoronoiCells[cellCounter]->getHalfSpaceNumber(iteCurHS_NgbNb->first) <<
" " << iteCurHS_NgbNb->second <<
" ";
746 this_ostream << std::endl;
753 throw std::length_error(
"VoronoiWithProperties::fuseCellsWithSameProperty() needs seeds as input!");
754 unsigned int currentSeedNb = 0;
755 std::vector< boost::shared_ptr<Polytope_Rn> >::iterator iteCell;
756 std::vector< std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>,
unsigned int> > >::iterator iteSeed;
761 std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>,
unsigned int> >::iterator iteCurHS_NgbNb;
762 for (iteCurHS_NgbNb=iteSeed->begin(); iteCurHS_NgbNb!=iteSeed->end(); ++iteCurHS_NgbNb) {
764 unsigned int ngbNb = iteCurHS_NgbNb->second;
768 if ((*iteCell)->numberOfHalfSpaces() > 0) {
770 boost::shared_ptr<HalfSpace_Rn> HS = iteCurHS_NgbNb->first;
772 (*iteCell)->removeHalfSpaceFromListAndGenerators(HS);
784 std::set< unsigned int > allProcessedSeeds;
785 newListOfNonConvexPolytopes.clear();
788 if (allProcessedSeeds.find(currentSeedNb) == allProcessedSeeds.end()) {
790 std::vector< unsigned int > v;
791 newListOfNonConvexPolytopes.push_back(v);
793 std::stack< unsigned int > allNeighboursWithSameProperty;
794 allNeighboursWithSameProperty.push(currentSeedNb);
797 if (allProcessedSeeds.insert(currentSeedNb).second ==
true) {
801 newListOfNonConvexPolytopes[newListOfNonConvexPolytopes.size()-1].push_back(currentSeedNb);
804 while (!allNeighboursWithSameProperty.empty()) {
805 unsigned int topSeed = allNeighboursWithSameProperty.top();
806 allNeighboursWithSameProperty.pop();
807 std::vector< std::pair<boost::shared_ptr<HalfSpace_Rn>,
unsigned int> >::iterator iteCurHS_NgbNb;
809 unsigned int ngbSeed = iteCurHS_NgbNb->second;
810 if (allProcessedSeeds.find(ngbSeed) == allProcessedSeeds.end()) {
812 allNeighboursWithSameProperty.push(ngbSeed);
813 allProcessedSeeds.insert(ngbSeed);
816 newListOfNonConvexPolytopes[newListOfNonConvexPolytopes.size()-1].push_back(ngbSeed);
832 throw (std::length_error)
835 throw std::length_error(
"VoronoiWithProperties::fuseCellsWithSameProperty() needs seeds as input!");
836 std::vector< std::vector< unsigned int > > allNonConvexPolytopeIds;
839 newListOfNonConvexPolytopes.resize(allNonConvexPolytopeIds.size());
840 std::vector< std::vector< unsigned int > >::const_iterator iteNCPIds = allNonConvexPolytopeIds.begin();
841 unsigned int currentSeedNb = 0;
842 for (; iteNCPIds != allNonConvexPolytopeIds.end(); ++iteNCPIds) {
843 std::vector< unsigned int >::const_iterator iteCurrentNCPId = iteNCPIds->begin();
844 for (; iteCurrentNCPId != iteNCPIds->end(); ++iteCurrentNCPId) {
845 newListOfNonConvexPolytopes[currentSeedNb].push_back(
_listOfVoronoiCells[*iteCurrentNCPId]);
void loadProperties(const std::string &filename)
virtual bool compute()
Run the whole algorithm.
Creation of a n-coordinate geometric point designed to be shared by its neighbour faces...
std::vector< int > _listOfSeedProperties
The list of properties associated to the seeds.
double _percentageOfSortedHalfSpaces
The amount of half-spaces we want to sort.
virtual bool compute()
Run the whole algorithm.
void dump(std::ostream &out) const
Dump the cell structure on the given output.
static void loadProp(const std::string &filename, std::vector< int > &propList)
virtual bool compute()
Run the whole algorithm.
virtual bool compute()
Run the whole algorithm.
Model a polytope using its two equivalent definitions : the convex hull and the half-space intersecti...
boost::shared_ptr< HalfSpace_Rn > computeMidPlane(std::vector< Point_Rn >::const_iterator seed1, std::vector< Point_Rn >::const_iterator seed2)
Compute the half-space containing seed1, in between seed1 and seed2, according to the growing seed pr...
A half-space whose frontier is a linear (n-1) dimension space. _constant + _coefficients[0].x1 + ... + _coefficients[n-1].xn >= 0.
bool operator()(std::pair< double, unsigned int > pt1, std::pair< double, unsigned int > pt2)
const std::vector< Point_Rn > & _listOfSeeds
The list of input points.
static void gnuplot2D(const boost::shared_ptr< Polytope_Rn > &polygon, const std::string &name, double col, std::ostream &out)
Provide the drwing of polygon under the gnuplot format.
void gnuplot(std::ostream &out) const
static polito_EXPORT void load(const std::string &filename, boost::shared_ptr< PolyhedralCone_Rn > POLY)
Load the main data format to store polytopes.
std::vector< boost::shared_ptr< Polytope_Rn > > _listOfVoronoiCells
The list of polytopes partitioning the whole space.
Voronoi_Rn(const boost::shared_ptr< Polytope_Rn > &inputSpace, const std::vector< Point_Rn > &listOfPoints)
Refers to the class WithProperties.
struct sortOnFirstCoord thisSortOnFirstCoord
bool checkTopologyAndGeometry() const
void processDistances(std::vector< std::pair< double, unsigned int > > &allDistances, std::vector< Point_Rn >::const_iterator newVoronoiSeed, boost::shared_ptr< Polytope_Rn > newVoronoiCell)
The distance criterion is going to be used to classify partially or globally the way in which we proc...
const boost::shared_ptr< Polytope_Rn > & _inputSpace
The original space to be divided.
static polito_EXPORT unsigned int getDimension()
Return the dimension of the cartesian space we work in.
This class can be more time-consuming than WeakRedundancyProcessing or NoRedundancyProcessing because...
void loadCell(const std::string &filename)
virtual void updateFacetNeighbours(const std::vector< std::pair< double, unsigned int > > &allDistances, boost::shared_ptr< Polytope_Rn > newVoronoiCell, unsigned int counter, unsigned int newTruncationStep)
This class is designed to run the list of all geometric objects representing a polytope.
void dumpFacetNeighbours(std::ostream &this_ostream) const
void dumpFacetNeighbours(std::ostream &this_ostream) const
std::vector< std::vector< std::pair< boost::shared_ptr< HalfSpace_Rn >, unsigned int > > > _facetNeighbours
For the current cell, store its neighbour numbers. _facetNeighbours[i] = { (H0, i0), (H1, i1), ... }.
void loadFacetNeighbours(const std::string &filename)
std::vector< std::vector< std::pair< boost::shared_ptr< HalfSpace_Rn >, unsigned int > > > _facetNeighbours
For the current cell, store its neighbour numbers. _facetNeighbours[i] = { (H0, i0), (H1, i1), ... }.
std::vector< boost::shared_ptr< HalfSpace_Rn > > _allHalfSpaces
For each seed, the list of the half-spaces used to build its cell.
The algorithm implemented here is an incremental algorithm as mentioned in How Good are Convex Hull ...
void loadSeeds(const std::string &filename)
std::vector< boost::shared_ptr< Polytope_Rn > > _listOfVoronoiCells
The list of polytopes partitioning the whole space.
void dumpNeighbours(std::ostream &this_ostream) const
bool fuseCellsWithSameProperty(std::vector< std::vector< unsigned int > > &newListOfNonConvexPolytopes)
Run the whole algorithm: refer to the base class.