DGtal  1.1.0
DGtal::DSLSubsegment< TInteger, TNumber > Class Template Reference

Aim: Given a Digital Straight line and two endpoints A and B on this line, compute the minimal characteristics of the digital subsegment [AB] in logarithmic time. Two algorithms are implemented: one is based on the local computation of lower and upper convex hulls, the other is based on a dual transformation and uses the Farey fan. Implementation requires that the DSL lies in the first octant (0 <= a <= b). More...

#include <DGtal/geometry/curves/DSLSubsegment.h>

class  RayC

## Public Types

typedef TNumber Number

typedef TInteger Integer

typedef long double LongDoubleType

typedef DGtal::PointVector< 2, IntegerRay

typedef DGtal::PointVector< 2, IntegerPoint

typedef DGtal::PointVector< 2, NumberPointF

typedef DGtal::PointVector< 2, IntegerVector

typedef DGtal::PointVector< 2, NumberVectorF

## Public Member Functions

~DSLSubsegment ()

void selfDisplay (std::ostream &out) const

bool isValid () const

BOOST_CONCEPT_ASSERT ((concepts::CEuclideanRing< Number >))

BOOST_CONCEPT_ASSERT ((concepts::CInteger< Integer >))

DSLSubsegment (Number a, Number b, Number mu, Point &A, Point &B, std::string type)

DSLSubsegment (Number alpha, Number beta, Point &A, Point &B, Number precision=1e-10)

Integer computeMinRemainder (Number a, Number b, Number mu, Point A, Point B)

Integer computeMaxRemainder (Number a, Number b, Number mu, Point A, Point B)

Integer getA () const

Integer getB () const

Integer getMu () const

## Protected Types

enum  Position { ABOVE, BELOW, ONTO }

typedef enum DGtal::DSLSubsegment::Position Position

## Protected Member Functions

void DSLSubsegmentFareyFan (Number a, Number b, Number mu, Point &A, Point &B)

void DSLSubsegmentLocalCH (Number a, Number b, Number mu, Point &A, Point &B)

DSLSubsegment ()

Integer intersectionVertical (Point &P, Vector &v, Integer n)

Integer intersection (Point &P, Vector &v, Vector &aL, Integer r)

Integer intersection (Point &P, Vector &v, Number s)

void update (Vector &u, Point &A, Vector &l, Integer r, Vector *v)

void update (Vector &u, Point &A, Number s, Vector *v)

void lowerConvexHull (Vector &l, Integer mu, Point &A, Point &B, Point *prevInfL, Point *infL, Point *infR, Point *prevInfR)

void convexHullApprox (Vector &l, Integer r, Integer n, Point *inf, Point *sup)

void convexHullApprox (Number s, Integer n, Point *inf, Point *sup)

void convexHullApproxTwoPoints (Vector &l, Integer r, Integer n, Point *inf, Point *sup, Point *prevInf, Point *prevSup, bool inv)

void convexHullHarPeled (Vector &l, Integer n, Point *inf, Point *sup)

Point nextTermInFareySeriesEuclid (Integer fp, Integer fq, Integer n)

RayC rayOfHighestSlope (Integer p, Integer q, Integer r, Integer smallestSlope, Integer n)

Integer slope (Integer p, Integer q, Integer r, Number a, Number b, Number mu)

Integer slope (Integer p, Integer q, Integer r, Number alpha, Number beta)

Position positionWrtRay (RayC &r, Number a, Number b, Number mu)

Position positionWrtRay (RayC &r, Number alpha, Number beta)

RayC smartRayOfSmallestSlope (Integer fp, Integer fq, Integer gp, Integer gq, Integer r)

Integer smartFirstDichotomy (Integer fp, Integer fq, Integer gp, Integer gq, Number a, Number b, Number mu, Integer n, bool *flagRayFound)

Integer smartFirstDichotomy (Integer fp, Integer fq, Integer gp, Integer gq, Number alpha, Number beta, Integer n, bool *flagRayFound)

RayC localizeRay (Integer fp, Integer fq, Integer gp, Integer gq, Integer r, Number a, Number b, Number mu, Integer n)

RayC localizeRay (Integer fp, Integer fq, Integer gp, Integer gq, Integer r, Number alpha, Number beta, Integer n)

RayC raySup (Integer fp, Integer fq, RayC r)

void findSolutionWithoutFractions (Integer fp, Integer fq, Integer gp, Integer gq, RayC r, Integer n, Integer *resAlphaP, Integer *resAlphaQ, Integer *resBetaP, bool found)

void shortFindSolution (Integer fp, Integer fq, Integer gp, Integer gq, RayC r, Integer n, Integer *resAlphaP, Integer *resAlphaQ, Integer *resBetaP)

## Protected Attributes

Integer myA

Integer myB

Integer myMu

Number myPrecision

## Detailed Description

### template<typename TInteger, typename TNumber> class DGtal::DSLSubsegment< TInteger, TNumber >

Aim: Given a Digital Straight line and two endpoints A and B on this line, compute the minimal characteristics of the digital subsegment [AB] in logarithmic time. Two algorithms are implemented: one is based on the local computation of lower and upper convex hulls, the other is based on a dual transformation and uses the Farey fan. Implementation requires that the DSL lies in the first octant (0 <= a <= b).

Description of class 'DSLSubsegment'

Template Parameters
 TInteger is the type of integer used TNumber is the type of number used to represent the input DSL characteristics.
Examples
geometry/curves/exampleDSLSubsegment.cpp.

Definition at line 75 of file DSLSubsegment.h.

## ◆ Integer

template<typename TInteger , typename TNumber >
 typedef TInteger DGtal::DSLSubsegment< TInteger, TNumber >::Integer

Definition at line 104 of file DSLSubsegment.h.

## ◆ LongDoubleType

template<typename TInteger , typename TNumber >
 typedef long double DGtal::DSLSubsegment< TInteger, TNumber >::LongDoubleType

Definition at line 105 of file DSLSubsegment.h.

## ◆ Number

template<typename TInteger , typename TNumber >
 typedef TNumber DGtal::DSLSubsegment< TInteger, TNumber >::Number

Number types

Definition at line 103 of file DSLSubsegment.h.

## ◆ Point

template<typename TInteger , typename TNumber >
 typedef DGtal::PointVector<2,Integer> DGtal::DSLSubsegment< TInteger, TNumber >::Point

2D integer point

Definition at line 117 of file DSLSubsegment.h.

## ◆ PointF

template<typename TInteger , typename TNumber >
 typedef DGtal::PointVector<2,Number> DGtal::DSLSubsegment< TInteger, TNumber >::PointF

2D real point

Definition at line 122 of file DSLSubsegment.h.

## ◆ Position

template<typename TInteger , typename TNumber >
 typedef enum DGtal::DSLSubsegment::Position DGtal::DSLSubsegment< TInteger, TNumber >::Position
protected

Position of a point wrt a ray

## ◆ Ray

template<typename TInteger , typename TNumber >
 typedef DGtal::PointVector<2,Integer> DGtal::DSLSubsegment< TInteger, TNumber >::Ray

A ray is defined as a 2D integer vector (x,y) such that Ray(x,y) is the straight line beta = -x alpha +y in the (alpha,beta)-space.

Definition at line 112 of file DSLSubsegment.h.

## ◆ Vector

template<typename TInteger , typename TNumber >
 typedef DGtal::PointVector<2,Integer> DGtal::DSLSubsegment< TInteger, TNumber >::Vector

2D integer vector

Definition at line 127 of file DSLSubsegment.h.

## ◆ VectorF

template<typename TInteger , typename TNumber >
 typedef DGtal::PointVector<2,Number> DGtal::DSLSubsegment< TInteger, TNumber >::VectorF

2D real vector

Definition at line 132 of file DSLSubsegment.h.

## ◆ Position

template<typename TInteger , typename TNumber >
 protected

Position of a point wrt a ray

Enumerator
ABOVE
BELOW
ONTO

Definition at line 279 of file DSLSubsegment.h.

280  {
281  ABOVE,
282  BELOW,
283  ONTO
284  } Position;

