Function rgeometry::algorithms::convex_hull

source · [−]
pub fn convex_hull<T>(pts: Vec<Point<T>>) -> 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