# Get a convex body from hyperplanes

## Recommended Posts

Mr Frank    100
I have some planes which presented by its normal and distance from zero (n.xyz, d). what should i do to find all minimal convex hulls inside these planes? ...BSP? i tried by every time i got some wrong planes groups i need something like this: [img]http://i39.tinypic.com/12342f7.jpg[/img]

##### Share on other sites
oliii    2196
BSP tree would be the natural solution to compute a convex shape. You must have some bug somewhere, but you can also use a clipping algorithm. build giant polygons out of the planes and clip them with other planes.

In 2D, that would be giant segments, cutting each other.

It also depends how you plan to represent the convex hulls.

##### Share on other sites
Dave Eberly    1173

##### Share on other sites
Mr Frank    100
WOW! cdd looks great)
i already used qhull but didn't noticed that tool)
thx!

---
ftp://ifor13.ethz.ch/pub/fukuda/cdd

is somebody have this thing?

##### Share on other sites
Dave Eberly    1173
Quote:
 Original post by Mr FrankWOW! cdd looks great)i already used qhull but didn't noticed that tool)thx!---ftp://ifor13.ethz.ch/pub/fukuda/cddlink isn't working(is somebody have this thing?

Looks like some of the links at the geom.uiuc page are stale. Try ftp://ftp.ifor.math.ethz.ch/pub/fukuda/cdd/
which I grabbed from a c.g.a. FAQ page
http://www.exaflop.org/docs/cgafaq/cga6.html

##### Share on other sites
Dave Eberly    1173
By the way, rather than using a package designed for handling the halfspace intersection problem, you could roll your own assuming you have a package for computing the convex hull of points in 3D. Your linear-inequality constraints, written as linear equalities, are converted to the form z = a*x + b*y + c. This means you can have no vertical planes defined by the constraints. Also, the origin must be a point in the halfspace intersection. If it is not, and you know some point in the intersection, then translate by that point to get the origin into the intersection.

The "dual point" to z = a*x + b*y + c is (a,b,c). Let's say that (a,b,c) is in (x',y',z') space. Compute the convex hull of the dual points. Each planar face of the hull is of the form z' = a'*x' + b'*y' + c'. The corresponding convex hull vertex in (x,y,z) space is (a',b',c').