pub trait KNearestConcaveHull {
type Scalar: CoordNum;
// Required method
fn k_nearest_concave_hull(&self, k: u32) -> Polygon<Self::Scalar>;
}Expand description
Another approach for concave hull. This algorithm is based on a k nearest neighbours approach by Adriano Moreira and Maribel Santos.
The idea of the algorithm is simple:
- Find a point on a future hull (e. g. a point with the smallest Y coordinate).
- Find K nearest neighbours to the chosen point.
- As the next point on the hull chose one of the nearest points, that would make the largest left hand turn from the previous segment.
- Repeat 2-4.
In cases when the hull cannot be calculated for the given K, a larger value is chosen and calculation starts from the beginning.
In the worst case scenario, when no K can be found to build a correct hull, the convex hull is returned.
This algorithm is generally several times slower then the one used in the ConcaveHull trait, but gives better results and does not require manual coefficient adjustment.
The larger K is given to the algorithm, the more “smooth” the hull will generally be, but the longer calculation may take. If performance is not critical, K=3 is a safe value to set (lower values do not make sense for this algorithm). If K is equal or larger than the number of input points, the convex hull will be produced.