GitHub

Hulls

Meshes.hull — Function
hull(points, method)

Compute the hull of points with given method.

source
Meshes.GrahamScan — Type
GrahamScan()

Compute the convex hull of a set of points or geometries using the Graham's scan algorithm. See [https://en.wikipedia.org/wiki/Grahamscan] (https://en.wikipedia.org/wiki/Grahamscan).

The algorithm has complexity O(n*log(n)) where n is the number of points.

References

  • Cormen et al. 2009. [Introduction to Algorithms] (https://mitpress.mit.edu/books/introduction-algorithms-third-edition)
source
Meshes.MoreiraMarch — Type
MoreiraMarch(k=3)

Compute the concave hull of a set of points or geometries using Moreira's march algorithm. k is the minimum number of nearest neighbors in the interval (2, n) where n is the number of unique points in the input.

The algorithm increases k until a valid hull is found, or until k reaches n - 1. It has complexity O(k*n*h) where h is the number of points in the hull, per attempt. The number of attempts is bounded above by n - 1 - k.

References

  • Moreira, A. & Santos, M. Y. 2007. [Concave hull: a k-nearest-neighbours approach for the computation of the region occupied by a set of points] (https://www.semanticscholar.org/paper/Concave-hull:-A-k-nearest-neighbours-approach-for-a-Moreira-Santos/319a3450f9909043d46eb7ceb4299efceb984d4f)
source
pset = PointSet(rand(Point, 100, crs=Cartesian2D))
chul = convexhull(pset)

fig = Mke.Figure(size = (800, 400))
viz(fig[1,1], chul)
viz!(fig[1,1], pset, color = :black)
fig
Example block output
box  = Box((-1, -1), (0, 0))
ball = Ball((0, 0), (1))
gset = GeometrySet([box, ball])
chul = convexhull(gset)

fig = Mke.Figure(size = (800, 400))
viz(fig[1,1], chul)
viz!(fig[1,1], boundary(box), color = :gray)
viz!(fig[1,1], boundary(ball), color = :gray)
fig
Example block output