0
$\begingroup$

I've just been told in a comment of this question I posted two days ago that there exists a Matlab function that computes the centroid of any convex polytope in $\mathbb{R}^n$. The user who pointed out that Matlab function knows of no equivalence in Mathematica. Therefore, my question is: do we have any way to compute the centroid of a convex polytope in $\mathbb{R}^n$ as that Matlab function does?

Thank you all for your time.

EDIT. Following the request I provide two such of polytopes. Consider the following convex hull of the following sets $x,x^\prime$ of vertices:

$Co(x) = Co \{(2,1,0),(2,0,1),(1,0,2),(0,1,2)\} \in \mathbb{R}^3$

$Co(x^\prime) = Co\{(1,0,1,1),(0,0,2,1),(0,0,1,2),(0,1,1,1),(1,1,1,0),(1,1,0,1),(1,2,0,0)\} \in \mathbb{R}^4$

These are examples of polytopes (polyhedrons for some) in $\mathbb{R}^3$ and $\mathbb{R}^4$, respectively.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ My math background is sorely lacking, could you give a few examples of a convex polytope, perhaps for different values of $n$? $\endgroup$ Commented Jan 18, 2018 at 14:54
  • 1
    $\begingroup$ The 4-volume of your example 4-tope is zero, since it's equivalent to the set {{0, 0, 0, 0}, {-1, 0, 1, 0}, {-1, 0, 0, 1}, {-1, 1, 0, 0}, {0, 1, 0, -1}, {0, 1, -1, 0}, {0, 2, -1, -1}}, and these vectors are spanned by only three vectors {{1, 0, 0, -1}, {0, 1, 0, -1}, {0, 0, 1, -1}} (applying RowReduce.) Was this intentional? $\endgroup$ Commented Jan 18, 2018 at 15:59
  • 1
    $\begingroup$ No, it could just be that the volume happens to be zero. This is analogous to picking 4 random vertices in 3-space that just happen to all lie in the same plane, in which case the 3-dimensional volume of their convex hull is zero. What does MATLAB return when you use the vertex set $x'$ as input? $\endgroup$ Commented Jan 18, 2018 at 16:07
  • 1
    $\begingroup$ Please do — I'm to see what MATLAB will do. I think the same problem holds for your first vertex set as well — all four vertices lie in the plane determined by $(2,0,1) + a (0, -1, 1) + b(-1,0,1)$. $\endgroup$ Commented Jan 18, 2018 at 16:16
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$ Commented Jan 18, 2018 at 16:30

1 Answer 1

Reset to default
2
$\begingroup$

I believe you're looking for RegionCentroid. For example, here (from the RegionCentroid documentation) is how to calculate the centroids of the standard $n$-simplex for various values of $n$:

Table[RegionCentroid[Simplex[n]], {n, 1, 5}] (* {{1/2}, {1/3, 1/3}, {1/4, 1/4, 1/4}, {1/5, 1/5, 1/5, 1/5}, {1/6, 1/6, 1/6, 1/6, 1/6}} *)

Region objects can be specified in many ways in Mathematica; consult the Geometric Computation Guide for more information.

EDIT: The problem arises in that Mathematica does not seem to have a built-in function to find the convex hull of a set of vertices in $n$ dimensions. (At least in my version, which is 10.4.) The obvious candidates, ConvexHullMesh and DelaunayMesh, only seem to work for $n \leq 3$. So we have to program something ourselves. The technique I will use is as follows:

  • Generate all possible subsets of the input points that could form an $n$-simplex.
  • For each subset, check whether the differences between all the vectors form an $n$-dimensional basis. This can be done by taking the determinant of the vectors $\vec{x}_1 - \vec{x}_2, \vec{x}_2 - \vec{x}_3, ...$ Discard those subsets which do not form such a basis.
  • Take the geometric union of the simplexes spanned by the points that remain; this union will be the convex hull of the points. Determine this region's centroid.

Here's the code:

convexCentroid[pts_?MatrixQ] := ( n = Length[First[pts]]; (* Determine dimension *) pointsubsets = Subsets[pts, {n + 1}]; (* Form candidate sets for simplexes *) simplexsubsets = Select[pointsubsets, (MatrixRank[Differences[#]] == n) &]; (*Discard all zero-volume simplexes *) RegionCentroid[RegionUnion[Simplex /@ simplexsubsets]] (* Take volume of union of remaining simplexes *) ) points = {{1, 0, 1, 1}, {0, 0, 2, 1}, {0, 0, 1, 2}, {0, 1, 1, 1}, {1, 1, 1, 0}, {1, 1, 0, 1}, {1, 3, 0, 0}}; convexCentroid[points] (* {3/5, 1, 4/5, 4/5} *)

Note that I modified the last point to $(1,3,0,0)$ in this example, since as I noted in the comments, the volume of the original point set is zero. (Better error handling could be implemented to deal with this.) This code takes about 50 seconds to run on my machine; it's not terribly efficient, particularly as the number of vertices goes up. I tried calculating the volume of the unit tesseract (4-cube) with this program, but my computer ran out of memory as it tried to keep track of all ${16 \choose 5} = 4368$ simplexes.

This code can be slightly modified; if you know a priori that the convex hull has dimensions $d < n$, you can explicitly tell Mathematica to look at all possible $d$-simplexes spanned by the points, and then take their union:

convexCentroidknownD[pts_?MatrixQ, dim_] := ( pointsubsets = Subsets[pts, {dim + 1}]; simplexsubsets = Select[pointsubsets, (MatrixRank[Differences[#]] == dim) &]; RegionCentroid[RegionUnion[Simplex /@ simplexsubsets]] )

This code allows us to find the 2-volume (area) of the convex hull of the 3D example points, and the 3-volume of the convex hull spanned by the 4-D example points:

points3 = {{2, 1, 0}, {2, 0, 1}, {1, 0, 2}, {0, 1, 2}}; points4 = {{1, 0, 1, 1}, {0, 0, 2, 1}, {0, 0, 1, 2}, {0, 1, 1, 1}, {1, 1, 1, 0}, {1, 1, 0, 1}, {1, 2, 0, 0}}; convexCentroidknownD[points3, 2] convexCentroidknownD[points4, 3] (* {11/9, 5/9, 11/9} *) (* {11/20, 13/20, 9/10, 9/10} *)
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much for your edit. To sum up, the short answer to my question is "no, there is no equivalent in Mathematica to that Matlab function I linked". If I knew how to write it, I would. But I can't. I like Mathematica way more than Matlab, but this time it seems I'll have to resort to Matlab. $\endgroup$ Commented Jan 18, 2018 at 15:43

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.