CODEWITHSUNDEEP
c++cgalpoint-in-polygonconcave-hull
Vahid
Vahid

Reputation: 125

Determine if a point is interior or exterior to a 3D Alpha-shapes surface in CGAL

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

Answers (2)

sloriot
sloriot

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.

  • whatever simplex type, EXTERIOR is exterior, INTERIOR is interior.
  • If the point falls on an edge, REGULAR is on the boundary and SINGULAR depends whether what an isolated edge should be in your setting
  • If the points fall on a vertex, REGULAR is on the boundary and SINGULAR is depends whether an isolated input point should be in your setting

Upvotes: 4

Logicrat
Logicrat

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

Related Questions