scpolytope.h File Reference

Detailed Description

Simplified version of a polytope associated with a chart. To see the full version check cpolytope.h.

See Also
Tscpolytope,scpolytope.c

Definition in file scpolytope.h.

Data Structures

struct  Tscpolytope
 A simpleifed polytope associated with chart on a manifold. More...
 

Macros

#define ADJUST_SR   0
 Set this to one if the sampling radius for each polytope has to be self-adjusted. More...
 
#define INIT_NUM_FACES   10
 Initial space for faces. More...
 

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...
 
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...
 
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...
 
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...
 

Macro Definition Documentation

#define ADJUST_SR   0

The sampling radius for each chart polytope be adjusted taking into account the acceptance/rejection when sampling on each polytope. In this way the sampling area is adjusted to the actual span of the polytope and the rejection is reduced.

The effect of this adjustment is probably minor, especially for problems that are solved fast (i.e., problems where few samples are drawn from each chart).

The ratio at which the sampling radius is adjusted is defined in MOV_AVG_UP and MOV_AVG_DOWN.

Definition at line 31 of file scpolytope.h.

Referenced by main().

#define INIT_NUM_FACES   10

Initial space for faces. Extended as much as necessary.

Definition at line 38 of file scpolytope.h.

Referenced by DefineSPolytope().

Function Documentation

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

Defines an empty chart simplified polytope.

Parameters
deltaDistance between two samples. We must ensure outher ball larger than this so that new samples can eventually trigger the generation of new charts.
kDimensinality of the space where to define the polytope.
rRadius of the ball to be enclosed by the polytope.
srSampling radius.
mpThe 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
mpThe 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_dstThe simple polytope where to copy the information.
mp_srcThe 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().

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
tCenter of the new ball.
rRadius of the new ball. This is typically the same as the ball for the current polytope.
idIdentifier of the chart generating the cut. This is used to update the list of neighbours.
mpThe 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
tParameters of the plane.
offsetOffset of the plane.
idIdentifier of the chart generating the cut. This is used to update the list of neighbours.
mpThe 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().

boolean InsideSPolytope ( double *  t,
Tscpolytope mp 
)

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

Parameters
tThe point.
mpThe 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
epsilonNumerical accuracy.
tThe point.
mpThe 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
tThe point.
mpThe polytope.

Definition at line 170 of file scpolytope.c.

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

Referenced by EnlargeChart().

double GetSPolytopeRadius ( Tscpolytope mp)

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

Parameters
mpThe 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
mpThe 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
mpThe 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
mpThe 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
nThe face number.
fSpace where to store the face coefients (including the offest). It must have k+1 entries and must be allocated externally.
mpThe 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
rSampleRadious 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.
tThe output point on the chart ball boundary (if any)
mpThe 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
scaleScale factor for the sampling area.
tThe array where to store the sample (must be allocated externally).
mpThe 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
mpThe 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
mpThe 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
mpThe 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
mpThe 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
mpThe 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
nThe number of neighbour to query (numbered from 0).
mpThe 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
mpThe 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
fThe file where to store the polytope information.
mpThe 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
fThe file from where to read the polytope information.
mpThe 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
mpThe 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().