3D contour of a list of points (concave hull)

问题:

I have a list of Vector3 points in c#, and I need to calculate the concave contour of these. There's really a lot of references around, especially for -convex- resolution (which I have successfully implemented already, thanks to graham's algorithm),

however, since my need is now to effectively compute a concave contour, I'm lost: wikipedia does list a lot of resources for convex calculation, but none for -concave-.

Anybody with math knowledge that can give me a lead on the available concave hull algorithms?

I have a concern for performance, too, so being able to benchmark the algorithm speed a priori would be very helpful.

Thanks.

回答1:

'Concave hull' is not a well-defined mathematical concept; there are many possible algorithms giving different reasonable results, which is why there are few resources on it. Try googling '3D alpha shapes' for something that might suit your needs, e.g. http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html