I need to compute a closest point on a nonconvex polyhedron to a given point in 3D space. I need a simple algorithm or library. I search in CGAL but did not find a suitable function and the package is very complicated. I also looked on Mauch's CPT (it does not compile) and gts-cpt (the result is not correct). I do not need any fast algorithm. The calculation is done only once for the grid during initialization. Simple to implement is MUCH more important to me.
A key phrase that will find you the literature is collision detection (because one needs to find the closest point to a polyhedral model to detect impending collision). For example:
Ponamgi, Manocha, Lin. "Incremental algorithms for collision detection between solid models." (ACM link)
A software package named SWIFT++ is maintained at the Univ. North Carolina: SWIFT++ link :
SWIFT++ is a collision detection package capable of detecting intersection, performing tolerance verification, computing approximate and exact distance, or determining the contacts between pairs of objects in a scene composed of general rigid polyhedral models.
Caveat: None of this is simple or straightforward!
-
$\begingroup$ Yhank you, I upvoted your answer, but I will use in the end what I found below, it was quite hidden to me, because I searched the CGAL documentation several times. $\endgroup$ – Vladimir F Mar 27 '13 at 14:30
In the end I found that the example http://www.cgal.org/Manual/latest/examples/AABB_tree/AABB_polyhedron_facet_distance_example.cpp does exactly what I need. How should a non expert like me know that he should search in some AABB I do not know.