The algorithm implemented here is an incremental algorithm as mentioned in How Good are Convex Hull Algorithms? (1997) by David Avis and David Bremner. Specific and efficient implementations can be found in The double description method revisited (1996) written by Komei Fukuda and Alain Prodon .
Incremental algorithms for the vertex enumeration problem compute the vertex description by intersecting the defining half-spaces sequentially. An initial simplex is constructed from a subset of n+1 half-spaces and its vertices and 1-skeleton are computed. Additional half-spaces are introduced sequentially and the vertex description and 1-skeleton are updated at each stage. Essentially such an update amounts to identifying and removing all vertices that are not contained in the new half-space, introducing new vertices for all intersections between edges and the bounding hyperplane of the new half-space, and generating the new edges between these new vertices.
This algorithm can be instantiated by polytopes or polyhedral cones, and as a second argument can be instantiated by iterators such as minindex, lexmin, lexmax.
More...
#include <UpdDoubleDescription_Rn.h>
Public Member Functions | |
| UpdDoubleDescription (POLYHEDRON poly, ITERATOR ite, REDUNDANCY_PROCESSING redproc, int truncationStep) | |
| UpdDoubleDescription (POLYHEDRON poly, ITERATOR ite, REDUNDANCY_PROCESSING redproc, int truncationStep, TrackingOperatorToResult &trackerVdesc, TrackingOperatorToResult &trackerHdesc) | |
| virtual | ~UpdDoubleDescription () |
| bool | getIsEmpty () const |
| void | computeVertexStates (std::vector< boost::shared_ptr< Generator_Rn_SD > > &GN_list, const boost::shared_ptr< HalfSpace_Rn > ¤tHalfSpace, std::vector< double > &GN_IN_sp, std::vector< double > &GN_OUT_sp, std::vector< boost::shared_ptr< Generator_Rn_SD > > &GN_IN, std::vector< boost::shared_ptr< Generator_Rn_SD > > &GN_OUT, std::vector< boost::shared_ptr< Generator_Rn_SD > > &GN_ON) |
| For each generator compute its state according to the current half-space. More... | |
| bool | compute (POLYHEDRON poly, ITERATOR iteHS, int truncationStep, std::vector< boost::shared_ptr< Generator_Rn_SD > > &listOfGenSD) |
| The main function splitting the polyhedron cone or polytope 1-skeleton with a list of half-spaces. More... | |
Protected Attributes | |
| bool | _isEmpty |
| Store the current state of the intersection. More... | |
| REDUNDANCY_PROCESSING | _redundancyProcessing |
| This class is dedicated to dealing with redundant half-spaces with the desired policy. More... | |
Detailed Description
template<class POLYHEDRON, class ITERATOR, class REDUNDANCY_PROCESSING>
class UpdDoubleDescription< POLYHEDRON, ITERATOR, REDUNDANCY_PROCESSING >
The algorithm implemented here is an incremental algorithm as mentioned in How Good are Convex Hull Algorithms? (1997) by David Avis and David Bremner. Specific and efficient implementations can be found in The double description method revisited (1996) written by Komei Fukuda and Alain Prodon .
Incremental algorithms for the vertex enumeration problem compute the vertex description by intersecting the defining half-spaces sequentially. An initial simplex is constructed from a subset of n+1 half-spaces and its vertices and 1-skeleton are computed. Additional half-spaces are introduced sequentially and the vertex description and 1-skeleton are updated at each stage. Essentially such an update amounts to identifying and removing all vertices that are not contained in the new half-space, introducing new vertices for all intersections between edges and the bounding hyperplane of the new half-space, and generating the new edges between these new vertices.
This algorithm can be instantiated by polytopes or polyhedral cones, and as a second argument can be instantiated by iterators such as minindex, lexmin, lexmax.
- minindex : Insert the half-spaces in the order given by the input.
- lexmin : Insert the half-spaces in the the lexicographic increasing order of coefficient vectors.
- lexmax : Insert the half-spaces in the the lexicographic decreasing order of coefficient vectors.
UpdDoubleDescription recomputes on the fly the connections between generators unlike the class DoubleDescription.
Definition at line 50 of file UpdDoubleDescription_Rn.h.
Constructor & Destructor Documentation
◆ UpdDoubleDescription() [1/2]
|
inline |
◆ UpdDoubleDescription() [2/2]
|
inline |
Compute the double description tracking all entities and considering the operator1 as the V-description and operator2 as the H-description.
Definition at line 94 of file UpdDoubleDescription_Rn.h.
◆ ~UpdDoubleDescription()
|
inlinevirtual |
Definition at line 168 of file UpdDoubleDescription_Rn.h.
Member Function Documentation
◆ compute()
|
inline |
The main function splitting the polyhedron cone or polytope 1-skeleton with a list of half-spaces.
Definition at line 238 of file UpdDoubleDescription_Rn.h.
◆ computeVertexStates()
|
inline |
For each generator compute its state according to the current half-space.
Definition at line 173 of file UpdDoubleDescription_Rn.h.
◆ getIsEmpty()
|
inline |
Definition at line 170 of file UpdDoubleDescription_Rn.h.
Member Data Documentation
◆ _isEmpty
|
protected |
Store the current state of the intersection.
Definition at line 545 of file UpdDoubleDescription_Rn.h.
◆ _redundancyProcessing
|
protected |
This class is dedicated to dealing with redundant half-spaces with the desired policy.
Definition at line 547 of file UpdDoubleDescription_Rn.h.
The documentation for this class was generated from the following file:
- /mnt/c/Users/vindelos/Documents/TEST/TEST/co/politopix/trunk/UpdDoubleDescription_Rn.h
