Convex polytope volume and centroid calculation

Question

I have troubles imagining how to compute a volume and centroid of an n-dimesional convex polytope.

For a polygon (especially for convex polygon) the area and centroid are described in (wiki) by $$ A= \frac{1}{2} \sum \limits_{i=0}^n (x_iy_{i+1}-x_{i+1}y_i) $$ For k-dimensional case the volume (Volume) is $$ \int\limits_a^bA(h)\mathrm{d}h $$ Still, maybe I need another cup of coffee to be able to transfer this into code. So i was thinking about this $$ A= \sum\limits_{d=1}^k \sum\limits_{\forall d' \neq d} \frac{1}{k}\sum \limits_{i=0}^n (p^{(d)}_i p^{(d')}_{i+1}-p^{(d)}_{i+1}p^{(d')}_i) $$ with $p^{(d)}$ beeing a variable in dimesion $d$ But I do not trust myself ;-) Do you have an idea ?

As for centroids, I do not understand where the factor $\frac{1}{6}$ comes from $$ C_x = \frac{1}{6 A} \sum_{i = 0}^{n - 1} (x_i + x_{i + 1}) (x_i y_{i + 1} - x_{i + 1} y_i) $$ and would blindly guess $$ C_{(d)} = \frac{1}{(k+1)! A} \sum\limits_{\forall d' \neq d}\sum_{i = 0}^{n - 1} (p_i^{(d)} + p_{i + 1}^{(d)}) (p_i^{(d)} p_{i + 1}^{(d')} - p_{i + 1}^{(d)} p_i^{(d')}) $$ Do you think this is right? I appriciate any feedback! Thanks!

Answer 1

If the dimension is not too high, you can use a triangulation library (e.g. CGAL) to decompose the polytope into n-dimensional simplices; calculating the volume of a simplex has a simple formula.