Detailed Description

Implements the functions for the polytope defined in a chart (i.e., in the tangent space to a variety defined on a given point).

See Also: Tscpolytope,scpolytope.h

Definition in file scpolytope.c.

Functions
void	InitEmptySPolytope (double delta, unsigned int k, double r, double sr, Tscpolytope *mp)
	Defines an empty chart simplieifed polytope. More...

void	DefineSPolytope (Tscpolytope *mp)
	Initial definition of the simple polytope bounding the local chart. More...

void	CopySPolytope (Tscpolytope mp_dst, Tscpolytope mp_src)
	Copies the simplified polytope from one chart to another. More...

boolean	InsideSPolytope (double t, Tscpolytope mp)
	Identifies points inside a chart simple polytope. More...

unsigned int	DetermineSPolytopeNeighbour (double epsilon, double t, Tscpolytope mp)
	Identifes the neighbour containing a given point. More...

void	EnlargeSPolytope (double t, Tscpolytope mp)
	Ensures that a polytompe includes a given point. More...

void	CutSPolytope (double t, double r, unsigned int id, Tscpolytope mp)
	Crops the polytope bounding chart with a plane. More...

void	CutSPolytopeWithFace (double t, double offset, unsigned int id, Tscpolytope mp)
	Cuts a simple polytope with a given plane. More...

double	GetSPolytopeRadius (Tscpolytope *mp)
	Returns the simple polytope radius. More...

double	GetSPolytopeBoxSide (Tscpolytope *mp)
	Returns the size of the box side. More...

unsigned int	GetSPolytopeDim (Tscpolytope *mp)
	Returns the simple polytope dimensionality. More...

unsigned int	GetSPolytopeNFaces (Tscpolytope *mp)
	Number of faces of a simple chart polytope. More...

void	GetSPolytopeFace (unsigned int n, double f, Tscpolytope mp)
	Gets a face. More...

boolean	SPolytopeRandomPointOnBoundary (double rSample, double t, Tscpolytope mp)
	Random point on the boundary of the chart. More...

boolean	RandomPointInSPolytope (double scale, double t, Tscpolytope mp)
	Random point on the polytope with uniform distribution. More...

double	SPolytopeGetSamplingRadius (Tscpolytope *mp)
	Returns the current sampling radius. More...

void	SPolytopeIncreaseSamplingRadius (Tscpolytope *mp)
	Increases the sampling radius. More...

void	SPolytopeDecreaseSamplingRadius (Tscpolytope *mp)
	Decreases the sampling radious. More...

double	SPolytopeMaxVolume (Tscpolytope *mp)
	Maximum volume of the simple polytope. More...

double	SPolytopeVolume (Tscpolytope *mp)
	Volume of the simple polytope. More...

unsigned int	SPolytopeNumNeighbours (Tscpolytope *mp)
	Number of neighbours of the simple polytope. More...

unsigned int	SPolytopeNeighbourID (unsigned int n, Tscpolytope *mp)
	Returns the identifier of one of the neighbours of a polytope. More...

unsigned int	SPolytopeMemSize (Tscpolytope *mp)
	Computes the memory used by the polytope. More...

void	SaveSPolytope (FILE f, Tscpolytope mp)
	Saves the chart polytope to a file. More...

void	LoadSPolytope (FILE f, Tscpolytope mp)
	Reads the chart polytope from a file. More...

void	DeleteSPolytope (Tscpolytope *mp)
	Deletes the structure allocated by DefineSPolytope. More...

Function Documentation

void InitEmptySPolytope	(	double	delta,
		unsigned int	k,
		double	r,
		double	sr,
		Tscpolytope *	mp
	)

Defines an empty chart simplified polytope.

Parameters

delta	Distance between two samples. We must ensure outher ball larger than this so that new samples can eventually trigger the generation of new charts.
k	Dimensinality of the space where to define the polytope.
r	Radius of the ball to be enclosed by the polytope.
sr	Sampling radius.
mp	The simple polytope to initialize.

See Also: InitEmptyCharPolytope.

Definition at line 21 of file scpolytope.c.

References Tscpolytope::face, Tscpolytope::ID, Tscpolytope::k, Tscpolytope::lsr, Tscpolytope::maxFaces, Tscpolytope::msr, Tscpolytope::nFaces, Tscpolytope::r, SPolytopeMaxVolume(), Tscpolytope::sr, and Tscpolytope::v.

Referenced by InitChartInt(), and Polytope2SPolytope().

void DefineSPolytope ( Tscpolytope * mp )

Defines a box.

Parameters

mp	The polytope to initialize.

See Also: DefineChartPolytope.

