Exact formulae for the area of polygons and volume of polyhedrals

2k views Asked by At

I want to compute the area of a random polygon and the volume of a random polyhedron. Google searches led me to tessellation and the Monte Carlo method. However I am only interested in an exact calculation and not an approximation through convergence. Might someone know the exact formulae by heart or have a link to a page where such formulae are described?

The formulae are not needed to apply to exotic polygons or polyhedrons. I am already satisfied if they apply to simple (non-intersecting edges) convex shapes. I would like to use nothing else besides a list of vertex coordinates [(x1, y1), ..., (xn, yn)] or [(x1, y1, z1), ..., (xn, yn, zn)], possible arranged in a specific order.

I am able to read Fortran, C/C++, Python and MATLAB. Hence an algorithm written in any of these languages or written in pseudo-code is well received.

1

There are 1 answers

5
Alexandre C. On BEST ANSWER

For simple polygons, you can use Green-Riemann formula, as explained there: http://www.math.unl.edu/~mbrittenham2/classwk/208s04/inclass/areas_of_polygons.pdf

This amounts to summing the (algebraic) areas of triangles M_iOM_j, with O the origin (or any point), and where the algebraic area of the triangle BOA is positive iff the angle BOA is positive.

For polyedras, you can use Ostrogradski's formula to generalize the above. See eg. there: http://en.wikipedia.org/wiki/Polyhedron#Volume

You can find a review of the above method for computing volumes there: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.3873&rep=rep1&type=pdf