The convex hull of a set of points: its vertices (counterclockwise), their number, its area and perimeter.
\operatorname{conv}(S) = \{\textstyle\sum \lambda_i p_i : \lambda_i \ge 0, \sum\lambda_i = 1\}
Inputs
points the points: x1 y1, x2 y2, ... vector
Returns
hull hull vertices [x, y], counterclockwise from the smallest x (then smallest y)n_vertices number of hull verticesarea area of the hullperimeter perimeter of the hull
Applies when
- at least 3 points, not all collinear, at most 5000
- points on a hull edge between two vertices are not vertices
- repeated points count once
Example
m.ask("Find the convex hull of the points (0, 0), (2, 1), (4, 0), (3, 3), (1, 2), (2, 4).")
→ hull = [[0.0, 0.0], [4.0, 0.0], [3.0, 3.0], [2.0, 4.0]], n_vertices = 4, area = 9, perimeter = 13.0486