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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.