DGtal
1.5.beta
|
Hull2D namespace gathers useful functions to compute and return the convex hull or the alpha-shape of a range of 2D points. More...
Enumerations | |
enum | ThicknessDefinition { HorizontalVerticalThickness , EuclideanThickness } |
The 2 thickness definitions. More... | |
Functions | |
template<typename Stack , typename Point , typename Predicate > | |
void | updateHullWithStack (Stack &aStack, const Point &aNewPoint, const Predicate &aPredicate) |
Procedure that updates the hull when an extra point aNewPoint is considered: while the last three consecutive points, ie. aNewPoint and the last two points of the container are not oriented such that the predicate aPredicate returns 'true', the last point of the container is removed. More... | |
template<typename Stack , typename Point , typename Predicate > | |
void | updateHullWithAdaptedStack (Stack aStack, const Point &aNewPoint, const Predicate &aPredicate) |
Procedure that calls Hull2D::updateHullWithStack on a copy of the stack object used to retrieved the hull vertices. Useful when the first argument is a stack adapter returned by a function: it must be copied before being passed by reference in Hull2D::updateHullWithStack. More... | |
template<typename Stack , typename ForwardIterator , typename Predicate > | |
void | buildHullWithStack (Stack &aStack, const ForwardIterator &itb, const ForwardIterator &ite, const Predicate &aPredicate) |
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP) in linear-time. This technique is called Sklansky's scan, Graham's scan or 3-coins algorithm. It works for all WEVP [Toussaint and Avis, 1982 : [117]]. More... | |
template<typename Stack , typename ForwardIterator , typename Predicate > | |
void | buildHullWithAdaptedStack (Stack aStack, const ForwardIterator &itb, const ForwardIterator &ite, const Predicate &aPredicate) |
Procedure that calls Hull2D::buildHullWithStack on a copy of the stack object used to retrieved the hull vertices. Useful when the first argument is a stack adapter returned by a function: it must be copied before being passed by reference in Hull2D::buildHullWithStack. More... | |
template<typename ForwardIterator , typename OutputIterator , typename Predicate > | |
void | openGrahamScan (const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate) |
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP) in linear-time. More... | |
template<typename ForwardIterator , typename OutputIterator , typename Predicate > | |
void | closedGrahamScanFromVertex (const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate) |
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP) in linear-time. More... | |
template<typename ForwardIterator , typename OutputIterator , typename Predicate > | |
void | closedGrahamScanFromAnyPoint (const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate) |
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP) in linear-time. More... | |
template<typename ForwardIterator , typename OutputIterator , typename Predicate , typename PolarComparator > | |
void | grahamConvexHullAlgorithm (const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate, PolarComparator &aPolarComparator) |
Procedure that retrieves the vertices of the convex hull of a set of 2D points given by the range [ itb , ite ). This procedure follows the well-known Graham's algorithm [Graham, 1972 : [63]]. More... | |
template<typename ForwardIterator , typename OutputIterator , typename Predicate , typename PolarComparator > | |
void | grahamConvexHullAlgorithm (const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate) |
Procedure that retrieves the vertices of the convex hull of a set of 2D points given by the range [ itb , ite ). This procedure follows the well-known Graham's algorithm [Graham, 1972 : [63]]. More... | |
template<typename ForwardIterator , typename OutputIterator , typename Predicate > | |
void | andrewConvexHullAlgorithm (const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate) |
Procedure that retrieves the vertices of the hull of a set of 2D points given by the range [ itb , ite ). This procedure follows the well-known monotone-chain algorithm due to [Andrew, 1979 : [6]]. More... | |
template<typename ForwardIterator > | |
double | computeHullThickness (const ForwardIterator &itb, const ForwardIterator &ite, const ThicknessDefinition &def) |
Procedure to compute the convex hull thickness given from different definitions (Horizontal/vertical or Euclidean distances). It takes as input the vertices of the hull given by the range [itbn, ite). The procedure applies the classic rotating caliper to recover all anti-podal pairs. More... | |
template<typename ForwardIterator , typename TInputPoint > | |
double | computeHullThickness (const ForwardIterator &itb, const ForwardIterator &ite, const ThicknessDefinition &def, TInputPoint &antipodalEdgeP, TInputPoint &antipodalEdgeQ, TInputPoint &antipodalVertexR) |
Procedure to compute the convex hull thickness given from different definitions (Horizontal/vertical or Euclidean distances). It takes as input the vertices of the hull given by the range [itbn, ite). The procedure applies the classic rotating caliper to recover all anti-podal pairs. More... | |
template<typename TInputPoint > | |
double | getAngle (const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, const TInputPoint &d) |
template<typename TInputPoint > | |
bool | isCoLinearOpp (const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, const TInputPoint &d) |
template<typename TInputPoint > | |
double | getThicknessAntipodalPair (const TInputPoint &p, const TInputPoint &q, const TInputPoint &r, const ThicknessDefinition &def) |
template<typename TInputPoint > | |
double | computeHProjDistance (const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, bool &isInside) |
template<typename TInputPoint > | |
double | computeVProjDistance (const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, bool &isInside) |
template<typename TInputPoint > | |
double | computeEuclideanDistance (const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, bool &isInside) |
template<typename ForwardIterator , typename OutputIterator , typename Functor > | |
void | melkmanConvexHullAlgorithm (const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, Functor &aFunctor) |
Procedure that retrieves the vertices of the hull of a set of 2D points given by the range [ itb , ite ). This procedure follows the well-known Melkman algorithm [Melkman, 1979 : [89]]. More... | |
Variables | |
constexpr double | angleTolerance = 1e-6 |
Hull2D namespace gathers useful functions to compute and return the convex hull or the alpha-shape of a range of 2D points.
The 2 thickness definitions.
Enumerator | |
---|---|
HorizontalVerticalThickness | |
EuclideanThickness |
Definition at line 78 of file Hull2DHelpers.h.
void DGtal::functions::Hull2D::andrewConvexHullAlgorithm | ( | const ForwardIterator & | itb, |
const ForwardIterator & | ite, | ||
OutputIterator | res, | ||
const Predicate & | aPredicate | ||
) |
Procedure that retrieves the vertices of the hull of a set of 2D points given by the range [ itb , ite ). This procedure follows the well-known monotone-chain algorithm due to [Andrew, 1979 : [6]].
itb | begin iterator |
ite | end iterator |
res | output iterator used to export the retrieved points |
aPredicate | any ternary predicate |
ForwardIterator | a model of forward and readable iterator |
OutputIterator | a model of incrementable and writable iterator |
Predicate | a model of ternary predicate |
void DGtal::functions::Hull2D::buildHullWithAdaptedStack | ( | Stack | aStack, |
const ForwardIterator & | itb, | ||
const ForwardIterator & | ite, | ||
const Predicate & | aPredicate | ||
) |
Procedure that calls Hull2D::buildHullWithStack on a copy of the stack object used to retrieved the hull vertices. Useful when the first argument is a stack adapter returned by a function: it must be copied before being passed by reference in Hull2D::buildHullWithStack.
aStack | stack copy |
itb | begin iterator |
ite | end iterator |
aPredicate | predicate |
Stack | a model of CStack |
ForwardIterator | a model of forward and readable iterator |
Predicate | a model of ternary predicate |
void DGtal::functions::Hull2D::buildHullWithStack | ( | Stack & | aStack, |
const ForwardIterator & | itb, | ||
const ForwardIterator & | ite, | ||
const Predicate & | aPredicate | ||
) |
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP) in linear-time. This technique is called Sklansky's scan, Graham's scan or 3-coins algorithm.
It works for all WEVP [Toussaint and Avis, 1982 : [117]].
aStack | reference to the stack of retrieved vertices |
itb | begin iterator |
ite | end iterator |
aPredicate | predicate |
Stack | a model of CStack |
ForwardIterator | a model of forward and readable iterator |
Predicate | a model of ternary predicate |
void DGtal::functions::Hull2D::closedGrahamScanFromAnyPoint | ( | const ForwardIterator & | itb, |
const ForwardIterator & | ite, | ||
OutputIterator | res, | ||
const Predicate & | aPredicate | ||
) |
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP) in linear-time.
NB: We do not assume that the starting point of the polygon is an extremal point like in Hull2D::closedGrahamScanFromVertex
itb | begin iterator |
ite | end iterator |
res | output iterator used to export the retrieved points |
aPredicate | any ternary predicate |
ForwardIterator | a model of forward and readable iterator |
OutputIterator | a model of incremental and writable iterator |
Predicate | a model of ternary predicate |
void DGtal::functions::Hull2D::closedGrahamScanFromVertex | ( | const ForwardIterator & | itb, |
const ForwardIterator & | ite, | ||
OutputIterator | res, | ||
const Predicate & | aPredicate | ||
) |
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP) in linear-time.
itb | begin iterator |
ite | end iterator |
res | output iterator used to export the retrieved points |
aPredicate | any ternary predicate |
ForwardIterator | a model of forward and readable iterator |
OutputIterator | a model of incremental and writable iterator |
Predicate | a model of ternary predicate |
double DGtal::functions::Hull2D::computeEuclideanDistance | ( | const TInputPoint & | a, |
const TInputPoint & | b, | ||
const TInputPoint & | c, | ||
bool & | isInside | ||
) |
Computes the euclidean distance a point c according to the segment [a, b]. (i.e the distance between c and its projected point on [a,b].
[in] | a | one point of the segment. |
[in] | b | a second point of the segment. |
[in] | c | the point for which the vertical distance is computed. |
[out] | isInside | indicates if the projected point is inside the segment or not. |
double DGtal::functions::Hull2D::computeHProjDistance | ( | const TInputPoint & | a, |
const TInputPoint & | b, | ||
const TInputPoint & | c, | ||
bool & | isInside | ||
) |
Computes the horizontal distance a point according
to the segment [ a , b ]. (i.e the horizontal projection distance of on
[ a , b ]).
[in] | a | one point of the segment. |
[in] | b | a second point of the segment. |
[in] | c | the point for which the horizontal distance is computed. |
[out] | isInside | indicates if the projected point is inside the segment or not. |
double DGtal::functions::Hull2D::computeHullThickness | ( | const ForwardIterator & | itb, |
const ForwardIterator & | ite, | ||
const ThicknessDefinition & | def | ||
) |
Procedure to compute the convex hull thickness given from different definitions (Horizontal/vertical or Euclidean distances). It takes as input the vertices of the hull given by the range [itbn, ite). The procedure applies the classic rotating caliper to recover all anti-podal pairs.
Typical use:
[in] | itb | begin iterator on the convex hull points. |
[in] | ite | end iterator on the convex hull points. |
[in] | def | definition of the thickness used in the estimation (i.e HorizontalVerticalThickness or EuclideanThickness) |
Referenced by convexHull(), and testConvexHullCompThickness().
double DGtal::functions::Hull2D::computeHullThickness | ( | const ForwardIterator & | itb, |
const ForwardIterator & | ite, | ||
const ThicknessDefinition & | def, | ||
TInputPoint & | antipodalEdgeP, | ||
TInputPoint & | antipodalEdgeQ, | ||
TInputPoint & | antipodalVertexR | ||
) |
Procedure to compute the convex hull thickness given from different definitions (Horizontal/vertical or Euclidean distances). It takes as input the vertices of the hull given by the range [itbn, ite). The procedure applies the classic rotating caliper to recover all anti-podal pairs.
Typical use:
[in] | itb | begin iterator on the convex hull points. |
[in] | ite | end iterator on the convex hull points. |
[in] | def | definition of the thickness used in the estimation (i.e HorizontalVerticalThickness or EuclideanThickness) |
[out] | antipodalEdgeP | one point of the antipodal edge associated to the minimal value of convex hull thickness. |
[out] | antipodalEdgeQ | one point of the antipodal edge associated to the minimal value of convex hull thickness. |
[out] | antipodalVertexR | the vertex of the antipodal pair associated to the minimal value of convex hull thickness. |
double DGtal::functions::Hull2D::computeVProjDistance | ( | const TInputPoint & | a, |
const TInputPoint & | b, | ||
const TInputPoint & | c, | ||
bool & | isInside | ||
) |
Computes the vertical distance a point according
to the segment [a, b]. (i.e the vertical projection distance of on
[a,b].
[in] | a | one point of the segment. |
[in] | b | a second point of the segment. |
[in] | c | the point for which the vertical distance is computed. |
[out] | isInside | indicates if the projected point is inside the segment or not. |
|
inline |
Computes the angle between the line (a,b) and (c,d)
[in] | a | one of point defining the first line. |
[in] | b | a second point defining the first line. |
[in] | c | a third point defining the second line. |
[in] | d | a third point defining the second line. |
double DGtal::functions::Hull2D::getThicknessAntipodalPair | ( | const TInputPoint & | p, |
const TInputPoint & | q, | ||
const TInputPoint & | r, | ||
const ThicknessDefinition & | def | ||
) |
Computes the thickness of an anti podal pair (represented by the segment [ p , q ] and vertex r) according to the given distance def definition.
If the distance definition is HorizontalVerticalThickness, it returns the minimal distance between the vertical/horizontal projection of r on ( p , q ).
If the distance definition is EuclideanThickness, it returns the distance between r and its projection on the line ( p ,q ).
[in] | p | the first point of the edge anti podal pair. |
[in] | q | the second point of the edge anti podal pair. |
[in] | r | the vertex of the anti podal pair. |
[in] | def | definition of the thickness used in the estimation (i.e HorizontalVerticalThickness or EuclideanThickness). |
Referenced by testConvexHullCompThickness().
void DGtal::functions::Hull2D::grahamConvexHullAlgorithm | ( | const ForwardIterator & | itb, |
const ForwardIterator & | ite, | ||
OutputIterator | res, | ||
const Predicate & | aPredicate | ||
) |
Procedure that retrieves the vertices of the convex hull of a set of 2D points given by the range [ itb , ite ). This procedure follows the well-known Graham's algorithm [Graham, 1972 : [63]].
itb | begin iterator |
ite | end iterator |
res | output iterator used to export the retrieved points |
aPredicate | any ternary predicate |
ForwardIterator | a model of forward and readable iterator |
OutputIterator | a model of incremental and writable iterator |
Predicate | a model of ternary predicate |
void DGtal::functions::Hull2D::grahamConvexHullAlgorithm | ( | const ForwardIterator & | itb, |
const ForwardIterator & | ite, | ||
OutputIterator | res, | ||
const Predicate & | aPredicate, | ||
PolarComparator & | aPolarComparator | ||
) |
Procedure that retrieves the vertices of the convex hull of a set of 2D points given by the range [ itb , ite ). This procedure follows the well-known Graham's algorithm [Graham, 1972 : [63]].
itb | begin iterator |
ite | end iterator |
res | output iterator used to export the retrieved points |
aPredicate | any ternary predicate |
aPolarComparator | any polar comparator |
ForwardIterator | a model of forward and readable iterator |
OutputIterator | a model of incremental and writable iterator |
Predicate | a model of ternary predicate |
PolarComparator | a model of CPolarPointComparator2D. |
|
inline |
Determine if the two vectors (a,b) and (c,d) are co linear from opposite directions
[in] | a | one of point defining the first line. |
[in] | b | a second point defining the first line. |
[in] | c | a third point defining the second line. |
[in] | d | a third point defining the second line. |
void DGtal::functions::Hull2D::melkmanConvexHullAlgorithm | ( | const ForwardIterator & | itb, |
const ForwardIterator & | ite, | ||
OutputIterator | res, | ||
Functor & | aFunctor | ||
) |
Procedure that retrieves the vertices of the hull of a set of 2D points given by the range [ itb , ite ). This procedure follows the well-known Melkman algorithm [Melkman, 1979 : [89]].
itb | begin iterator |
ite | end iterator |
res | output iterator used to export the retrieved points |
aFunctor | aFunctor |
ForwardIterator | a model of forward and readable iterator |
OutputIterator | a model of incrementable and writable iterator |
Functor | a model of COrientationFunctor2 |
void DGtal::functions::Hull2D::openGrahamScan | ( | const ForwardIterator & | itb, |
const ForwardIterator & | ite, | ||
OutputIterator | res, | ||
const Predicate & | aPredicate | ||
) |
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP) in linear-time.
itb | begin iterator |
ite | end iterator |
res | output iterator used to export the retrieved points |
aPredicate | any ternary predicate |
ForwardIterator | a model of forward and readable iterator |
OutputIterator | a model of incremental and writable iterator |
Predicate | a model of ternary predicate |
void DGtal::functions::Hull2D::updateHullWithAdaptedStack | ( | Stack | aStack, |
const Point & | aNewPoint, | ||
const Predicate & | aPredicate | ||
) |
Procedure that calls Hull2D::updateHullWithStack on a copy of the stack object used to retrieved the hull vertices. Useful when the first argument is a stack adapter returned by a function: it must be copied before being passed by reference in Hull2D::updateHullWithStack.
aStack | stack copy |
aNewPoint | new point |
aPredicate | point predicate |
Stack | a model of CStack |
Point | a model of point |
Predicate | a model of ternary predicate |
void DGtal::functions::Hull2D::updateHullWithStack | ( | Stack & | aStack, |
const Point & | aNewPoint, | ||
const Predicate & | aPredicate | ||
) |
Procedure that updates the hull when an extra point aNewPoint is considered: while the last three consecutive points, ie. aNewPoint and the last two points of the container are not oriented such that the predicate aPredicate returns 'true',
the last point of the container is removed.
aStack | reference to the stack of retrieved vertices |
aNewPoint | new point |
aPredicate | point predicate |
Stack | a model of CStack |
Point | a model of point |
Predicate | a model of ternary predicate |
|
constexpr |
Definition at line 76 of file Hull2DHelpers.h.