aerocaps.geom.tools.concave_hull

concave_hull(poly: ~numpy.ndarray) -> (<class 'numpy.ndarray'>, <class 'numpy.ndarray'>)

Gets the concave hull of points of a polygon. Has a worst-case time complexity of \(\mathcal{O}\left(3n^2 \right)\) but uses shapely.prepare for increased performance. Some algorithms exist that are \(\mathcal{O}\left( n \log{n} \right)\), but this algorithm seems to be more robust and is fast enough in many cases.

Parameters:

poly (numpy.ndarray) – Array of size \(2 \times N\) representing the polygon. Does not need to form a closed loop

Returns:

The vertices of the triangles as an \(N \times 3\) index array and the points of the triangles as an \(N \times 3\) float array

Return type:

numpy.ndarray, numpy.ndarray