Trait geo::algorithm::concave_hull::ConcaveHull

source ·

pub trait ConcaveHull {
    type Scalar: CoordNum;

    // Required method
    fn concave_hull(&self, concavity: Self::Scalar) -> Polygon<Self::Scalar>;
}

Expand description

Returns a polygon which covers a geometry. Unlike convex hulls, which also cover their geometry, a concave hull does so while trying to further minimize its area by constructing edges such that the exterior of the polygon incorporates points that would be interior points in a convex hull.

This implementation is inspired by https://github.com/mapbox/concaveman and also uses ideas from the following paper: www.iis.sinica.edu.tw/page/jise/2012/201205_10.pdf

Examples

use geo::{line_string, polygon};
use geo::ConcaveHull;

// a square shape
let poly = polygon![
    (x: 0.0, y: 0.0),
    (x: 4.0, y: 0.0),
    (x: 4.0, y: 4.0),
    (x: 0.0, y: 4.0),
];

// The correct concave hull coordinates
let correct_hull = line_string![
    (x: 4.0, y: 0.0),
    (x: 4.0, y: 4.0),
    (x: 0.0, y: 4.0),
    (x: 0.0, y: 0.0),
    (x: 4.0, y: 0.0),
];

let res = poly.concave_hull(2.0);
assert_eq!(res.exterior(), &correct_hull);