Multi-dimensional paving representation of a connected subset. More...

#include <codac_ConnectedSubset.h>

Inheritance diagram for codac::ConnectedSubset:

Collaboration diagram for codac::ConnectedSubset:

Public Member Functions
Methods related to topological degree
bool	zero_proven (const std::function< IntervalVector(const IntervalVector &)> &f)
	Tests if an unknown function \(\mathbf{f}^*\) enclosed by \([\mathbf{f}]\) vanishes at least once on this subset.

int	zeros_number (const std::function< IntervalVector(const IntervalVector &)> &f, const std::function< IntervalMatrix(const IntervalVector &)> &Jf, float precision)
	Counts the number of zeros of an uncertain function \(\mathbf{f}^*\) enclosed by \([\mathbf{f}]\) on this subset.

Public Member Functions inherited from codac::Set
	Set (const IntervalVector &box, SetValue value=SetValue::UNKNOWN)
	Creates a set.

	~Set ()
	Set destructor.

SetValue	value () const
	Returns the value of this set.

int	size () const
	Returns the dimension of the paving.

const IntervalVector &	box () const
	Returns the n-dimensional box representing this set.

void	set_value (SetValue value)
	Sets the integer value for this set.

Protected Member Functions
Protected methods for topological degree computation
int	topological_degree (const std::function< IntervalVector(const IntervalVector &)> &f)
	Computes the topological degree related to \(\mathbf{f}\).

bool	all_positive_signs (const std::vector< int > &v_s) const
	Returns `true` if all items in v_s are positive.

int	orientation (const IntervalVector &b, const IntervalVector &parent_coface, int orientation) const
	Returns orientation of vector b.

int	compute_local_degree (const std::function< IntervalVector(const IntervalVector &)> &f, const IntervalVector &b, const IntervalVector &common_cocoface) const
	Computes local degree related to \(\mathbf{f}\).

std::vector< int >	sign_vector (const std::function< IntervalVector(const IntervalVector &)> &f, const IntervalVector &b, const IntervalVector &common_cocoface) const
	Returns a vector of signs represented as integers.

std::vector< IntervalVector >	get_cofaces (const IntervalVector &b) const
	Returns a vector of cofaces related to \([\mathbf{b}]\).

std::vector< IntervalVector >	get_cofaces (const IntervalVector &b, const IntervalVector &common_cocoface) const
	Returns a vector of cofaces related to \([\mathbf{b}]\), common_cocoface.

int	box_dimension (const IntervalVector &b) const
	Returns the dimension of the box \([\mathbf{b}]\).

bool	non_singular_jacobian (const std::function< IntervalMatrix(const IntervalVector &)> &Jf, float precision)
	Tests whether the Jacobian is non-singular or not.

Protected Attributes
std::vector< const Paving * >	m_v_subset_items
	set of leaves items

Protected Attributes inherited from codac::Set
SetValue	m_value
	integer value of this set

IntervalVector	m_box
	box representing this set

Basics
	ConnectedSubset (const std::vector< const Paving * > &v_subset_items)
	Creates a connected subset.

	~ConnectedSubset ()
	ConnectedSubset destructor.

bool	is_strictly_included_in_paving () const
	Tests if this subset is strictly included in its paving structure.

bool	contains (const Vector &p) const
	Tests if p is contained in the connected subset.

const Paving *	get_paving () const
	Returns a const pointer to the paving structure.

const std::vector< const Paving * > &	get_items () const
	Returns the set of Paving leaves this subset is made of.

std::vector< IntervalVector >	get_boxes () const
	Returns the set of Paving boxes this subset is made of.

std::vector< IntervalVector >	get_boundary (SetValue value_boundary=SetValue::UNKNOWN, SetValue value_out=SetValue::OUT) const
	Returns the boundary boxes of this subset.

static const std::vector< IntervalVector >	get_boxed_hulls (const std::vector< ConnectedSubset > v_subsets)
	Returns the boxed hull of each connected subset into a vector of boxes.

Detailed Description

Multi-dimensional paving representation of a connected subset.

