convex_hull

named_arrays.geometry.convex_hull(points, axis, axis_vertex='vertex', where=True)

Find the convex hull of a set of points: the smallest convex polygon which contains all of them.

The points along axis are reduced to the vertices of their hull, along the new axis axis_vertex, in counterclockwise order starting from the vertex with the least \(x\)-coordinate (the least \(y\)-coordinate among a tie). Every other axis of points is a batch axis, along which each set of points gets a hull of its own.

Hulls have different numbers of vertices, so every hull is padded to the number of vertices of the largest by repeating its last vertex, which leaves the polygon it describes unchanged. Points which lie on an edge of a hull, rather than at a corner, are not vertices of it, and neither are copies of a vertex, so the hull of points which all coincide is that one point. Points with a coordinate which is not finite, like NaN, are left out. A set with no points has a hull whose vertices are all NaN.

The vertices keep the unit of the \(x\)-coordinates, or of the \(y\)-coordinates if those have none, and the type of the coordinates if it is a floating-point type, or else are 64-bit floats.

The hull of each set is found with Andrew’s monotone chain algorithm, in \(O(n \log n)\) time for \(n\) points.

Parameters:

• points (AbstractCartesian2dVectorArray) – The points to find the hull of. Must have exactly the two components \(x\) and \(y\), which must be scalars that are not uncertain.

• axis (str | Sequence[str]) – The logical axis or axes along which the points of a single set vary.

• axis_vertex (str) – The name of the new logical axis along which the vertices of each hull vary. It may be the name of one of the axes in axis, which the points no longer vary along, but not of any other axis.

• where (bool | AbstractScalar) – Which of the points take part. Those for which it is False are left out of the hull.

Return type:

Cartesian2dVectorArray

Examples

Find the hull of a cloud of random points.

import matplotlib.pyplot as plt
import named_arrays as na

# Define a cloud of random points
axis = "point"
points = na.Cartesian2dVectorArray(
    x=na.random.normal(0, 1, shape_random={axis: 101}),
    y=na.random.normal(0, 2, shape_random={axis: 101}),
)

# Find the vertices of the hull of the points
hull = na.geometry.convex_hull(points, axis=axis)

# Plot the points and their hull
fig, ax = plt.subplots()
na.plt.scatter(points.x, points.y, ax=ax)
na.plt.fill(
    hull.x,
    hull.y,
    ax=ax,
    axis="vertex",
    facecolor="none",
    edgecolor="black",
);