Sign in to follow this  
Mr Frank

Get a convex body from hyperplanes

Recommended Posts

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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
WOW! cdd looks great)
i already used qhull but didn't noticed that tool)
thx!

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

link isn't working(
is somebody have this thing?

Share this post


Link to post
Share on other sites
Quote:
Original post by Mr Frank
WOW! cdd looks great)
i already used qhull but didn't noticed that tool)
thx!

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

link 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 this post


Link to post
Share on other sites
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').

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this