CODEWITHSUNDEEP
algorithm3dmeshpoint-clouds
David
David

Reputation: 13580

What algorithms exist for finding a bounding surface to a set of points?

Suppose you have a point cloud, and you want a surface that wraps those points to enclose them all, and wrap them fairly tightly so it intersects with the outer points in the cloud - how do you generate this wrapped surface? That is, where some or many points may be inside the volume and so the surface does not need to intersect them, only enclose them, but the surface should be a good fit for the "outside" layer of points.

(I'm aware of triangulation algorithms (such as Delaunay) for fitting a mesh through - I think - all points in a set, but I don't think that algorithm will work unless there's a good way to discard all but the outer shell of points. Feel free to point out approaches I'm missing here, too!)

What algorithms (or even search keywords beyond "mesh", "fit", "wrap" "point cloud" etc) should I look for?

Upvotes: 4

Views: 3296

Answers (3)

user1054186
user1054186

Reputation:

You can use TetGen to compute the convex hull or, if needed, a surface triangulation in the case your point set is not convex.

I am not sure this is useful to you, Mathematica has a TetGenLink interface to TetGen.

Upvotes: 1

Sirko
Sirko

Reputation: 74036

I think, what you are searching for is a convex hull.

For algorithms to compute it, take a look here.

Upvotes: 2

templatetypedef
templatetypedef

Reputation: 372724

I think that you're looking for a convex hull algorithm. The convex hull is the shape you get if you were to wrap a set of points in some sort of wrapping paper, leaving the outermost boundary. I may be misinterpreting your question, but this sounds like exactly what you're looking for.

Hope this helps!

Upvotes: 4

Related Questions