How to get all the points inside a convex hull?

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view

How to get all the points inside a convex hull?

I'd like to find the center of the inner hole of this planar surface:


To do this, I have computed the convex hull of this point cloud, which gives
me this:

Now I'd like to subtract all the points that are inside the convex hull with
the original point cloud. In this way, I'd obtain the inner hole, and I
could compute its centroid.

But the problem is that the convex hull returns only the boundaries, not all
the points inside it. How could I achieve this?


Sent from:
[hidden email] /
Reply | Threaded
Open this post in threaded view

Re: How to get all the points inside a convex hull?

This post was updated on .
maybe I am missing something, but if you subtract all points within the
hull, then you would indeed end up with your hole. BUT, your hole does not
contain any point information, therefore you would end up with nothing.

Idea 1:
If you calculate the centroid of you original point cloud you should get a
fairly good estimate of the centroid of the hole. Have you done this and
added this point to the original cloud for visualisation?

Idea 2:
Alternatively, you can, let say, "invert" your point cloud. And i think this
is what you had in mind with your original idea (but you were missing the
fact that you would end up with no points at all).
So to invert your point cloud plane do the following:

1. obtain the plane equation of your input point cloud
2. using said equation to generate a plane with the dimensions of your input
plane using a dense point distance (kind of depends of the scale of your
input), e.g within the distance of 0-1 and 0-3 meters make a point every
(e.g. 0.2m) in all directions. Note: if you make his value too small you can
end up with a huge (>2^6 points) new point cloud. Depends of course on the
actual size of your surface plane.
- this will yield you a new plane that is at the same location as the your
original one BUT is fully filled with points.
3. now you can look at your new point cloud as a point cloud full of query
- for each point location in your new point cloud do a kdtree search with
radius K (depends on your input and point distance) in your original cloud.
- if you find a point in this given radius, you can delete this one from
your new plane point cloud, else you keep the point.
4. So you will be left with the hole of the original point cloud but filled
with points.
5. now simply calculate the centroid of all remaining points.

But you should try "Idea 1" first. "Idea 2" will definitely work for all square or rectangular planes but its
much more work to realize.

Sent from:
_______________________________________________ /