CGAL 4.7  Kinetic Framework

The concept Kinetic::FunctionKernel
encapsulates all the methods for representing and handing functions. The set is kept deliberately small to easy use of new Kinetic::FunctionKernel
s, but together these operations are sufficient to allow the correct processing of events, handling of degeneracies, usage of static data structures, runtime error checking as well as runtime verification of the correctness of kinetic data structures. The computation of a polynomial with the variable negated is used for reversing time in kinetic data structures and can be omitted if that capability is not needed.
POLYNOMIAL::Kernel<RootStack>
POLYNOMIAL::Filtered_kernel<RootStack>
Kinetic::RootEnumerator
Example
We provide several models of the concept, which are not documented separately. The models of Kinetic::SimulationTraits
all choose appropriate models. However, if more control is desired, we here provide examples of how to create the various supported Kinetic::FunctionKernel
.
A Sturm sequence based kernel which supports exact comparisons of roots of polynomials (certificate failure times):
A wrapper for CORE::Expr
which implements the necessary operations:
A function kernel which computes approximations to the roots of the polynomials:
When using the function kernel in kinetic data structures, especially one that is in exact, it is useful to wrap the root stack. The wrapper checks the sign of the certificate function being solved and uses that to handle degeneracies. This is done by, for the inexact solvers
and for exact solvers
For exact computations, the primary representation for roots is the now standard choice of a polynomial with an associated isolating interval (and interval containing exactly one distinct root of a polynomial) along with whether the root has odd or even multiplicity and, if needed, the Sturm sequence of the polynomial. Two intervals can be compared by first seeing if the isolating intervals are disjoint. If they are, then we know the ordering of the respective roots. If not we can subdivide each of the intervals (using the endpoints of the other interval) and repeat. In order to avoid subdividing endlessly when comparing equal roots, once we subdivide a constant number of times, we use the Sturm sequence of \( p\) and \( p'q\) (where \( p\) and \( q\) are the two polynomials and \( p'\) is the derivative of \( p\)) to evaluate the sign of the second at the root of the first one directly (note that this Sturm sequence is applied to a common isolating interval of the roots of interest of both polynomials).
Concepts  
concept  ConstructFunction 
The concept ConstructFunction is used to construct functions. More...  
concept  Function 
The concept Function represents a function. More...  
Types  
typedef unspecified_type  NT 
The basic representational number type.  
typedef unspecified_type  Root 
A type representing the roots of a Function .  
typedef unspecified_type  Root_stack 
A model of RootStack . More...  
typedef unspecified_type  Root_enumerator_traits 
The traits for the Root_enumerator class.  
Each of the following types has a corresponding  
typedef unspecified_type  Sign_at 
A functor which returns the sign of a Function at a NT or Root .  
typedef unspecified_type  Sign_after 
A functor which returns sign of a function immediately after a root.  
The following functor likewise have a The arguments are given below.  
typedef unspecified_type  Sign_between_roots 
This functor, creation of which requires two Root s, returns the sign of a passed function between the pair of roots.  
typedef unspecified_type  Differentiate 
This functor computes the derivitive of a Function . More...  
The following methods do not require any arguments to get the functor and take one  
typedef unspecified_type  Negate_variable 
Map \( f(x)\) to \( f(x)\).  
This functor computes the derivitive of a Function
.
Construction takes no arguments.
A model of RootStack
.
These objects can be created by calling the root_stack_object
method with a Function
and two (optional) Root
objects. The enumerator then enumerates all roots of the function in the open inverval defined by the two root arguments. They optional arguments default to positive and negative infinity.