CGAL users discussion list

[Peter Hachenberger <>]

Hi Atul,

if you want exact queries, then you could do it with Nef polyhedra. The 3D Nef polyhedra include
a point locator that can tell you of any point where it is. But since you also want to report points
in a surrounding of a surface, that does not work.

The fastest method I see at the moment, is to compute compute an offset of every facet (such that
each facet becomes a box, store the offsets in a search data structure, e.g., kd-tree, and
perform point location queries on that.

Peter

-----"Atul Thakur" <> wrote: -----

To:
From: "Atul Thakur" <>
Date: 10/20/2008 08:03PM
Subject: [cgal-discuss] Minimum distance of a Point_3 from a Polyhedron

Hi all:

I have a Polyhedron_3 and Point_3 and need to find out if the point lies "on the" polyhedron or not <the answer should be true if the point lies on the surface or very near to it, should be false if it lies deep within or totally outside of polyhedron>.
I think one way of doing this is to determine the distance of the point from each facet plane along its normal of the Polyhedron and then seeing if any of the distance is less than a minimum bound value (say 1e-5). Is this the right way or there exists some neat elegant function to do this check <being a newbie, scanning 3500 pages of manual looks daunting :)>? I saw some functions Polytope distance* but haven't quite understood(may be unrelated).

Any pointers would be really helpful.

sincerely,
-Atul