CGAL Point in Polyhedron Algorithm

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:

#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.