2

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.

Vahid
  • 125
  • 12
  • I'm not that familiar with CGAL, so I don't know how easy it will be to implement a ray-tracing and ray-collision algorithm there. If that is hard, and performance is not critical, then if a point is inside an alpha shape, then alpha shape of the original point set + the query point should be the same as the original alpha shape, and you might be able to check this "equality". – triple_r Jul 15 '14 at 18:14
  • Thanks for your reply. Actually, the performance is very critical since I need to repeat this procedure at each time step, and there may be quite large numbers of points in my data set (hundreds of thousands or more). – Vahid Jul 15 '14 at 18:25

2 Answers2

4

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
sloriot
  • 6,070
  • 18
  • 27
  • Thanks for your useful answer. currently, I am only using the "Alpha_shapes_3" to construct the concave surface. Does this mean that I need to first generate a triangular grid within the entire volume (covered by the concave surface) in order to be able to use the "locate" function in "Traiangulation_3"? I am a new CGAL user with basic C++ experience, so this confuses me a little bit. – Vahid Jul 15 '14 at 20:15
  • Alpha_shape_3 inherits from the Triangulation_3. – sloriot Jul 16 '14 at 11:22
  • I tried to use the locate function by adding the following lines to the code, but I get errors in compilation. – Vahid Jul 18 '14 at 21:21
  • `typedef CGAL::Alpha_shape_3 Alpha_shape_3;` `typedef Alpha_shape_3::Cell_handle Cell_handle;` `typedef Alpha_shape_3::Locate_type Locate_type;` `Point query_point(1.0,1.0,1.0);` `int li, lj;` `Locate_type lt;` `Cell_handle ch = Alpha_shape_3::locate(query_point, lt, li, lj);` `assert( lt == OUTSIDE_AFFINE_HULL );` – Vahid Jul 18 '14 at 21:22
  • Alpha_shape_3::OUTSIDE_AFFINE_HULL – sloriot Jul 19 '14 at 08:31
  • I had success this way: with `Alpha_shape_3 as(...);` and having set `as.set_alpha(alpha);` you can do `Alpha_shape_3::Classification_type cl = as.classify(Point(x,y,z));`, `cl` will be in [0, 1, 2, 3, corresponding to exterior, singular, regular, interior](http://doc.cgal.org/latest/Alpha_shapes_3/classCGAL_1_1Alpha__shape__3.html#ae887e9ecdaca28790f6ccdd73b84e40c) – Raketenolli Jul 19 '17 at 13:24
1

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.

Logicrat
  • 4,438
  • 16
  • 22
  • It seems an interesting approach for a convex hull, thanks. However, in my case I have a concave hull which could include more than one volume (unconnected sections in the space) or more than two triangles whose XY surround the query point. I guess this algorithm will not work in such a case. – Vahid Jul 15 '14 at 19:33
  • My bad, I misread "concave" as "convex" in your original question. However, the basic logic still applies, although it is more complex. You'd have to find all surrounding triangles in 2D. Then, if the number of those triangles either above or below your point on the Z axis is odd, the point is inside one of the volumes, in particular, the one containing the triangles whose Z values are closest in either direction to the test point. – Logicrat Jul 16 '14 at 10:56