convex_hull_xy

compas.geometry.convex_hull_xy(points, strict=False)

Computes the convex hull of a set of 2D points.

Parameters

points (sequence[point]) – XY(Z) coordinates of the points.

Returns

list[[float, float, 0.0]] – XY(Z) coordinates of vertices of the convex hull in counter-clockwise order, starting from the vertex with the lexicographically smallest coordinates.

Notes

Implements Andrew’s monotone chain algorithm 1. O(n log n) complexity.

References

1

Wiki Books. Algorithm Implementation/Geometry/Convex hull/Monotone chain. Available at: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain.

Examples

>>>