6
$\begingroup$

I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution.

My problem is to find the vertices that make up each face of a convex polyhedron. At my disposal are a set of planes, with each plane corresponding to a face. Each plane is derived from exactly three points that I know already exist on the corresponding face.

How do I solve this problem in an efficient manner? Apologies if this isn't in the right section, since it involves both math and computer science.

$\endgroup$
2
  • 5
    $\begingroup$ You could use the software qhull to compute the intersection of halfspaces. See this link for qhull's halfspace intersection capabilities. $\endgroup$ Aug 4, 2013 at 2:01
  • $\begingroup$ Thanks for the link. I played around with qhull, and while it produces correct results, it does not do so quickly if you simply call the program multiple times, unless there's something I'm not doing right. $\endgroup$ Aug 4, 2013 at 4:18

1 Answer 1

5
$\begingroup$

For the description of a pretty good algorithm see Avis and Fukuda. For an efficient implementation (in any dimension), and much additional discussion and references, see Komei Fukuda's page.

$\endgroup$
1
  • $\begingroup$ After a bit of debating amongst myself, I decided to accept this answer. I'll do some reading on the links you sent me. $\endgroup$ Aug 4, 2013 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.