A connected subset is a topological space that cannot be represented as the union of two or more disjoint non-empty open subsets.

This object gathers a set of Paving leaves items that represent a subset of a paving structure.

Constructor & Destructor Documentation

◆ ConnectedSubset()

codac::ConnectedSubset::ConnectedSubset ( const std::vector< const Paving * > & v_subset_items )

Creates a connected subset.

Parameters

v_subset_items set of Paving leaves this object will be made of

Member Function Documentation

◆ is_strictly_included_in_paving()

bool codac::ConnectedSubset::is_strictly_included_in_paving ( ) const

Tests if this subset is strictly included in its paving structure.

Returns: true in case of strict inclusion

◆ contains()

bool codac::ConnectedSubset::contains ( const Vector & p ) const

Tests if p is contained in the connected subset.

Parameters

p	vector to be tested

Returns: true if p is inside this

◆ get_paving()

const Paving * codac::ConnectedSubset::get_paving ( ) const

Returns a const pointer to the paving structure.

Returns: a const pointer to the Paving object

◆ get_items()

const std::vector< const Paving * > & codac::ConnectedSubset::get_items ( ) const

Returns the set of Paving leaves this subset is made of.

Returns: a vector of Paving leaves items

◆ get_boxes()

std::vector< IntervalVector > codac::ConnectedSubset::get_boxes ( ) const

Returns the set of Paving boxes this subset is made of.

Returns: a vector of boxes

◆ get_boundary()

std::vector< IntervalVector > codac::ConnectedSubset::get_boundary	(	SetValue	value_boundary = SetValue::UNKNOWN,
		SetValue	value_out = SetValue::OUT ) const

Returns the boundary boxes of this subset.

Note that the returned boxes are degenerated as they represent subpaving's edges.

Parameters

value_boundary	value of the items representing the boundary of the subset
value_out	value of the items representing no-solution boxes in the paving

Returns: a vector of boxes

◆ get_boxed_hulls()

static const std::vector< IntervalVector > codac::ConnectedSubset::get_boxed_hulls ( const std::vector< ConnectedSubset > v_subsets )

static

Returns the boxed hull of each connected subset into a vector of boxes.

Parameters

v_subsets vector of connected subsets

Returns: a vector of boxes

◆ zero_proven()

bool codac::ConnectedSubset::zero_proven ( const std::function< IntervalVector(const IntervalVector &)> & f )

Tests if an unknown function \(\mathbf{f}^*\) enclosed by \([\mathbf{f}]\) vanishes at least once on this subset.

This method stands on topological degree computations. This has been the object of the publication:

Proving the existence of loops in robot trajectories
S. Rohou, P. Franek, C. Aubry, L. Jaulin
The International Journal of Robotics Research, 2018

Note: If this method returns false, it does not mean a zero cannot exist on this subset. It only corresponds to a case of undecidability.

Parameters

f	the inclusion function \([\mathbf{f}]:\mathbb{IR}^2\to\mathbb{IR}^2\)

Returns: true in case of at least one zero proven on this subset, false in case of undecidability

◆ zeros_number()

int codac::ConnectedSubset::zeros_number	(	const std::function< IntervalVector(const IntervalVector &)> &	f,
		const std::function< IntervalMatrix(const IntervalVector &)> &	Jf,
		float	precision )

Counts the number of zeros of an uncertain function \(\mathbf{f}^*\) enclosed by \([\mathbf{f}]\) on this subset.

This method stands on topological degree computations. This has been the object of the publication:

Proving the existence of loops in robot trajectories
S. Rohou, P. Franek, C. Aubry, L. Jaulin
The International Journal of Robotics Research, 2018

Parameters

f	the inclusion function \([\mathbf{f}]:\mathbb{IR}^2\to\mathbb{IR}^2\)
Jf	Jacobian matrix \([\mathbf{J_f}]\) of the unknown function \(\mathbf{f}^*\)
precision	The subset may be made of wide boxes \([\mathbf{t}]_k\) that will result in an over-approximation of the \([\mathbf{J_f}]([\mathbf{t}]_k)\). A bisection of the \([\mathbf{t}]_k\) may be applied on order to deal with smaller boxes, thus reducing the pessimism of the Jacobian evaluation and thus the chances of concluding about the number of zeros. This parameter is the precision limit of this auto-refinement.

