Drake
Drake C++ Documentation

Detailed Description

Implements the convex hull of a set of convex sets.

The convex hull of multiple sets is defined as the smallest convex set that contains all the sets. Given non-empty convex sets {X₁, X₂, ..., Xₙ}, the convex hull is the set of all convex combinations of points in the sets, i.e. {∑ᵢ λᵢ xᵢ | xᵢ ∈ Xᵢ, λᵢ ≥ 0, ∑ᵢ λᵢ = 1}.

#include <drake/geometry/optimization/convex_hull.h>

Public Member Functions

 ConvexHull (const ConvexSets &sets, const bool remove_empty_sets=true)
 Constructs the convex hull from a vector of convex sets. More...
 
 ~ConvexHull () final
 
const ConvexSetssets () const
 Returns the participating convex sets. More...
 
const ConvexSetsparticipating_sets () const
 Returns the participating sets in the convex hull. More...
 
bool empty_sets_removed () const
 Returns true if this was constructed with remove_empty_sets=true. More...
 
const ConvexSetelement (int index) const
 Returns a reference to the convex set at the given index (including empty sets). More...
 
int num_elements () const
 Returns the number of convex sets defining the convex hull (including empty sets). More...
 
bool IsEmpty () const
 
double CalcVolume () const
 
Implements CopyConstructible, CopyAssignable, MoveConstructible, MoveAssignable
 ConvexHull (const ConvexHull &)=default
 
ConvexHulloperator= (const ConvexHull &)=default
 
 ConvexHull (ConvexHull &&)=default
 
ConvexHulloperator= (ConvexHull &&)=default
 
- Public Member Functions inherited from ConvexSet
virtual ~ConvexSet ()
 
std::unique_ptr< ConvexSetClone () const
 Creates a unique deep copy of this set. More...
 
int ambient_dimension () const
 Returns the dimension of the vector space in which the elements of this set are evaluated. More...
 
bool IntersectsWith (const ConvexSet &other) const
 Returns true iff the intersection between this and other is non-empty. More...
 
bool IsBounded () const
 Returns true iff the set is bounded, e.g., there exists an element-wise finite lower and upper bound for the set. More...
 
bool IsEmpty () const
 Returns true iff the set is empty. More...
 
std::optional< Eigen::VectorXd > MaybeGetPoint () const
 If this set trivially contains exactly one point, returns the value of that point. More...
 
std::optional< Eigen::VectorXd > MaybeGetFeasiblePoint () const
 Returns a feasible point within this convex set if it is nonempty, and nullopt otherwise. More...
 
bool PointInSet (const Eigen::Ref< const Eigen::VectorXd > &x, double tol=0) const
 Returns true iff the point x is contained in the set. More...
 
std::pair< VectorX< symbolic::Variable >, std::vector< solvers::Binding< solvers::Constraint > > > AddPointInSetConstraints (solvers::MathematicalProgram *prog, const Eigen::Ref< const solvers::VectorXDecisionVariable > &vars) const
 Adds a constraint to an existing MathematicalProgram enforcing that the point defined by vars is inside the set. More...
 
std::vector< solvers::Binding< solvers::Constraint > > AddPointInNonnegativeScalingConstraints (solvers::MathematicalProgram *prog, const Eigen::Ref< const solvers::VectorXDecisionVariable > &x, const symbolic::Variable &t) const
 Let S be this convex set. More...
 
std::vector< solvers::Binding< solvers::Constraint > > AddPointInNonnegativeScalingConstraints (solvers::MathematicalProgram *prog, const Eigen::Ref< const Eigen::MatrixXd > &A, const Eigen::Ref< const Eigen::VectorXd > &b, const Eigen::Ref< const Eigen::VectorXd > &c, double d, const Eigen::Ref< const solvers::VectorXDecisionVariable > &x, const Eigen::Ref< const solvers::VectorXDecisionVariable > &t) const
 Let S be this convex set. More...
 
std::pair< std::unique_ptr< Shape >, math::RigidTransformd > ToShapeWithPose () const
 Constructs a Shape and a pose of the set in the world frame for use in the SceneGraph geometry ecosystem. More...
 
double CalcVolume () const
 Computes the exact volume for the convex set. More...
 
SampledVolume CalcVolumeViaSampling (RandomGenerator *generator, const double desired_rel_accuracy=1e-2, const int max_num_samples=1e4) const
 Calculates an estimate of the volume of the convex set using sampling and performing Monte Carlo integration. More...
 
