#include <DGtal/geometry/tools/MelkmanConvexHull.h>
Aim: This class implements the on-line algorithm of Melkman for the computation of the convex hull of a simple polygonal line (without self-intersection) [Melkman, 1987: [46]].
This algorithm is based on a deque, which stores the vertices of the convex hull (for convenience, the first and last vertex contained in the deque are the same point). Since we assume that the input points form a simple polygonal line, a new point cannot be located in the cone formed by the first and last edges of the current convex hull. As a consequence, it is enough to update the convex hull by a Graham scan from the front and/or from the back of the deque; it is never required to remove/insert points in the middle of the container. See Convex hull and alpha-shape in the plane for more details.
Note that if the input points do not form a simple polygonal line, the behavior is not defined.
Definition at line 89 of file MelkmanConvexHull.h.
Type of predicate devoted to the backward scan
Definition at line 114 of file MelkmanConvexHull.h.
Type of iterator on the convex hull vertices
Definition at line 123 of file MelkmanConvexHull.h.
Type of predicate devoted to the forward scan
Definition at line 118 of file MelkmanConvexHull.h.
Type of orientation functor
Definition at line 106 of file MelkmanConvexHull.h.
Type of point
Definition at line 102 of file MelkmanConvexHull.h.
Self type
Definition at line 97 of file MelkmanConvexHull.h.
Consider a new point and possibly update the convex hull.
Begin iterator
clear the current content of the convex hull.
End iterator
Checks the validity/consistency of the object.
Assignement Operator
Reverse the convex hull container allowing to change the order of adding points from the front or from the back in reference to an input contour. Such a reverse is important to avoid wrong convexhull and to allow convex hull extension from two directions.
Writes/Displays the object on an output stream.
Predicate devoted to the backward scan
Definition at line 213 of file MelkmanConvexHull.h.
Deque container, which stores the vertices of the convex hull NB: the first and last point is the same.
Definition at line 209 of file MelkmanConvexHull.h.
Used to define a default functor to allow default constructor
Definition at line 221 of file MelkmanConvexHull.h.
first point used to reverse the convexhull container.
Definition at line 225 of file MelkmanConvexHull.h.
Predicate devoted to the forward scan
Definition at line 217 of file MelkmanConvexHull.h.