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

Perhaps you need to define 'best'. Also did you mean 3D k-sided polyhedron instead of polygon? — , Aug 09 '10 at 21:25
I guess it was a bit poorly worded, I'll edit it now. And I do mean polygon, because I am looking for a 2-D shape projected into 3-D — Xzhsh, Aug 09 '10 at 22:04

deinst · Accepted Answer · 2010-08-11T12:33:53.137

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.

score 0 · Answer 2 · answered May 07 '13 at 06:33

First of all you are to choose a representation for your mesh. In 2D, I implemented a Python concave hull algo using this representation: half-edge data structure.

Then, algorithm in 2D (you should adapt to 3D) can be close to alpha shape algorithm, by Edelbrunner.

score 0 · Answer 3 · edited May 23 '17 at 11:55

0

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.

edited May 23 '17 at 11:55

Community

1
1

answered Aug 10 '10 at 01:39

andand

17,134
11
53
79

It seems that the 2D case you linked to is more of the sparse point variety. In my case, for a simple 9 sided concave polygon, there may be around 40000 points. If I used the same algorithm, it seems that it would be wildly inefficient – Xzhsh Aug 10 '10 at 17:22

Simplified concave-hulls

3 Answers3