cp.c File Reference

Detailed Description

Implementation of the functions dealing with critial points, i.e., recursion points for the silhouette algorithm.

See Also

cp.h, Tcp.

Definition in file cp.c.

Functions
void	GetSCpSystem (boolean silhouette, Tparameters *p, double **planes, Tcp *cp, TCuikSystem *cs, boolean **originalSystemVars, TCuikSystem *csR)
	Generates a cuiksystem whose solution is a silhouette or a set of critical points. More...
void	GenerateProjectionPlanes (Tparameters *p, unsigned int n, unsigned int dim, unsigned int m, double **v)
	Generates n orthonormals planes. More...
void	NewCP (unsigned int l, Tbox *b, Tcp *cp)
	Constructor. More...
unsigned int	GetCPlevel (Tcp *cp)
	Gets the creation level of a critical point. More...
Tbox *	GetCPFixedRanges (Tcp *cp)
	Gets the collection of fixed ranges for a critical point. More...
void	DealWithCP (FILE *f_out, unsigned int n, Tparameters *p, TCuikSystem *cs, Tlist *cps, Tcp *cp)
	Processes a critical point. More...
void	DeleteCP (Tcp *cp)
	Destructor. More...

Function Documentation

void GetSCpSystem	(	boolean	silhouette,
		Tparameters *	p,
		double **	planes,
		Tcp *	cp,
		TCuikSystem *	cs,
		boolean **	originalSystemVars,
		TCuikSystem *	csR
	)

Generates a cuiksystem whose solution is a silhouette or a set of critical points. The cuiksystem is generated form an extended Jacobian of the original cuiksystem. The extended comes from the fact that we add the projection planes to the system Jacobian. The silhouette/critical points are the points where this extended Jacobian is not full rank. To identify these points, we generate a system with the linear combinations of the equations in the Jacobian and we search from points where this linear combination is zero (excluding the trivial solution by imposing the norm of the scale factor of the linear combinations to be 1).

Parameters

silhouette	TRUE if we have to generate a system to determine a silhouette and FALSE to generate a system to isolate critical points.
p	A set of parameters
planes	Two arrays of doubles with one entry for each variables in the system defining the projection planes in which the silhouette or the critical points are defined. When parameter silhouette is FALSE only one plane is used.
cp	The that triggered the generation of the system.
cs	The original cuiksystem.
originalSystemVars	An array of flags with as many entries as the number of variables in the output cuiksystem (csR) with entries to TRUE only for the system variables in the original cuiksystem (cs parameter).
csR	The output cuiksystem.

Definition at line 84 of file cp.c.

References AccumulateEquations(), AddCt2Monomial(), AddEquation2CS(), AddMonomial(), AddVariable2CS(), AddVariable2Monomial(), CopyCuikSystem(), CopyEquation(), CT_N_DOF, DeleteEquation(), DeleteJacobian(), DeleteMonomial(), DeleteVariable(), EQU, Error(), FALSE, Tcp::fixedRanges, GenerateGeneralNormEquation(), GetBoxInterval(), GetCSJacobian(), GetCSNumEquations(), GetCSNumVariables(), GetCSSystemVars(), GetJacobianEquation(), GetParameter(), INF, InitEquation(), InitMonomial(), Tcp::level, NEW, NewInterval(), NewVariable(), NFUN, SetCSVariableRange(), SetEquationCmp(), SetEquationType(), SetVariableInterval(), SYSTEM_EQ, SYSTEM_VAR, and VarScaleEquation().

Referenced by DealWithCP().

void GenerateProjectionPlanes	(	Tparameters *	p,
		unsigned int	n,
		unsigned int	dim,
		unsigned int	m,
		double **	v
	)

Generates n orthonormals planes in a space of dimension dim that we use for projection.

m is level at which these planes are fixed: values up to m are zero in the output vectors.

Parameters

p	A set of parameters.
n	The number of planes to generate
dim	The number variables in the original cuiksystem.
m	The number of variables already fixed.
v	Room for the vectors.

Definition at line 215 of file cp.c.

References randomDouble().

Referenced by DealWithCP().

void NewCP	(	unsigned int	l,
		Tbox *	b,
		Tcp *	cp
	)

Defines a new critical point.

Parameters

l	The recursion level at which the critical point is created.
b	The box with the already fixed ranges
cp	The Tcp structure to create.

Definition at line 278 of file cp.c.

References CopyBox(), Tcp::fixedRanges, GetBoxInterval(), IntervalCenter(), Tcp::level, and NewInterval().

Referenced by DealWithCP(), and main().

unsigned int GetCPlevel

(

Tcp *

cp

)

Gets the creation level of a critical point.

Parameters

cp	The critical point to query.

Returns

The recursion level at which the critical point was created.

Definition at line 299 of file cp.c.

References Tcp::level.

Tbox* GetCPFixedRanges

(

Tcp *

cp

)

Gets the collection of fixed ranges for a critical point.

Returns

A box with the fixed ranges to create the critical point.

Definition at line 304 of file cp.c.

References Tcp::fixedRanges.

void DealWithCP	(	FILE *	f_out,
		unsigned int	n,
		Tparameters *	p,
		TCuikSystem *	cs,
		Tlist *	cps,
		Tcp *	cp
	)

A critical point is a recursion point for the silhouette algorithm, i.e., a point where the range for one variable is fixed and the silhouette algorithms is launched in a sub-space with one degree of freedom less than the original space

The process of the critical point is the following

• Given the ranges fixed and not fixed stored in the Tcp structure, we generate a TCuikSystem whose solution is a silhouette traced at this critical point.
• We solve the TCuikSystem and add the resulting silhouette to the solution file f_out. Boxes in this file corresponding to a given silhouette are identified with a prefix in the for "SL n" with n the number of the silhouette.
• If the resulting silhouette is just a point, we are in the end case of the recursion and nothing else need to be done.
• If the resulting silhouette is a proper one-dimensional curbe, we generate a TCuikSystem whose solutions are critical points on the silhouette previously defined.
• We solve the TCuikSystem to get the new critical points.
• For each one of the solutions, we store them in the output file (f_out) and we generate a Tcp structure and we add it to the list of critical points pending to be processed (cps).

This is just a brute-force approach to the silhouette algorithm and the result is not very efficient. Many refinements are possible to speed up the execution. We will introduce them as time is available, but this is not a priority right now.

Parameters

f_out	File where to store the silhouettes and critical points.
n
p	The set of parameters to use when solving the cuiksystem generated in this function.
cs	The cuiksystem whose solution space we want to characterize using the silhouette algorithm.
cps	The list of critical points pending to be processed.
cp	The critical point to be processed (typically extracted from cps by the caller)

Definition at line 309 of file cp.c.

References AddLastElement(), Advance(), ChangeParameter(), CT_N_DOF, CT_N_SOLUTIONS, DeleteCuikSystem(), DeleteListOfBoxes(), EndOfList(), FALSE, First(), GenerateProjectionPlanes(), GetCSNumVariables(), GetCurrent(), GetParameter(), GetSCpSystem(), InitIterator(), InitListOfBoxes(), Tcp::level, ListOfBoxesCluster(), NEW, NewCP(), PrintCuikSystemWithSimplification(), PrintListOfBoxes(), SolveCuikSystem(), and TRUE.

Referenced by main().

void DeleteCP

(

Tcp *

cp

)

Deletes the information stored in the critical point and frees the allocated memory space.

Definition at line 388 of file cp.c.

References DeleteBox(), and Tcp::fixedRanges.

Referenced by main().