# Function rgeometry::algorithms::convex_hull[−][src]

pub fn convex_hull<T>(pts: Vec<Point<T, 2>>) -> Result<PolygonConvex<T>, Error> where    T: PolygonScalar,
Expand description

Convex hull of a set of points.

Graham scan algorithm for finding the smallest convex polygon which contains all the given points.

# Errors

Will return an error iff the input set contains less than three distinct points.

# Properties

• No points from the input set will be outside the returned convex polygon.
• All vertices in the convex polygon are from the input set.

# Time complexity

$O(n \log n)$

# Examples

let empty_set: Vec<Point<i32,2>> = vec![];
assert_eq!(
convex_hull(empty_set).err(),
Some(Error::InsufficientVertices))
Run
let dups = vec![Point::new([0,0])].repeat(3);
assert_eq!(
convex_hull(dups).err(),
Some(Error::InsufficientVertices))
Run
if let Ok(convex) = convex_hull(points) {
render_polygon(&convex);
}
Run