CGAL users discussion list

[Bernd Gärtner <>]

If the polyhedron is convex, another option would be to use the CGAL LP 
solver. You can write the point containment test as a linear program, 
where each facet defines a linear inequality constraint, see 
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/QP_solver/Chapter_main.html. 
There is an example (convex hull containment) performing such a test if 
the polyhedron is given as a convex hull of vertices, see 
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/QP_solver/Chapter_main.html#Section_10.5. 
You could massage this into a program that works with facets.

All the best,
Bernd.

On 3/14/12 2:39 PM, Zohar wrote:
> After a few experiments:
>
> http://cgal-discuss.949826.n4.nabble.com/Surface-remeshing-using-mesh-generation-td4471479.html
>
> First the condition should be
>
>           plane.oriented_side(p) != CGAL::ON_NEGATIVE_SIDE
>
> since we need oriented plane.
>
> Second we need to remember to test this with all
> ftree.all_intersected_primitives() (if the closest point is an edge or a
> vertex the returned primitive is random).
>
> Third the oriented side test requires Epec kernel, else the calculation is
> wrong. This makes the scheme terribly slow.
>
>
>
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Determine-if-a-point-is-interior-or-exterior-to-a-Polyhedron-3-tp4466730p4471850.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.