Returns: the number of zeros, or -1 in case of undecidability

◆ topological_degree()

int codac::ConnectedSubset::topological_degree ( const std::function< IntervalVector(const IntervalVector &)> & f )

protected

Computes the topological degree related to \(\mathbf{f}\).

Parameters

f	the inclusion function \([\mathbf{f}]:\mathbb{IR}^2\to\mathbb{IR}^2\)

Returns: degree number

◆ all_positive_signs()

bool codac::ConnectedSubset::all_positive_signs ( const std::vector< int > & v_s ) const

protected

Returns true if all items in v_s are positive.

Parameters

v_s	vector of integers

Returns: true if all positive

◆ orientation()

int codac::ConnectedSubset::orientation	(	const IntervalVector &	b,
		const IntervalVector &	parent_coface,
		int	orientation ) const

protected

Returns orientation of vector b.

Parameters

b
parent_coface
orientation

Returns: orientation integer

◆ compute_local_degree()

int codac::ConnectedSubset::compute_local_degree	(	const std::function< IntervalVector(const IntervalVector &)> &	f,
		const IntervalVector &	b,
		const IntervalVector &	common_cocoface ) const

protected

Computes local degree related to \(\mathbf{f}\).

Parameters

f	the inclusion function \([\mathbf{f}]:\mathbb{IR}^2\to\mathbb{IR}^2\)
b
common_cocoface

Returns: local degree number

◆ sign_vector()

std::vector< int > codac::ConnectedSubset::sign_vector	(	const std::function< IntervalVector(const IntervalVector &)> &	f,
		const IntervalVector &	b,
		const IntervalVector &	common_cocoface ) const

protected

Returns a vector of signs represented as integers.

Parameters

f
b
common_cocoface

Returns: vector of integers

◆ get_cofaces() [1/2]

std::vector< IntervalVector > codac::ConnectedSubset::get_cofaces ( const IntervalVector & b ) const

protected

Returns a vector of cofaces related to \([\mathbf{b}]\).

Parameters

b

Returns: vector of cofaces boxes

◆ get_cofaces() [2/2]

std::vector< IntervalVector > codac::ConnectedSubset::get_cofaces	(	const IntervalVector &	b,
		const IntervalVector &	common_cocoface ) const

protected

Returns a vector of cofaces related to \([\mathbf{b}]\), common_cocoface.

Parameters

b
common_cocoface

Returns: vector of cofaces boxes

◆ box_dimension()

int codac::ConnectedSubset::box_dimension ( const IntervalVector & b ) const

protected

Returns the dimension of the box \([\mathbf{b}]\).

Parameters

b

Returns: integer dimension

◆ non_singular_jacobian()

bool codac::ConnectedSubset::non_singular_jacobian	(	const std::function< IntervalMatrix(const IntervalVector &)> &	Jf,
		float	precision )

protected

Tests whether the Jacobian is non-singular or not.

Parameters

Jf	Jacobian matrix function
precision	of the bisected method used in case of ambiguity on the already existing paving structure

Returns: true if the Jacobian is non-singular

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

/home/simon/codac/src/core/paving/codac_ConnectedSubset.h

Public Member Functions

Protected Member Functions

Protected Attributes

Basics

Detailed Description

Constructor & Destructor Documentation

◆ ConnectedSubset()

Member Function Documentation

◆ is_strictly_included_in_paving()

◆ contains()

◆ get_paving()

◆ get_items()

◆ get_boxes()

◆ get_boundary()

◆ get_boxed_hulls()

◆ zero_proven()

◆ zeros_number()

◆ topological_degree()

◆ all_positive_signs()

◆ orientation()

◆ compute_local_degree()

◆ sign_vector()

◆ get_cofaces() [1/2]

◆ get_cofaces() [2/2]

◆ box_dimension()

◆ non_singular_jacobian()