Definition at line 43 of file scpolytope.c.

References Tscpolytope::face, Tscpolytope::ID, INIT_NUM_FACES, Tscpolytope::maxFaces, and NEW.

Referenced by CutSPolytopeWithFace(), and Polytope2SPolytope().

void CopySPolytope	(	Tscpolytope *	mp_dst,
		Tscpolytope *	mp_src
	)

Copies the data defining the simple polytope from one chart to another.

Parameters

mp_dst	The simple polytope where to copy the information.
mp_src	The simple polytope from where to copy the information.

See Also: CopyChartPolytope.

Definition at line 54 of file scpolytope.c.

References Tscpolytope::face, Tscpolytope::ID, Tscpolytope::k, Tscpolytope::lsr, Tscpolytope::maxFaces, Tscpolytope::msr, NEW, Tscpolytope::nFaces, Tscpolytope::r, Tscpolytope::sr, and Tscpolytope::v.

Referenced by CopyChart().

boolean InsideSPolytope	(	double *	t,
		Tscpolytope *	mp
	)

Decides wheter or not a point in inside the simple polytope bounding a chart.

Parameters

t	The point.
mp	The polytope.

Returns: TRUE point t is inside the simple polytope of chart mp.

See Also: InsidePolytope.

Definition at line 88 of file scpolytope.c.

References Tscpolytope::face, GeneralDotProduct(), Tscpolytope::k, Tscpolytope::msr, and Norm().

Referenced by DetermineSPolytopeNeighbour(), InsideChartPolytope(), RandomPointInSPolytope(), SPolytopeRandomPointOnBoundary(), and SPolytopeVolume().

unsigned int DetermineSPolytopeNeighbour	(	double	epsilon,
		double *	t,
		Tscpolytope *	mp
	)

This function returns the neighbouring chart including a point in the polytope radious but outside the polytope.

For points outside the chart ball or inside the polytope this function returns NO_UINT.

Parameters

epsilon	Numerical accuracy.
t	The point.
mp	The poytope.

Definition at line 105 of file scpolytope.c.

References Tscpolytope::face, FALSE, GeneralDotProduct(), Tscpolytope::ID, InsideSPolytope(), Tscpolytope::k, NEW, Tscpolytope::nFaces, NO_UINT, Norm(), Tscpolytope::r, and ScaleVector().

Referenced by DetermineChartNeighbour().

void EnlargeSPolytope	(	double *	t,
		Tscpolytope *	mp
	)

Ensures that a polytope includes a given point possibly modifying the faces.

Parameters

t	The point.
mp	The polytope.

Definition at line 170 of file scpolytope.c.

References Tscpolytope::face, GeneralDotProduct(), Tscpolytope::k, Tscpolytope::nFaces, and Tscpolytope::v.

Referenced by EnlargeChart().

void CutSPolytope	(	double *	t,
		double	r,
		unsigned int	id,
		Tscpolytope *	mp
	)

Reduces a polytope bounding chart cropping it with a plane defined by the intersection of the chart ball with a ball centered at t with radious r. This ball is an approximation in the chart plane of the ball bounding another chart.

Parameters

t	Center of the new ball.
r	Radius of the new ball. This is typically the same as the ball for the current polytope.
id	Identifier of the chart generating the cut. This is used to update the list of neighbours.
mp	The chart with the polytope to crop.

See Also: CutPolytope.

Definition at line 186 of file scpolytope.c.

References CutSPolytopeWithFace(), Tscpolytope::k, Norm(), and Tscpolytope::r.

Referenced by ForceChartCut(), and IntersectChartsInt().

void CutSPolytopeWithFace	(	double *	t,
		double	offset,
		unsigned int	id,
		Tscpolytope *	mp
	)

This is the generic function cutting a simple polytope by a plane that can come from the intersection of two balls or from anywhere else.

The plane is given in the form

$offset+\sum_{i=1}^{k} x_i t_i \leq 0$

where the $ t_i $ are given in t, the $ x_i $ are the variables in the tangent space, and $ k $ is the dimension of this space.

We simply add the face to the set of faces implicitly defining the polytope.

Parameters

t	Parameters of the plane.
offset	Offset of the plane.
id	Identifier of the chart generating the cut. This is used to update the list of neighbours.
mp	The chart with the polytope to crop.

See Also: CutPolytopeWithFace.

Definition at line 199 of file scpolytope.c.

References DefineSPolytope(), Tscpolytope::face, Tscpolytope::ID, Tscpolytope::k, Tscpolytope::maxFaces, MEM_DUP, MEM_EXPAND, NEW, Tscpolytope::nFaces, NO_UINT, and Tscpolytope::v.

