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.

Improve this question
$\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$
    – Joseph O'Rourke
    Commented 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$
    – Freddy Pierson
    Commented Aug 4, 2013 at 4:18

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Freddy Pierson
    Commented Aug 4, 2013 at 4:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .