I have a set of 2D points of a known density I want to mesh by taking the holes in account. Basically, given the following input:

I want something link this:

I tried PCL ConcaveHull, but it doens't handle the holes and splitted mesh very well.

I looked at CGAL Alpha shapes, which seems to go in the right direction (creating a polygon from a point cloud), but I don't know how to get triangles after that.

I though of passing the resulting polygons to a constrained triangulation algorithm and mark domains, but I didn't find how to get a list of polygons.

CodePudding user response：

The resulting triangulated polygon is about a two step process at the least. First you need to triangulate your 2D points (using something like a Delaunay2D algorithm). There you can set the maximum length for the triangles and get the the desired shape. Then you can decimate the point cloud and re-triangulate. Another option is to use the convex hull to get the outside polygon, then extract the inside polygon through a TriangulationCDT algorithm, the apply some PolygonBooleanOperations, obtain the desired polygon, and finaly re-triangulate.

I suggest you look into the Geometric Tools library and specifically the Geometric Samples. I think everything you need is in there, and is much less library and path heavy than CGAL (the algorithms are not free for this type of work unless is a school project) or the PCL (I really like the library for segmentation, but their triangulation breaks often and is slow).

If this solves your problem, please mark it as your answer. Thank you!