COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Determining a non-convex hull

• Follow

```I have a 3D point cloud near the origin (0,0,0). All triples (x,y,z) are non-negative, which means that my points lie in the positive octant.

I know that the point cloud approximates a "concave" volume V, in the sense that the complement of V in the positive octant is convex.

How do I get the "concave" boundary of V, i.e., the convex hull of the complement of V?

The function convhull is not directly helpful of course. But is there a trick?
```
 0

```here is an idea: Any concave solid can be split summed as a collection of finite number of convex solids. I am personally unaware of any ways to do this.(I am sure something exists!). So I searched online and I found this on a different website:

If you asked me what I would use: it would be a brute force method of induction: I would start with four vertices and form a tetrahedron that contain no other points (choose 4 and then recurse if there are points that exist inside this, ignore the first choice thus avoiding unnecessary false edges). Such a construction should give rise to a tetrahedral solid that approximates the concave hull. I would like to shy away from answering the complexity of this algorithm.
```
 0

```Dear Jens,

is a concave hull well defined at all? I imagine the 2d case of 4 points on the corners of a square and an additional point in the center. What is the concave hull?

Jan
```
 0

2 Replies
752 Views

Similiar Articles:

7/25/2012 12:41:33 AM