## ◆ ~DSLSubsegment()

template<typename TInteger , typename TNumber >
 DGtal::DSLSubsegment< TInteger, TNumber >::~DSLSubsegment ( )
inline

Destructor.

Definition at line 83 of file DSLSubsegment.h.

83 {};

## ◆ DSLSubsegment() [1/3]

template<typename TInteger , typename TNumber >
 DGtal::DSLSubsegment< TInteger, TNumber >::DSLSubsegment ( Number a, Number b, Number mu, Point & A, Point & B, std::string type )

Constructor Given the parameters of a DSL 0 <= ax -by + mu < b, and two points A and B of this DSL, compute the parameters of the DSS [AB]. The algorithm used depends on the value of the boolean (Farey fan if true, local convex hull otherwise).

Parameters
 [in] a DSL a parameter [in] b DSL b parameter [in] mu DSL mu parameter [in] A left-most point [in] B right-most point [in] type a type

## ◆ DSLSubsegment() [2/3]

template<typename TInteger , typename TNumber >
 DGtal::DSLSubsegment< TInteger, TNumber >::DSLSubsegment ( Number alpha, Number beta, Point & A, Point & B, Number precision = 1e-10 )

Constructor Given a straight line of equation y = alpha x + beta, and two points A and B of the OBQ digitization of this line, compute the parameters of the DSS [AB]. The algorithm implemented uses the Farey fan. Requires a precision parameter for floating-point geometrical predicates

Parameters
 [in] alpha slope of the line [in] beta intercept of the line [in] A left-most point [in] B right-most point [in] precision precision

## ◆ DSLSubsegment() [3/3]

template<typename TInteger , typename TNumber >
 DGtal::DSLSubsegment< TInteger, TNumber >::DSLSubsegment ( )
protected

Constructor. Forbidden by default (protected to avoid g++ warnings).

## ◆ BOOST_CONCEPT_ASSERT() [1/2]

template<typename TInteger , typename TNumber >
 DGtal::DSLSubsegment< TInteger, TNumber >::BOOST_CONCEPT_ASSERT ( (concepts::CEuclideanRing< Number >) )

Check that Number type verifies the Euclidean Rign concept and Integer type verifies the Integer concept

## ◆ BOOST_CONCEPT_ASSERT() [2/2]

template<typename TInteger , typename TNumber >
 DGtal::DSLSubsegment< TInteger, TNumber >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< Integer >) )

## ◆ computeMaxRemainder()

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::computeMaxRemainder ( Number a, Number b, Number mu, Point A, Point B )

## ◆ computeMinRemainder()

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::computeMinRemainder ( Number a, Number b, Number mu, Point A, Point B )

## ◆ convexHullApprox() [1/2]

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::convexHullApprox ( Number s, Integer n, Point * inf, Point * sup )
protected

Compute the left part of the upper and lower convex hulls of the line of slope s, between x=0 and x=n. Returns the upper and lower closest points.

Parameters
 s slope of the line (interpect is equal to zero here) n maximal value of x-coordinate [out] inf closest point below the line [out] sup closest point above the line

## ◆ convexHullApprox() [2/2]

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::convexHullApprox ( Vector & l, Integer r, Integer n, Point * inf, Point * sup )
protected

Compute the left part of the upper and lower convex hulls of the line of directional vector l and intercept r, between x=0 and x=n. Returns the upper and lower closest points. Implementation of Charrier and Buzer algorithm [21]

Parameters
 l directional vector of the line r intercept of the line n maximal value of x-coordinate [out] inf closest point below the line [out] sup closest point above the line

## ◆ convexHullApproxTwoPoints()

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::convexHullApproxTwoPoints ( Vector & l, Integer r, Integer n, Point * inf, Point * sup, Point * prevInf, Point * prevSup, bool inv )
protected

Compute the left part of the upper and lower convex hulls of the line of slope s, between x=0 and x=n. Returns the last two points computed. Implementation of Charrier and Buzer algorithm [21]

Parameters
 l directional vector of the line r intercept of the line n maximal value of x-coordinate [out] inf closest point below the line [out] sup closest point above the line [out] prevInf second-closest point below the line [out] prevSup second-closest point above the line inv boolean used to know if the CH is computed from left-to-right (inv=false) or right-to-left (inv = true)

## ◆ convexHullHarPeled()

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::convexHullHarPeled ( Vector & l, Integer n, Point * inf, Point * sup )
protected

Compute the left part of the upper and lower convex hulls of the line of directional vector l, between x=0 and x=n. Returns the last two points computed. Implementation of Har-Peled algorithm (Computational Geometry: Theory and Applications, 1998)

Parameters
 l directional vector of the line (intercept is zero) n maximal value of x-coordinate [out] inf closest point below the line [out] sup closest point above the line

## ◆ DSLSubsegmentFareyFan()

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::DSLSubsegmentFareyFan ( Number a, Number b, Number mu, Point & A, Point & B )
protected

Function called by the constructor when the input parameters are integers and the Farey Fan algorithm is used.

Parameters
 a DSL a parameter b DSL b parameter mu DSL mu parameter A left-most point B right-most point

## ◆ DSLSubsegmentLocalCH()

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::DSLSubsegmentLocalCH ( Number a, Number b, Number mu, Point & A, Point & B )
protected

Function called by the constructor when the input parameters are integers and the local convex hull algorithm is used.

Parameters
 a DSL a parameter b DSL b parameter mu DSL mu parameter A left-most point B right-most point

## ◆ findSolutionWithoutFractions()

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::findSolutionWithoutFractions ( Integer fp, Integer fq, Integer gp, Integer gq, RayC r, Integer n, Integer * resAlphaP, Integer * resAlphaQ, Integer * resBetaP, bool found )
protected

The two fractions f and g together with the ray r define a segment PQ. PQ is part of the lower boundary of exactly one cell of the FareyFan. This cell represents a DSS. This function computes the vertex of the cell that represents the minimal characteristics of the DSS. Optimized version of the algorithm presented in the paper [92] . Complexity of nextTermInFareySeriesEuclid

Parameters
 fp numerator of the smallest fraction of the ladder fq denominator of the smallest fraction of the ladder gp numerator of the greatest fraction of the ladder gq denominator of the greatest fraction of the ladder r a ray n order of the Farey Fan [out] resAlphaP numerator of the x-coordinate of the result [out] resAlphaQ denominator of the x- and y- coordinates of the result [out] resBetaP numerator of the y-coordinate of the result [in] found used for optimization (true if r is the ray of smallest slope on point P, false otherwise). Its value comes from the smartFirstDichotomy function.

## ◆ getA()

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::getA ( ) const
Returns
an Integer of value myA.

## ◆ getB()

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::getB ( ) const
Returns
an Integer of value myB.

## ◆ getMu()

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::getMu ( ) const
Returns
an Integer of value myMu.

## ◆ intersection() [1/2]

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::intersection ( Point & P, Vector & v, Number s )
protected

Compute the intersection between the line of direction v passing through P and the line y = s*x The intersection point is of the form P + α*v and the function returns the value floor(α).

Parameters
 P a point of the first line v directional vector of the first line s slope of the second line
Returns
integer

## ◆ intersection() [2/2]

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::intersection ( Point & P, Vector & v, Vector & aL, Integer r )
protected

Compute the intersection between the line of direction v passing through P and the line y = (aL[1]/aL[0])*x +r The intersection point is of the form P + α*v and the function returns the value floor(α).

Parameters
 P a point of the first line v directional vector of the first line aL slope of the second line is equal to aL[1]/aL[0] r intercept of the second line
Returns
integer

## ◆ intersectionVertical()

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::intersectionVertical ( Point & P, Vector & v, Integer n )
protected

Compute the intersection between the line of direction v passing through P and the vertical line x = n. The intersection point is of the form P + α*v and the function returns the value floor(α).

Parameters
 P a point v directional vector of the line n maximal value for x-coordinate
Returns
integer

## ◆ isValid()

template<typename TInteger , typename TNumber >
 bool DGtal::DSLSubsegment< TInteger, TNumber >::isValid ( ) const

Checks the validity/consistency of the object.

Returns
'true' if the object is valid, 'false' otherwise.

## ◆ localizeRay() [1/2]

template<typename TInteger , typename TNumber >
 RayC DGtal::DSLSubsegment< TInteger, TNumber >::localizeRay ( Integer fp, Integer fq, Integer gp, Integer gq, Integer r, Number a, Number b, Number mu, Integer n )
protected

Compute the closest ray below the point (a/b,mu/b) passing through the point (fp/fq,r/fq) in the Farey fan of order n

Parameters
 fp numerator of the smallest fraction of the ladder fq denominator of the smallest fraction of the ladder gp numerator of the greatest fraction of the ladder gq denominator of the greatest fraction of the ladder r numerator of the point y-coordinate a DSL a parameter b DSL b parameter mu DSL my parameter n order of the Farey Fan
Returns
a ray

## ◆ localizeRay() [2/2]

template<typename TInteger , typename TNumber >
 RayC DGtal::DSLSubsegment< TInteger, TNumber >::localizeRay ( Integer fp, Integer fq, Integer gp, Integer gq, Integer r, Number alpha, Number beta, Integer n )
protected

Compute the closest ray below the point (alpha,beta) passing through the point (fp/fq,r/fq) in the Farey fan of order n

Parameters
 fp numerator of the smallest fraction of the ladder fq denominator of the smallest fraction of the ladder gp numerator of the greatest fraction of the ladder gq denominator of the greatest fraction of the ladder r numerator of the point y-coordinate alpha DSL slope beta DSL intercept n order of the Farey Fan
Returns
a ray

## ◆ lowerConvexHull()

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::lowerConvexHull ( Vector & l, Integer mu, Point & A, Point & B, Point * prevInfL, Point * infL, Point * infR, Point * prevInfR )
protected

Compute the lower integer convex hull of the line of directional vector l and intercept mu between the points A and B. The algorithm works in two steps (from left to right and right to left). Each step returns the two closest points, and these four points are returned by the function.

Parameters
 l directional vector of the straight line mu intercept of the straight line A left-most bound of the CH B right-most bound of the CH [out] prevInfL last-but-one point of the CH from left to right [out] infL last point of the CH from left to right [out] infR last point of the CH from right to left [out] prevInfR last-but-one point of the CH from right to left

## ◆ nextTermInFareySeriesEuclid()

template<typename TInteger , typename TNumber >
 Point DGtal::DSLSubsegment< TInteger, TNumber >::nextTermInFareySeriesEuclid ( Integer fp, Integer fq, Integer n )
protected

Compute the term following fp/fq in the Farey series of order n.

Parameters
 fp numerator fq denominator n order the the Farey Series
Returns
a point (q,p) such that p/q follows fp/fq in the Farey Series of order n

## ◆ positionWrtRay() [1/2]

template<typename TInteger , typename TNumber >
 Position DGtal::DSLSubsegment< TInteger, TNumber >::positionWrtRay ( RayC & r, Number a, Number b, Number mu )
protected

Compute the position of the point (a/b,mu/b) with respect to a ray r. Number must be an Integer type

Parameters
 r a ray a numerator of x-coordinate b denominator of x- and y-coordinates mu numerator of x-coordinate
Returns
Position equal to BELOW, ABOVE or ONTO

## ◆ positionWrtRay() [2/2]

template<typename TInteger , typename TNumber >
 Position DGtal::DSLSubsegment< TInteger, TNumber >::positionWrtRay ( RayC & r, Number alpha, Number beta )
protected

Compute the position of the floating-point point(alpha,beta) with respect to a ray r.

Parameters
 r a ray alpha x-coordinate beta y-coordinate
Returns
Position equal to BELOW, ABOVE or ONTO

## ◆ rayOfHighestSlope()

template<typename TInteger , typename TNumber >
 RayC DGtal::DSLSubsegment< TInteger, TNumber >::rayOfHighestSlope ( Integer p, Integer q, Integer r, Integer smallestSlope, Integer n )
protected

Compute the ray of highest slope passing through a given point (p/q,r/q) in O(1) knowing the ray of smallest slope and the order of the Farey fan

