CGAL users discussion list

[Olivier Devillers <>]

Le 4/17/12 11:51 AM, sgdimitris a écrit :
> I would like to ask which is the easiest and fastest way to calculate the
> intersection of two *CONVEX* 3D polyhedrons?
> I *don't* want only to see if the two polyhedrons are intersected but also
> to calculate the polyhedron that is their intersection!
from a theoretical point of view, it can be done in linear time:
Chazelle, an optimal algorithm for intersecting three-dimensional convex 
polyhedra. SIAM J Comput. 21(4):671-606, 1992.

More practically (using CGAL):
By duality, intersection of half-spaces is equivalent to a convex hull.

- Modelize your polyhedra as intersections of half-spaces.
- Dualize your half-spaces
- compute the convex hull of all points
- dualize again.