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:

 

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

“Unresolved external symbol” Errors when Compiling CGAL 4.7 Under Windows with Visual Studio 2013

I spent hours trying to compile CGAL 4.7 with Visual Studio 2013. Everything compiled on the first try with Visual Studio 2010 but for some reason I was unable to get it working with VS2013. CMake would create the solution files just fine and was able to resolve everything. However, when I attempted to build the confiugured solution I would get lots of “unresolved external” errors like this:

unresolved external symbol "__declspec(dllimport) class boost::system::error_category const & __cdecl boost::system::generic_category(void)

I followed this guide to the letter. I was sure Boost was being discovered just fine. I had everything in my PATH. After a while I figured out what my problem was! Although I wanted to build 64-bit binaries, I was selecting Visual Studio 12 2013 as my generator!! I was skimming every time I was selecting it so I wasn’t paying attention! I should’ve in fact selected Visual Studio 12 2013 Win64 as my generator. Doing that solved the problems.