Parameters
 p numerator of x-coordinate q denominator of x- and y-coordinates r numerator of y-coordinate smallestSlope smallest slope of the rays passing through (p/q,r/q) n order of the Farey fan
Returns
a ray

## ◆ raySup()

template<typename TInteger , typename TNumber >
 RayC DGtal::DSLSubsegment< TInteger, TNumber >::raySup ( Integer fp, Integer fq, RayC r )
protected

Compute the ray passing through from (f=fp/fq,h/fq) just above r. The knowledge of h is not necessary. Complexity O(1)

Parameters
 fp numerator fq denominator r a ray

## ◆ selfDisplay()

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::selfDisplay ( std::ostream & out ) const

Writes/Displays the object on an output stream.

Parameters
 out the output stream where the object is written.

## ◆ shortFindSolution()

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::shortFindSolution ( Integer fp, Integer fq, Integer gp, Integer gq, RayC r, Integer n, Integer * resAlphaP, Integer * resAlphaQ, Integer * resBetaP )
protected

Corresponds to the algorithm presented in [92].

Parameters
 fp numerator of the smallest fraction of the ladder fq denominator of the smallest fraction of the ladder gp numerator of the greatest fraction of the ladder gq denominator of the greatest fraction of the ladder r a ray n order of the Farey Fan [out] resAlphaP numerator of the x-coordinate of the result [out] resAlphaQ denominator of the x- and y- coordinates of the result [out] resBetaP numerator of the y-coordinate of the result

## ◆ slope() [1/2]

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::slope ( Integer p, Integer q, Integer r, Number a, Number b, Number mu )
protected

Compute the ceil of the slope of the line through (f=p/q,r/q) and point (a/b,mu/b) - O(1) - Number must be an Integer type.

Parameters
 p numerator of x-coordinate of the first point q denominator of x- and y-coordinates of the first point r numerator of y-coordinate of the first point a numerator of x-coordinate of the second point b denominator of x- and y-coordinates of the second point mu numerator of y-coordinate of the second point
Returns
the ceil of the slope of the line passing through the two points

## ◆ slope() [2/2]

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::slope ( Integer p, Integer q, Integer r, Number alpha, Number beta )
protected

Compute the ceil of the slope of the line through (f=p/q,r/q) and floating-point point (alpha,beta) - O(1)

Parameters
 p numerator of x-coordinate of the first point q denominator of x- and y-coordinates of the first point r numerator of y-coordinate of the first point alpha x-coordinate of the second point beta y-coordinate of the second point
Returns
the ceil of the slope of the line passing through the two points

## ◆ smartFirstDichotomy() [1/2]

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::smartFirstDichotomy ( Integer fp, Integer fq, Integer gp, Integer gq, Number a, Number b, Number mu, Integer n, bool * flagRayFound )
protected

Performs a dichotomy among the rays of smallest slope passing through the points (fp/fq,r/fq), r in [0,fq] in order to locate the point lambda(a/b,mu/b) in the ladder. Implements line 3 of Algorithm 1 in [92]. Return an integer h such that either i) lambda is in between the rays passing through the point (fp/fq,h/fq) and flagRayFound is set to false or ii) lambda is below all the rays passing through the point (fp/fq,h+1/fq) and above all the rays passing through the point (fp/fq,h/fq) and flagRayFound is set to false. In case i), function localizeRay is used afterwards to localize lambda in between the rays. In case ii), the ray under lambda has been found and no further search is needed. The Number type must verify the CInteger concept (otherwise, see overloaded function).

Parameters
 fp numerator of the smallest fraction of the ladder fq denominator of the smallest fraction of the ladder gp numerator of the greatest fraction of the ladder gq denominator of the greatest fraction of the ladder a DSL a parameter b DSL b parameter mu DSL mu parameter n order of the Farey Fan [out] flagRayFound pointer on a boolean, used to check whether localizeRay should be called ot not
Returns
an integer

## ◆ smartFirstDichotomy() [2/2]

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::smartFirstDichotomy ( Integer fp, Integer fq, Integer gp, Integer gq, Number alpha, Number beta, Integer n, bool * flagRayFound )
protected

Performs a dichotomy among the rays of smallest slope passing through the points (fp/fq,r/fq), r in [0,fq] in order to locate the point lambda(alpha,beta) in the ladder. Implements line 3 of Algorithm 1 in [92]. Return an integer h such that either i) lambda is in between the rays passing through the point (fp/fq,h/fq) and flagRayFound is set to false or ii) lambda is below all the rays passing through the point (fp/fq,h+1/fq) and above all the rays passing through the point (fp/fq,h/fq) and flagRayFound is set to false. In case i), function localizeRay is used afterwards to localize lambda in between the rays. In case ii), the ray under lambda has been found and no further search is needed.

Parameters
 fp numerator of the smallest fraction of the ladder fq denominator of the smallest fraction of the ladder gp numerator of the greatest fraction of the ladder gq denominator of the greatest fraction of the ladder alpha DSL slope beta DSL intercept n order of the Farey Fan [out] flagRayFound pointer on a boolean, used to check whether localizeRay should be called ot not
Returns
an integer

## ◆ smartRayOfSmallestSlope()

template<typename TInteger , typename TNumber >
 RayC DGtal::DSLSubsegment< TInteger, TNumber >::smartRayOfSmallestSlope ( Integer fp, Integer fq, Integer gp, Integer gq, Integer r )
protected

Computes the ray of smallest slope emanating from the point (f=p/q, r/q) using the knowledge of the next fraction g in the Farey Series. Complexity O(1)

Parameters
 fp numerator of the point x-coordinate fq denominator of the point x- and y-coordinates gp numerator of the fraction following fp/fq in the Farey Series gq denominator of the fraction following fp/fq in the Farey Series r numerator of the point y-coordinate
Returns
the ray of smallest slope passing through the point

## ◆ update() [1/2]

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::update ( Vector & u, Point & A, Number s, Vector * v )
protected

Update the Bezout vector v of u according to the new point A in the case of floating-point parameters. Follows algorithm presented in [21]

Parameters
 u a vector A a point s slope of the line [in,out] v bezout vector updated in this function

## ◆ update() [2/2]

template<typename TInteger , typename TNumber >
 void DGtal::DSLSubsegment< TInteger, TNumber >::update ( Vector & u, Point & A, Vector & l, Integer r, Vector * v )
protected

Update the Bezout vector v of u according to the new point A in the case of integer parameters. Follows algorithm presented in [21]

Parameters
 u a vector A a point l directional vector of the line r intercept of the line [in,out] v bezout vector updated in this function

## ◆ myA

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::myA
protected

The minimal characteristics of the subsegment AB of the DSL(a,b,mu) are (myA,myB,myMu).

Definition at line 147 of file DSLSubsegment.h.

## ◆ myB

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::myB
protected

The minimal characteristics of the subsegment AB of the DSL(a,b,mu) are (myA,myB,myMu).

Definition at line 154 of file DSLSubsegment.h.

## ◆ myMu

template<typename TInteger , typename TNumber >
 Integer DGtal::DSLSubsegment< TInteger, TNumber >::myMu
protected

The minimal characteristics of the subsegment AB of the DSL(a,b,mu) are (myA,myB,myMu).

Definition at line 161 of file DSLSubsegment.h.

## ◆ myPrecision

template<typename TInteger , typename TNumber >
 Number DGtal::DSLSubsegment< TInteger, TNumber >::myPrecision
protected

Precision used for floating-point geometrical predicates (when TNumber is not an integer type)

Definition at line 167 of file DSLSubsegment.h.

The documentation for this class was generated from the following file:
DGtal::DSLSubsegment::BELOW
@ BELOW
Definition: DSLSubsegment.h:282
DGtal::DSLSubsegment::ONTO
@ ONTO
Definition: DSLSubsegment.h:283
DGtal::DSLSubsegment::ABOVE
@ ABOVE
Definition: DSLSubsegment.h:281
DGtal::DSLSubsegment::Position
Position
Definition: DSLSubsegment.h:280