Simplified concave-hulls

Question

Problem:

Given: n points that are strongly correlated to a 3d k-sided non-convex polygon, where n >> k

Find: the best fit concave-hull that matches the original geometry of the points

---

Attempted solutions:

Warning: pseudocode

segments = []
for each point in image:
    #segment points into planes via comparing approximate normals
    #actual implementation is more complicated
    findSegment(image,point)
for each segment in image:
    #transform coordinate system to be a 
    #2D-plane perpendicular to the normal of segment
    transform(segment, segment.normal)
    edges = findEdges(segment)
    polygonHull = reconstructPolygon(edges)
    #transform back to original coordinate system
    transform(segment, segment.normal)

---

Example:

 ___
|   |               |
|    \__    ==>     |   ___
|       |           |__/  /_____
|_______|          /  /   \_
                  /  /_____/
                 /

Input would be simply a high density point cloud that is approximately uniformly distributed random points within the polygon plane, with a bit of noise.

Output would be the vertices of the polygon in 3d points.

---

My question is, is there a better way to approach this problem? The problem with the above solution is that the points can be noisy. Also, rasterization of the points into 2d and then preforming a edge find is pretty costly.

Any pointers would be great. Thanks in advance

Answer 1

It sounds like you want to compute the concave hull of a collection of points in 3-space projected onto a plane. The 2D case is discussed in some detail here.

Answer 2

If your concave corners are not too sharp, I might try doing a 3d Delaunay triangulation on the point set. The Voronoi regions of the points on the boundary will tend to be either infinite or much longer than the ones on the interior. Similary, cells on the boundary that are associated with a single face of the polyhedron will tend to be aligned in a direction nearly normal to the face that they are associated with, in that they will all be long and thin and their long axes will be nearly parallel and pointing out of the polygon. In kinda sorta quasi-pseudocode

Compute Delaunay triangulation
Collect long thin Voronoi regions
Partition the Voronoi regions into clusters that are nearby and nearly parallel.
Create faces normal to the axes of the Voronoi regions. 

Edit Now I see that you just want a polygon. The above approach works, but it is probably best to do it in two steps. First find the plane in which the polygon lies, doing a least squares fit of a small sample of the points is probably good enough. Project the points onto a plane (This is pretty much what you have been doing) then compute the 2d Delaunay triangulation to find the edge points and continue as above.