Hulls
|
Страница в процессе перевода. |
#
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
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
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