I am aware that an algorithm exist to find area of a convex polyhedron when the vertices are given in order. But, I have a convex polyhedra which does not have vertices in order and I wish to compute its area.

I thought of 2 possible approaches -

  • Convert the unordered vertices into ordered vertices (Can it be done using Convex Hull of the polytope?)
  • A direct algorithm which computes area using the unordered vertices

An answer using any one of the above mentioned approaches will satisfy my question.

PS - Mentioning any avaialble packages (in C) which will solve my problem will be a plus.

  • 1
    $\begingroup$ Certainly the first will work fine. Given that putting the vertices in order is almost a linear-time procedure, why not just do it? (Yes, you can use CHULL to do it.) $\endgroup$ – John Hughes Apr 9 at 11:56
  • $\begingroup$ @JohnHughes thanks for your help! From what I have found CHULL is in R. If you know any package in C, that would be very useful. Also, can you direct me towards the sources explaining the algorithm for putting the vertices in order? $\endgroup$ – Curious Iitian Apr 10 at 6:41
  • $\begingroup$ CHULL is an algorithm. It has been implemented in many languages, surely including the C or C++ computation geometry library. The output of the convex hull algorithm, applied to a set of points that are the vertices of a convex shape, will be a list of those same vertices, in order (i.e., exactly what you want). Source? Just about any computational geometry book. Sorry not to help more -- that stops being math and starts being "dealing with software," and I'm not going there. $\endgroup$ – John Hughes Apr 10 at 9:58

Your Answer

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

Browse other questions tagged or ask your own question.