5
$\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$
  • 5
    $\begingroup$ You could use the software qhull to compute the intersection of halfspaces. See this link for qhull's halfspace intersection capabilities. $\endgroup$ – Joseph O'Rourke Aug 4 '13 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$ – Kein Mitleid Aug 4 '13 at 4:18
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$
  • $\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$ – Kein Mitleid Aug 4 '13 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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