Referenced by AddBorderConstraint(), CutSPolytope(), and Polytope2SPolytope().

double GetSPolytopeRadius ( Tscpolytope * mp )

Returns the radious of the ball included in the initial polytope.

Parameters

mp	The simple polytope to query.

Returns: The radius.

Definition at line 229 of file scpolytope.c.

References Tscpolytope::r.

double GetSPolytopeBoxSide ( Tscpolytope * mp )

Simple convex polytopes have an enclosing ball. This function returns the side of a box fully enclosing ths enclosing ball. This is basically used for plotting purposes.

Todo:: Frontier charts should be represented by balls and not by boxes.

Parameters

mp	The simple polytope to query.

Returns: The box side.

Definition at line 234 of file scpolytope.c.

References Tscpolytope::sr.

unsigned int GetSPolytopeDim ( Tscpolytope * mp )

Returns the dimensionality of the space where the simple polytope is defined.

Parameters

mp	The simple polytope to query.

Returns: The dimensionality.

Definition at line 239 of file scpolytope.c.

References Tscpolytope::k.

Referenced by SPolytope2Polytope().

unsigned int GetSPolytopeNFaces ( Tscpolytope * mp )

Returns the number of faces of a simple chart polytope.

Parameters

mp	The simple polytope to query.

Returns: The number of faces.

Definition at line 244 of file scpolytope.c.

References Tscpolytope::nFaces.

Referenced by SPolytope2Polytope().

void GetSPolytopeFace	(	unsigned int	n,
		double *	f,
		Tscpolytope *	mp
	)

Returns the coeficients defining the face for a simple polytope associated to a chart.

If n is above the number of faces of the polytope, nothing is changed in f.

Parameters

n	The face number.
f	Space where to store the face coefients (including the offest). It must have k+1 entries and must be allocated externally.
mp	The simple polytope to query.

Definition at line 249 of file scpolytope.c.

References Tscpolytope::face, and Tscpolytope::k.

Referenced by SPolytope2Polytope().

boolean SPolytopeRandomPointOnBoundary	(	double	rSample,
		double *	t,
		Tscpolytope *	mp
	)

Returns a random point uniformly distributed in the boundary of the hypersphere defined in the tangent space.

After sampling the point we check if it is actually inside the polytope.

Charts that are basically sorounded by neighbours and only have a small portion of its ball in the border or expansion of the manifold could be arbitrarily hard to sample.

Parameters

rSample	Radious to use in the sampling. This is typically the radius of the ball initially inside the polytope but it can be smaller if many attempts to sample points fail.
t	The output point on the chart ball boundary (if any)
mp	The polytope to sample.

Returns: TRUE if the sampled point is actually on the boundary of the atlas.

Definition at line 255 of file scpolytope.c.

References InsideSPolytope(), Tscpolytope::k, and randomOnBall().

Referenced by RandomPointOnBoundary().

boolean RandomPointInSPolytope	(	double	scale,
		double *	t,
		Tscpolytope *	mp
	)

Drawns a random point inside the polytope with uniform distribution. Rejection sampling is used so for some degenerate polytopes it can take long.

Parameters

scale	Scale factor for the sampling area.
t	The array where to store the sample (must be allocated externally).
mp	The polytope to sample.

Returns: TRUE if we could actually sample inside the simple polytope.

See Also: RandomPointInPolytope.

Definition at line 262 of file scpolytope.c.

References InsideSPolytope(), Tscpolytope::k, Tscpolytope::lsr, Tscpolytope::msr, Tscpolytope::nFaces, randomInBall(), Tscpolytope::sr, and TRUE.

Referenced by ChartVolume(), and RandomPointInChart().

double SPolytopeGetSamplingRadius ( Tscpolytope * mp )

Returns the current sampling radius.

Parameters

mp	The simple polytope to query.

Returns: The sampling radius.

Definition at line 281 of file scpolytope.c.

References Tscpolytope::sr.

Referenced by GetChartSamplingRadius().

void SPolytopeIncreaseSamplingRadius ( Tscpolytope * mp )

Increases the sampling radius after a succesful sampling or a succesful branch extension. The aim here is to try to reach further, if possible.

When extending the sampling radious we keep track of the maximum sampling radius ever. All samples belonging to the polytope can not be further than this maximum from the center.

Parameters

mp	The simple polytope to adjust.

Definition at line 286 of file scpolytope.c.

References MOV_AVG_UP, Tscpolytope::msr, and Tscpolytope::sr.

Referenced by IncreaseChartSamplingRadius().

void SPolytopeDecreaseSamplingRadius ( Tscpolytope * mp )

