libpysal.cg.alpha_shape_auto

libpysal.cg.alpha_shape_auto(xys, step=1, verbose=False, return_radius=False, return_circles=False)

Computation of alpha-shape delineation with automated selection of alpha.

This method uses the algorithm proposed by Edelsbrunner, Kirkpatrick & Seidel (1983) to return the tightest polygon that contains all points in xys. The algorithm ranks every point based on its radius and iterates over each point, checking whether the maximum alpha that would keep the point and all the other ones in the set with smaller radii results in a single polygon. If that is the case, it moves to the next point; otherwise, it retains the previous alpha value and returns the polygon as shapely geometry. Note that this geometry may have holes.

Parameters:

xysndarray

Nx2 array with one point per row and coordinates structured as X and Y

stepint

[Optional. Default=1] Number of points in xys to jump ahead after checking whether the largest possible alpha that includes the point and all the other ones with smaller radii

verboseBoolean

[Optional. Default=False] If True, it prints alpha values being tried at every step.

Returns:

polyshapely.Polygon

Tightest alpha-shape polygon containing all points in xys

References

Edelsbrunner, H., Kirkpatrick, D., & Seidel, R. (1983). On the shape of

a set of points in the plane. IEEE Transactions on information theory, 29(4), 551-559.

Examples

>>> pts = np.array([[0, 1], [3, 5], [4, 1], [6, 7], [9, 3]])
>>> poly = alpha_shape_auto(pts)
>>> poly.bounds
(0.0, 1.0, 9.0, 7.0)
>>> poly.centroid.x, poly.centroid.y
(4.690476190476191, 3.4523809523809526)