3

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.

roamcel
  • 645
  • 1
  • 8
  • 17
  • 1
    You might want to look at [this question](http://stackoverflow.com/questions/83593/is-there-an-efficient-algorithm-to-generate-a-2d-concave-hull) for the 2D problem. There are some interesting pointers there that might help you on your search. – Bart Nov 05 '11 at 22:04

1 Answers1

4

'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

James Moughan
  • 413
  • 2
  • 3