5
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot! Still, I need to figure out, if I'm dealing with simplices - I'm not sure, that every convex hull is a simplex. $\endgroup$ – Drey Jul 24 '12 at 8:37
  • $\begingroup$ a n-d simplex has exactly n+1 vertices so no, not every convex hull is a simplex. But every polytope can be partitioned into the union of disjoint simplices (e.g. in 2d, triangulating an arbitrary polygon). Then, to get the total area, add up the areas of all the triangles. $\endgroup$ – Ronaldo Carpio Jul 26 '12 at 19:27

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.