The “point in polygon” or “point in polyhedron” is a classic computer graphics problem. The goal is to determine whether a given point is inside a polygon (in 2D) or a polyhedron (in 3D).

One solution to the problem is shooting a ray originating from the said point to an arbitrary direction and determine the number of intersections of the ray with the polygon or polyhedron. If the ray intersects the shape an odd number of times, then the point is inside the shape. Otherwise it is outside the shape.

There are problems associated with this approach. An important edge case is when the point is on the surface of the shape. Also, it is commonly advisable to shoot multiple rays instead of just one, and then do a majority voting.

Luckily, in CGAL the point in polyhedron test is very simple and you don’t have to worry about the edge cases! You can do the test using the `Side_of_triangle_mesh`

class. A code snippet is shown below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <CGAL/Simple_cartesian.h> #include <CGAL/AABB_tree.h> #include <CGAL/AABB_traits.h> #include <CGAL/Polyhedron_3.h> #include <CGAL/boost/graph/graph_traits_Polyhedron_3.h> #include <CGAL/AABB_face_graph_triangle_primitive.h> #include <CGAL/algorithm.h> #include <CGAL/Side_of_triangle_mesh.h> typedef CGAL::Simple_cartesian<double> K; typedef K::Point_3 Point; typedef CGAL::Polyhedron_3<K> Polyhedron; typedef CGAL::AABB_face_graph_triangle_primitive<Polyhedron> Primitive; typedef CGAL::AABB_traits<K, Primitive> Traits; typedef CGAL::AABB_tree<Traits> Tree; typedef CGAL::Side_of_triangle_mesh<Polyhedron, K> Point_inside; bool pointInside(Polyhedron &polyhedron, Point &query) { // Construct AABB tree with a KdTree Tree tree(faces(polyhedron).first, faces(polyhedron).second, polyhedron); tree.accelerate_distance_queries(); // Initialize the point-in-polyhedron tester Point_inside inside_tester(tree); // Determine the side and return true if inside! return inside_tester(query) == CGAL::ON_BOUNDED_SIDE; } |

You can also determine whether the point is on the surface of the polyhedron or not.

## 1 comment

Thanks for this useful explanation.

May I ask you to show an application of the code for a polyhedron and a given point?