Reputation: 125
I am using CGAL to create the concave hull of a set of 3D points using ex_alpha_shapes_3 example. Next, I would like to find out whether a point query in space is located within the surface created by the triangular concave hull faces (the output of ex_alpha_shapes_3 code) or not. A "point in polygon" technique should be useful for this purpose. I would appreciate it if anyone could help me with this problem.
Upvotes: 2
Views: 1594
Reputation: 6303
You can use the locate function and depending on the simplex the point fall on and the output of the function classify of the simplex you'll directly know if you're inside, outside or on the boundary.
Upvotes: 4
Reputation: 4468
I don't know about CGAL, but there are a few heuristics you can use given that your polyhedron is known to be convex. You can do a lot of the work in essentially 2D. You can use any axes, but let's assume we are working in the XY plane and momentarily ignoring the Z component. Since your shape is convex, there will generally only be two triangles whose XY coordinates surround the XY coordinates of your point. For any triangle, you can quickly determine if x[min] < x[point] < x[max] and likewise for y. If those tests fail, move on. If they succeed, a little further testing is needed to determine whether the point is actually inside the triangle. Once you have located 2 acceptable triangles, find the Z value for each triangle at the point's (X,Y). If the point's Z is between the Z values for the faces, then the point is inside the solid.
Upvotes: 1