CGAL users discussion list

["Laurent Rineau (GeometryFactory)" <>]

Le lundi 12 mars 2012 23:37:12 Zohar a écrit :
> Maybe there's a better way, but I would construct a AABB tree for the
> polyhedron triangles. The I would find the closest triangle to the query
> point and use Kernel::BoundedSide_2() to determine if the point is on the
> bounded side of the triangle.

BoundedSide_2 is for Kernel::Triangle_2, that is 2D triangles, or more 
generally for 2D objects.

For the inside test of point 'p' and a polyhedron 'polyh', you may choose a 
random ray with source point 'p', and a random direction, and, using the 
AABB tree, query the number of intersections between the polyhedron and that 
ray. If the polyhedron is closed, then the point is inside the polyhedron if 
and only if the number of intersections between the ray and the polyhedron is 
odd.

Note that this method will give you random results if the point is exactly on 
the boundary of the polyhedron.

That is important that the direction of the ray is random, because the ray 
may 
intersect the border of facets of the polyhedron, and the number of 
intersections given by the AABB tree will not be the number of intersections 
with the polyhedron (because of multiplicity). But the probability of those 
degenerate cases, with a random ray, is zero¹.


¹) Given that floating point random generators are not true real random 
generators, the probability may be non-zero, but it is really small. To be 
sure you can shoot several rays instead of just one.

-- 
Laurent Rineau, PhD
R&D Engineer at GeometryFactory           http://www.geometryfactory.com/
Release Manager of the CGAL Project       http://www.cgal.org/