Hulls

Страница в процессе перевода.

# Meshes.hull — Function

hull(points, method)

Compute the hull of points with given method.

# Meshes.convexhull — Function

convexhull(object)

Convex hull of object.

# Meshes.HullMethod — Type

HullMethod

A method for computing hulls of geometries.

# 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/Graham_scan.

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

References

Cormen et al. 2009. Introduction to Algorithms

# Meshes.JarvisMarch — Type

JarvisMarch()

Compute the convex hull of a set of points or geometries using the Jarvis’s march algorithm. See https://en.wikipedia.org/wiki/Giftwrappingalgorithm.

The algorithm has complexity O(n*h) where n is the number of points and h is the number of points in the hull.

References

Jarvis 1973. On the identification of the convex hull of a finite set of points in the plane

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

wwosAAAAABLNb3EAAAAAJJoACwAAAIBEE2ABAAAAkGgCLAAAAAASTYAFAAAAQKIJsAAAAABINAEWAAAAAIkmwAIAAAAg0QRYAAAAACSaAAsAAACARBNgAQAAAJBoAiwAAAAAEk2ABQAAAECiCbAAAAAASDQBFgAAAACJJsACAAAAINEEWAAAAAAkmgALAAAAgEQTYAEAAACQaAIsAAAAABJNgAUAAABAogmwAAAAAEg0ARYAAAAAiSbAAgAAACDRBFgAAAAAJJoACwAAAIBEE2ABAAAAkGgCLAAAAAASTYAFAAAAQKIJsAAAAABINAEWAAAAAIkmwAIAAAAg0QRYAAAAACSaAAsAAACARPsf0XDNgdMpSEgAAAAASUVORK5CYII=

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

MxnPvPNb35zzpw5ZfokAMZg1apVa9euXbFixXANuPQeI8nzvErXAAAAAAAAAAyL39IBAAAAAABQ1QiwAAAAAAAAUNUIsAAAAAAAAFDVCLAAAAAAAABQ1QiwAAAAAAAAUNUIsAAAAAAAAFDVCLAAAAAAAABQ1QiwAAAAAAAAUNUIsAAAAAAAAFDVCLAAAAAAAABQ1QiwAAAAAAAAUNUIsAAAAAAAAFDVCLAAAAAAAABQ1QiwAAAAAAAAUNUIsAAAAAAAAFDVCLAAAAAAAABQ1QiwAAAAAAAAUNUIsAAAAAAAAFDVCLAAAAAAAABQ1QiwAAAAAAAAUNUIsAAAAAAAAFDVCLAAAAAAAABQ1QiwAAAAAAAAUNUIsAAAAAAAAFDVCLAAAAAAAABQ1QiwAAAAAAAAUNUIsAAAAAAAAFDVCLAAAAAAAABQ1QiwAAAAAAAAUNUIsAAAAAAAAFDVCLAAAAAAAABQ1QiwAAAAAAAAUNUIsAAAAAAAAFDVCLAAAAAAAABQ1f4fWa21J8EcXV8AAAAASUVORK5CYII=