SinEqLine Class Reference

Helper class to calculate roots for the function f(x) = sin x - slope * x - intercept. More...

#include <SinEqLine.h>

Public Member Functions
	SinEqLine ()
	Default constructor initializing slope and intercept to zero.
	SinEqLine (const Line2D &line2D)
	Constructor taking the line that shall be superimposed with the sin curve.
	SinEqLine (const double slope, const double intercept)
	Constructor taking the slope and intercept of the line that shall be superimposed with the sin curve.
double	map (const double x) const
	Interpreting as the function f this method carries out the translation from x to y coordinates.
double	gradient (const double x) const
	Interpreting as the function f this method calculates the gradient as need in Newtons algorithms.
int	getIHalfPeriod (const double x) const
	Returns the half period index in which the x position is located.
double	computeSmallestPositiveRoot (int maxIHalfPeriod=5) const
double	computeRootLargerThanExtemumInHalfPeriod (int iHalfPeriod) const
	Computes the solution that is addressed by the given half period index.
double	computeRootForLargeSlope () const
	Compute single solution in the case that fabs(slope) >= 1.
double	computeRootInInterval (double lowerX, double upperX) const
	Computes the solution in between the given x values. The x values are generally choosen consecutive local extermas. More...
double	computeExtremumXInHalfPeriod (int iHalfPeriod) const
	Get the local extermum that is located in the half period indicated by the given index.
bool	hasLargeSlope () const
	Indicates that the slope is so large such that the function has no local exterma.
double	getSlope () const
	Getter for the slope.
double	getIntercept () const
	Getter for the intercept.

Static Public Member Functions
static bool	changesSign (const Vector2D &lower, const Vector2D &upper)
	Checks if the function changes sign in the intervall.
static EIncDec	getEIncDec (const Vector2D &lower, const Vector2D &upper)
	Determines if the function is increasing or decreasing in the intervall.
static int	getIPeriodFromIHalfPeriod (int iHalfPeriod)
	Helper function to translate the index of the half period to index of the containing period.

Private Member Functions
double	newtonX (const Vector2D &pos) const
	Shrinking method of the newton algorithm return the next candidate root.

Static Private Member Functions
static double	secantX (const Vector2D &lower, const Vector2D &upper)
	Fall back shrinking method to the secant algorithm.
static double	middleX (const Vector2D &lower, const Vector2D &upper)
	Simple fall back shrinking method using trivial devision of the intervall.
static bool	updateBounds (Vector2D &lower, Vector2D &upper, const Vector2D &next)
	Replaces the lower or upper bound inplace if the next candidate position is valid and within the intervall. Returns true on success. More...
static bool	isBetween (const Vector2D &lower, const Vector2D &next, const Vector2D &upper)
	Check is next position is within the intervall given by lower and upper.
static bool	isConverged (const Vector2D &lower, const Vector2D &upper)
	Check if the intervall has shrunk close enough to the solution.
static double	getConvergedBound (const Vector2D &lower, const Vector2D &upper)
	Returns the better solution x from the bounds of the intervall.

Private Attributes
double	m_slope
	Memory for the slope.
double	m_intercept
	Memory for the intercept.

Detailed Description

Helper class to calculate roots for the function f(x) = sin x - slope * x - intercept.

Solves the equation sin x = slope * x + intercept by netwons method on the function f(x) = sin x - slope * x - intercept. There can be zero, infinitly many solutions and anything inbetween depending on the value of slope and intercept. To find solutions we expliot that the local exterma of the function f(x) can be found easily and that maximally one solutions can be found between consecutive extrema. There is exactly one local extermum in each half period of sin(x) and local extrema are therefore addressed by there half period index. Each possible solution of the equation is than addressed by the index of the closest smaller local extrema. However only a range of indices corresponds to realized solutions. For non existent solutions NAN is returned. Note that for fabs(slope) >= 1 there are no more local maxima. In this case only a single solution exists, which is always returned for any index.

Definition at line 46 of file SinEqLine.h.

Member Function Documentation

computeRootInInterval()

double computeRootInInterval	(	double	lowerX,
		double	upperX
	)		const

Computes the solution in between the given x values. The x values are generally choosen consecutive local extermas.

Checks if convergence criterium has been met. For instance if one bound is already exactly at the root.

Checks if the function changes sign in the interval

Definition at line 69 of file SinEqLine.cc.

{
  if (not(lowerX < upperX)) return NAN;
 
  Vector2D lower(lowerX, map(lowerX));
  Vector2D upper(upperX, map(upperX));
 
  if (isConverged(lower, upper)) {
    B2INFO("Coverage early");
    return getConvergedBound(lower, upper);
  }
 
  if (not changesSign(lower, upper)) {
    return NAN;
  }
 
  Vector2D last(lower);
  Vector2D current(upper);
 
  Vector2D next;
  next.setX(secantX(last, current));
  next.setY(map(next.x()));
 
  // Should  always succeed since we checked everything before
  // cppcheck-suppress unreadVariable
  bool updatedBound = updateBounds(lower, upper, next);
  if (not updatedBound) return NAN;
 
  while (not isConverged(lower, upper)) {
    // swap accepted values
    last.set(current);
    current.set(next);
 
    next.setX(newtonX(current));
    next.setY(map(next.x()));
 
    updatedBound = updateBounds(lower, upper, next);
 
    if (not updatedBound) {
 
      // fall back to sekant.
      next.setX(secantX(last, current));
      next.setY(map(next.x()));
 
      updatedBound = updateBounds(lower, upper, next);
 
      if (not updatedBound) {
        // fallback to interval devision.
        next.setX(middleX(lower, upper));
        next.setY(map(next.x()));
        updatedBound = updateBounds(lower, upper, next);
 
        if (not updatedBound) break;
      }
    }
  }
 
  if (isConverged(lower, upper)) {
    return getConvergedBound(lower, upper);
 
  } else {
    return NAN;
  }
}

computeSmallestPositiveRoot()

double computeSmallestPositiveRoot

(

int

maxIHalfPeriod = 5

)

const

Smallest positive root might before the first positive extermum

Most of the time to should be sufficient to look for the root in the first two half periods. So we spell out this case explicitly.

Check if the solution returned is positiv, that implies that it is not NAN.

Definition at line 19 of file SinEqLine.cc.

updateBounds()

bool updateBounds ( Vector2D &  lower, Vector2D &  upper, const Vector2D &  next  )

staticprivate

Replaces the lower or upper bound inplace if the next candidate position is valid and within the intervall. Returns true on success.

Only update if the next point is inbetween the lower and upper bound

Definition at line 152 of file SinEqLine.cc.

---

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

• tracking/trackFindingCDC/numerics/include/SinEqLine.h
• tracking/trackFindingCDC/numerics/src/SinEqLine.cc