DGtal 1.3.0
|
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 Attributes | |
Integer | myA |
Integer | myB |
Integer | myMu |
Number | myPrecision |
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'
TInteger | is the type of integer used |
TNumber | is the type of number used to represent the input DSL characteristics. |
Definition at line 75 of file DSLSubsegment.h.
typedef TInteger DGtal::DSLSubsegment< TInteger, TNumber >::Integer |
Definition at line 104 of file DSLSubsegment.h.
typedef long double DGtal::DSLSubsegment< TInteger, TNumber >::LongDoubleType |
Definition at line 105 of file DSLSubsegment.h.
typedef TNumber DGtal::DSLSubsegment< TInteger, TNumber >::Number |
Number types
Definition at line 103 of file DSLSubsegment.h.
typedef DGtal::PointVector<2,Integer> DGtal::DSLSubsegment< TInteger, TNumber >::Point |
2D integer point
Definition at line 117 of file DSLSubsegment.h.
typedef DGtal::PointVector<2,Number> DGtal::DSLSubsegment< TInteger, TNumber >::PointF |
2D real point
Definition at line 122 of file DSLSubsegment.h.
|
protected |
Position of a point wrt a ray
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.
typedef DGtal::PointVector<2,Integer> DGtal::DSLSubsegment< TInteger, TNumber >::Vector |
2D integer vector
Definition at line 127 of file DSLSubsegment.h.
typedef DGtal::PointVector<2,Number> DGtal::DSLSubsegment< TInteger, TNumber >::VectorF |
2D real vector
Definition at line 132 of file DSLSubsegment.h.
|
protected |
|
inline |
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).
[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 |
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
[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 |
|
protected |
Constructor. Forbidden by default (protected to avoid g++ warnings).
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
DGtal::DSLSubsegment< TInteger, TNumber >::BOOST_CONCEPT_ASSERT | ( | (concepts::CInteger< Integer >) | ) |
Integer DGtal::DSLSubsegment< TInteger, TNumber >::computeMaxRemainder | ( | Number | a, |
Number | b, | ||
Number | mu, | ||
Point | A, | ||
Point | B | ||
) |
Integer DGtal::DSLSubsegment< TInteger, TNumber >::computeMinRemainder | ( | Number | a, |
Number | b, | ||
Number | mu, | ||
Point | A, | ||
Point | B | ||
) |
|
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.
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 |
|
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 [22]
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 |
|
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 [22]
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) |
|
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)
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 |
|
protected |
Function called by the constructor when the input parameters are integers and the Farey Fan algorithm is used.
a | DSL a parameter |
b | DSL b parameter |
mu | DSL mu parameter |
A | left-most point |
B | right-most point |
|
protected |
Function called by the constructor when the input parameters are integers and the local convex hull algorithm is used.
a | DSL a parameter |
b | DSL b parameter |
mu | DSL mu parameter |
A | left-most point |
B | right-most point |
|
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 [111] . Complexity of nextTermInFareySeriesEuclid
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. |
Integer DGtal::DSLSubsegment< TInteger, TNumber >::getA | ( | ) | const |
Integer DGtal::DSLSubsegment< TInteger, TNumber >::getB | ( | ) | const |
Integer DGtal::DSLSubsegment< TInteger, TNumber >::getMu | ( | ) | const |
|
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(α).
P | a point of the first line |
v | directional vector of the first line |
s | slope of the second line |
|
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(α).
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 |
|
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(α).
P | a point |
v | directional vector of the line |
n | maximal value for x-coordinate |
bool DGtal::DSLSubsegment< TInteger, TNumber >::isValid | ( | ) | const |
Checks the validity/consistency of the object.
|
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
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 |
|
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
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 |
|
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.
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 |
|
protected |
Compute the term following fp/fq in the Farey series of order n.
fp | numerator |
fq | denominator |
n | order the the Farey Series |
|
protected |
Compute the position of the point (a/b,mu/b) with respect to a ray r. Number must be an Integer type
r | a ray |
a | numerator of x-coordinate |
b | denominator of x- and y-coordinates |
mu | numerator of x-coordinate |
|
protected |
Compute the position of the floating-point point(alpha,beta) with respect to a ray r.
r | a ray |
alpha | x-coordinate |
beta | y-coordinate |
|
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
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 |
|
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)
fp | numerator |
fq | denominator |
r | a ray |
void DGtal::DSLSubsegment< TInteger, TNumber >::selfDisplay | ( | std::ostream & | out | ) | const |
Writes/Displays the object on an output stream.
out | the output stream where the object is written. |
|
protected |
Corresponds to the algorithm presented in [111].
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 |
|
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.
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 |
|
protected |
Compute the ceil of the slope of the line through (f=p/q,r/q) and floating-point point (alpha,beta) - O(1)
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 |
|
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 [111]. 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).
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 |
|
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 [111]. 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.
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 |
|
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)
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 |
|
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 [22]
u | a vector | |
A | a point | |
s | slope of the line | |
[in,out] | v | bezout vector updated in this function |
|
protected |
Update the Bezout vector v of u according to the new point A in the case of integer parameters. Follows algorithm presented in [22]
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 |
|
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.
|
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.
|
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.
|
protected |
Precision used for floating-point geometrical predicates (when TNumber is not an integer type)
Definition at line 167 of file DSLSubsegment.h.