Decreases the sampling radious after an unsuceessful sampling or a collisiong when trying the create a new branch.

When decresing the sampling radius we take care of not reducing it below a given threshold so that it is always significantly larger than the radius r.

Definition at line 295 of file scpolytope.c.

References Tscpolytope::lsr, MOV_AVG_DOWN, and Tscpolytope::sr.

Referenced by DecreaseChartSamplingRadius().

double SPolytopeMaxVolume ( Tscpolytope * mp )

Upper bound of the volume of the polytope.

This is basically the area that RandomPointInSPolytope uses to drawn random samples.

Parameters

mp	The polytope to measure.

Returns: The polytope maximum volume.

Definition at line 304 of file scpolytope.c.

References BallVolume(), Tscpolytope::k, and Tscpolytope::sr.

Referenced by ChartVolume(), and InitEmptySPolytope().

double SPolytopeVolume ( Tscpolytope * mp )

Volume of the simple polytope considering the neighbouring relations (i.e., initial volume or maximum volume)

Parameters

mp	The polytope to measure.

Returns: The polytope volume.

Definition at line 309 of file scpolytope.c.

References BallVolume(), InsideSPolytope(), Tscpolytope::k, NEW, randomInBall(), Tscpolytope::sr, and Tscpolytope::v.

Referenced by ChartMaxVolume().

unsigned int SPolytopeNumNeighbours ( Tscpolytope * mp )

Returns the number of neighbours of a polytope. Note that a simple polytope can consider as neighbours charts that where neighbours but are not neighbours any more.

Parameters

mp	The simple polytope to query.

Returns: The numbe of neighbours of the simple polytope.

See Also: PolytopeNumNeighbours.

Definition at line 332 of file scpolytope.c.

References Tscpolytope::nFaces.

Referenced by ChartNumNeighbours().

unsigned int SPolytopeNeighbourID	(	unsigned int	n,
		Tscpolytope *	mp
	)

Returns the identifier of one of the neighbours of a polytope. Note that a simple polytope can consider as neighbours charts that where neighbours but are not neighbours any more.

Parameters

n	The number of neighbour to query (numbered from 0).
mp	The chart to query.

Returns: The neighbour identifer. NO_UINT if i is larger thatn the actual number of neighbours of the polytope.

See Also: PolytopeNeighbourID.

Definition at line 337 of file scpolytope.c.

References Tscpolytope::ID, and NO_UINT.

Referenced by ChartNeighbourID(), and SPolytope2Polytope().

unsigned int SPolytopeMemSize ( Tscpolytope * mp )

Computes the approximated memory used by the polytope (in bytes).

Parameters

mp	The polytope.

Returns: The number of bytes used.

Definition at line 345 of file scpolytope.c.

References Tscpolytope::k, and Tscpolytope::nFaces.

Referenced by ChartMemSize().

void SaveSPolytope	(	FILE *	f,
		Tscpolytope *	mp
	)

Saves the information about the chart simple polytope (if any) to a given file.

Parameters

f	The file where to store the polytope information.
mp	The chart with the polytope to save.

See Also: SaveChartPolytope.

Definition at line 355 of file scpolytope.c.

References Tscpolytope::face, Tscpolytope::ID, Tscpolytope::k, Tscpolytope::lsr, Tscpolytope::maxFaces, Tscpolytope::msr, Tscpolytope::nFaces, Tscpolytope::r, Tscpolytope::sr, and Tscpolytope::v.

Referenced by SaveChart().

void LoadSPolytope	(	FILE *	f,
		Tscpolytope *	mp
	)

Initializes the information about the chart polytope (if any) from a given file.

Parameters

f	The file from where to read the polytope information.
mp	The chart with the polytope to initialize.

See Also: LoadChartPolytope.

Definition at line 381 of file scpolytope.c.

References Tscpolytope::face, Tscpolytope::ID, Tscpolytope::k, Tscpolytope::lsr, Tscpolytope::maxFaces, Tscpolytope::msr, NEW, Tscpolytope::nFaces, Tscpolytope::r, Tscpolytope::sr, and Tscpolytope::v.

Referenced by LoadChart().

void DeleteSPolytope ( Tscpolytope * mp )

Deletes the structure allocated by DefineSPolytope.

Parameters

mp	The polytope to free.

See Also: DeleteChartPolytope.

Definition at line 415 of file scpolytope.c.

References Tscpolytope::face, Tscpolytope::ID, Tscpolytope::maxFaces, and Tscpolytope::nFaces.

Referenced by DeleteChart().

Institut de Robòtica i Informàtica Industrial

Detailed Description

Functions

Function Documentation

Institut de Robòtica
i Informàtica Industrial