Calculates the convex hull of a given set of points

Calculates the convex hull of a given set of points. A monotone chain is used as an algorithm.

Info

Given a set of points, the convex hull is a subset of points that form a polygon that encloses all points. The implemented algorithm is Andrew’s monotone chain algorithm, which has an efficient O(n log n) runtime.

(Maonus, [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0), via Wikimedia Commons)

Usage

The library consists of the convexHull function, which takes a generic list of objects and accessor function for the x and y coordinates, and returns the objects forming a convex hull.

import 'package:vector_math/vector_math_64.dart';
import 'package:convex_hull/convex_hull.dart';

// you can use an iterable of any object. Here,
// Vector2 is used.
const points = <Vector2>[
    Vector2(1, 2),
    Vector2(3.2, 1),
    Vector2(1.3, 1),
]
// specify what should be considered as the x and y coordinate
List<Vector2> hull = convexHull<Vector2>(points, x: (e) => e.x, y: (e) => e.y);

Download source code on the GitHub repository

Calculates the convex hull of a given set of points.
https://github.com/defo10/convex-hull
2 forks.
3 stars.
1 open issues.

Recent commits:

• add keepCollinear parameter, Daniel
• take into account orientation of coordinate system, Daniel
• use accessor functions instead of pre-defined object, Daniel
• use Iterable instead of List., Daniel
• add more docs.., Daniel