1
$\begingroup$

Is there a simple algorithm to compute the convex polyhedron (as a mesh with verticies, edges, and faces) resulting from the intersection of a set of infinite halfspaces? This is essentially a CSG (constructive solid geometry) to B-rep (boundary representation) problem. I am aware that CGAL has the Nef-polyhedra capabilities, but using CGAL is way overkill and complicated.

The actual problem I have is this: Given a 3D lattice specified by its 3 primitive lattice vectors, determine the Voronoi cell of a single lattice point.

The problem is that I actually need the polyhedral surface rather than just the volume, so I need a boundary representation.

1 Answers 1

2

Try qhalf from the qhull package.

  • 0
    Section 11.4 of *Computational Geometry* by de Berg et al. is about duality. [David Mount's notes](http://www.cs.umd.edu/class/spring2010/cmsc754/lectures.shtml) contain a summary. See lecture 07.2011-10-07