Function geo::algorithm::convex_hull::graham::graham_hull

source ·

pub fn graham_hull<T>(
    points: &mut [Coord<T>],
    include_on_hull: bool
) -> LineString<T>where
    T: GeoNum,

Expand description

The Graham’s scan algorithm to compute the convex hull of a collection of points. This algorithm is less performant than the quick hull, but allows computing all the points on the convex hull, as opposed to a strict convex hull that does not include collinear points.

§References

Graham, R.L. (1972). “An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set” (PDF).
Information Processing Letters. 1 (4): 132–133. doi:10.1016/0020-0190(72)90045-2