CGAL users discussion list

[Evan Behar <>]

Thank you Olivier, Quentin,

By prior operations, I have the planes specified as Kernel::Plane_3, and grouped into sets such that the intersection of the planes from each set is guaranteed to be either Point_3 or Segment_3, so I have used CGAL::intersection to obtain either the Point_3 or Segment_3 from these sets of intersections, and took the convex hull of the vertices obtained using convex_hull_3, which is much faster than using Nef_polyhedron_3 intersections. It seems to be correct, but I'm wondering, are there correctness or robustness issues with that approach?

Thanks,

Evan

On Fri, May 3, 2013 at 11:24 AM, Quentin Merigot <> wrote:

Hi Evan,

I attach a function that does exactly what Olivier suggest in order to compute the intersection of halfspaces in 3D, assuming that the origin is contained inside the intersection. Note that the code makes some geometric constructions and is not robust to degenerate situations. (The right way to do this would probably be to write modified predicates for convex_hull_3 in order to work to work implicitely with the points that are the dual of the planes.)

PS: despite the CGAL namespace, this code is not part of CGAL, all bugs are mine.

Best,

Quentin

2013/4/30 Olivier Devillers <>

Le 4/29/13 5:58 PM, Evan Behar a écrit :

Hi,

I have computed many Plane_3 from points and vectors that I am given, and I want to combine them into a convex polyhedron. I have been trying to do this by constructing Nef_polyhedron_3 from the Plane_3 to create the halfspace and then iteratively intersecting the Nef_polyhedron_3, however this becomes quite slow after a while.

It is not important that I specifically have a Nef_polyhedron_3, a Polyhedron_3 will work just fine. Given that, is there a canonical, efficient way to compute a convex polyhedron from the intersection of half-spaces?

If you know a point inside the intersection then, by duality, an intersection of half spaces corresponds to a 3D convex hull of points.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss