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>

Data Structures
class	RayC

Public Types
typedef TNumber	Number

typedef TInteger	Integer

typedef long double	LongDoubleType

typedef DGtal::PointVector< 2, Integer >	Ray

typedef DGtal::PointVector< 2, Integer >	Point

typedef DGtal::PointVector< 2, Number >	PointF

typedef DGtal::PointVector< 2, Integer >	Vector

typedef DGtal::PointVector< 2, Number >	VectorF

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.

Member Typedef Documentation

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

Member Enumeration Documentation

◆ Position

template<typename TInteger , typename TNumber >

enum DGtal::DSLSubsegment::Position

protected

Position of a point wrt a ray

Enumerator
ABOVE
BELOW
ONTO

Definition at line 279 of file DSLSubsegment.h.

       {
         ABOVE,
         BELOW,
         ONTO
       } Position;

Constructor & Destructor Documentation

◆ ~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).

Member Function Documentation

◆ 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 [23]

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 [23]

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 [116] . 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 [116].

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 [116]. 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 [116]. 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 [23]

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 [23]

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

Field Documentation

◆ 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:

DSLSubsegment.h

Data Structures

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

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

Member Typedef Documentation

◆ Integer

◆ LongDoubleType

◆ Number

◆ Point

◆ PointF

◆ Position

◆ Ray

◆ Vector

◆ VectorF

Member Enumeration Documentation

◆ Position

Constructor & Destructor Documentation

◆ ~DSLSubsegment()

◆ DSLSubsegment() [1/3]

◆ DSLSubsegment() [2/3]

◆ DSLSubsegment() [3/3]

Member Function Documentation

◆ BOOST_CONCEPT_ASSERT() [1/2]

◆ BOOST_CONCEPT_ASSERT() [2/2]

◆ computeMaxRemainder()

◆ computeMinRemainder()

◆ convexHullApprox() [1/2]

◆ convexHullApprox() [2/2]

◆ convexHullApproxTwoPoints()

◆ convexHullHarPeled()

◆ DSLSubsegmentFareyFan()

◆ DSLSubsegmentLocalCH()

◆ findSolutionWithoutFractions()

◆ getA()

◆ getB()

◆ getMu()

◆ intersection() [1/2]

◆ intersection() [2/2]

◆ intersectionVertical()

◆ isValid()

◆ localizeRay() [1/2]

◆ localizeRay() [2/2]

◆ lowerConvexHull()

◆ nextTermInFareySeriesEuclid()

◆ positionWrtRay() [1/2]

◆ positionWrtRay() [2/2]

◆ rayOfHighestSlope()

◆ raySup()

◆ selfDisplay()

◆ shortFindSolution()

◆ slope() [1/2]

◆ slope() [2/2]

◆ smartFirstDichotomy() [1/2]

◆ smartFirstDichotomy() [2/2]

◆ smartRayOfSmallestSlope()

◆ update() [1/2]

◆ update() [2/2]

Field Documentation

◆ myA

◆ myB

◆ myMu

◆ myPrecision

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