std::optional< std::pair< std::vector< double >, Eigen::MatrixXd > > Projection (const Eigen::Ref< const Eigen::MatrixXd > &points) const
 Computes in the L₂ norm the distance and the nearest point in this convex set to every column of points. More...
 
bool has_exact_volume () const
 Returns true if the exact volume can be computed for this convex set instance. More...
 

Additional Inherited Members

- Protected Member Functions inherited from ConvexSet
 ConvexSet (int ambient_dimension, bool has_exact_volume)
 For use by derived classes to construct a ConvexSet. More...
 
template<typename Archive >
void Serialize (Archive *a)
 Implements non-virtual base class serialization. More...
 
virtual std::vector< std::optional< double > > DoProjectionShortcut (const Eigen::Ref< const Eigen::MatrixXd > &points, EigenPtr< Eigen::MatrixXd > projected_points) const
 Non-virtual interface implementation for DoProjectionShortcut(). More...
 
virtual std::optional< Eigen::VectorXd > DoMaybeGetFeasiblePoint () const
 Non-virtual interface implementation for MaybeGetFeasiblePoint(). More...
 
virtual std::optional< bool > DoPointInSetShortcut (const Eigen::Ref< const Eigen::VectorXd > &x, double tol) const
 A non-virtual interface implementation for PointInSet() that should be used when the PointInSet() can be computed more efficiently than solving a convex program. More...
 
virtual double DoCalcVolume () const
 Non-virtual interface implementation for CalcVolume(). More...
 
std::optional< symbolic::VariableHandleZeroAmbientDimensionConstraints (solvers::MathematicalProgram *prog, const ConvexSet &set, std::vector< solvers::Binding< solvers::Constraint >> *constraints) const
 Instances of subclasses such as CartesianProduct and MinkowskiSum can have constituent sets with zero ambient dimension, which much be handled in a special manner when calling methods such as DoAddPointInSetConstraints. More...
 
virtual std::unique_ptr< ConvexSetDoAffineHullShortcut (std::optional< double > tol) const
 NVI implementation of DoAffineHullShortcut, which trivially returns null. More...
 
 ConvexSet (const ConvexSet &)=default
 
ConvexSetoperator= (const ConvexSet &)=default
 
 ConvexSet (ConvexSet &&)=default
 
ConvexSetoperator= (ConvexSet &&)=default
 
- Static Protected Member Functions inherited from ConvexSet
static std::unique_ptr< ConvexSetAffineHullShortcut (const ConvexSet &self, std::optional< double > tol)
 When there is a more efficient strategy to compute the affine hull of this set, returns affine hull as an AffineSubspace. More...
 

Constructor & Destructor Documentation

◆ ConvexHull() [1/3]

ConvexHull ( const ConvexHull )
default

◆ ConvexHull() [2/3]

ConvexHull ( ConvexHull &&  )
default

◆ ConvexHull() [3/3]

ConvexHull ( const ConvexSets sets,
const bool  remove_empty_sets = true 
)
explicit

Constructs the convex hull from a vector of convex sets.

Parameters
setsA vector of convex sets that define the convex hull.
remove_empty_setsIf true, the constructor will check if any of the sets are empty and will not consider them. If false, the constructor will not check if any of the sets are empty.
Warning
If remove_empty_sets is set to false, but some of the sets are in fact empty, then unexpected and incorrect results may occur. Only set this flag to false if you are sure that your sets are non-empty and performance in the constructor is critical.

◆ ~ConvexHull()

~ConvexHull ( )
final

Member Function Documentation

◆ CalcVolume()

double CalcVolume
Exceptions
Notimplemented.

◆ element()

const ConvexSet& element ( int  index) const

Returns a reference to the convex set at the given index (including empty sets).

◆ empty_sets_removed()

bool empty_sets_removed ( ) const

Returns true if this was constructed with remove_empty_sets=true.

◆ IsEmpty()

bool IsEmpty
Note
if called on an instance that was called with remove_empty_sets=false, this function will reconstruct the convex hull with remove_empty_sets=true. Therefore, it is recommended to call this function only once.

◆ num_elements()

int num_elements ( ) const

Returns the number of convex sets defining the convex hull (including empty sets).

◆ operator=() [1/2]

ConvexHull& operator= ( ConvexHull &&  )
default

◆ operator=() [2/2]

ConvexHull& operator= ( const ConvexHull )
default

◆ participating_sets()

const ConvexSets& participating_sets ( ) const

Returns the participating sets in the convex hull.

If the constructor was called with remove_empty_sets=false, this function will return the original sets, including potentially empty sets.

◆ sets()

const ConvexSets& sets ( ) const

Returns the participating convex sets.


The documentation for this class was generated from the following file: