#29382 closed enhancement (fixed)
Compute the centroid of a polytope
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  geometry  Keywords:  polytopes, centroid 
Cc:  jipilab, ghLaisRast, vbraun  Merged in:  
Authors:  Volker Braun, Jonathan Kliem  Reviewers:  Laith Rastanawi, JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  4a24902 (Commits, GitHub, GitLab)  Commit:  4a24902541f7dc6ba9c6ced558aa6c67fdace8b0 
Dependencies:  Stopgaps: 
Description
This ticket implements a method to compute the center of the mass of a polytope.
It is motivated by
https://ask.sagemath.org/question/8092/computethecentroidofapolytope/
Change History (19)
comment:1 Changed 15 months ago by
 Branch set to public/29382
 Commit set to 0e893ced596c0728e40dab701a9c8f7a216cd2dc
 Status changed from new to needs_review
comment:2 Changed 15 months ago by
typo in the sentence "the induces Lebesgue measure"
comment:3 Changed 15 months ago by
 Commit changed from 0e893ced596c0728e40dab701a9c8f7a216cd2dc to 97e59993ddfe7fda7df9329bb650fb137baf1dc2
Branch pushed to git repo; I updated commit sha1. New commits:
97e5999  typo

comment:4 Changed 15 months ago by
Ok.
comment:5 Changed 15 months ago by
You should add a comment to the asksage question and point to this ticket.
comment:6 Changed 15 months ago by
Ok, did that.
comment:7 Changed 15 months ago by
Thanks for doing this.
One small comment (and I apologize if this is noise) is that the code seems to give an error on 0dimensional polytopes (i.e., a single vertex), even though they have an obvious centroid. (One reason for the error seems to be that sage cannot triangulate them. Should this be considered a bug?)
sage: P = Polyhedron(vertices=[(1.0,2.0)], base_ring=RDF) sage: P A 0dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex sage: P.centroid()  KeyError Traceback (most recent call last) /Users/dmorris/Documents/misc/Programs/sage3/local/lib/python3.7/sitepackages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10139)() 1942 try: > 1943 return cache[k] 1944 except TypeError: # k is not hashable KeyError: (('auto',), ()) During handling of the above exception, another exception occurred: AttributeError Traceback (most recent call last) <ipythoninput343e9b24a83d1c> in <module>() > 1 P.centroid() [snip] /Users/dmorris/Documents/misc/Programs/sage3/local/lib/python3.7/sitepackages/sage/geometry/triangulation/point_configuration.py in facets_of_simplex(simplex) 2001 facet = frozenset(rest) 2002 normal = sum(normals) > 2003 normal.set_immutable() 2004 facet_normals[facet] = normal 2005 facets.append(facet) AttributeError: 'int' object has no attribute 'set_immutable' sage: P.triangulate()  AttributeError Traceback (most recent call last) <ipythoninput359c7468245456> in <module>() > 1 P.triangulate() [snip] /Users/dmorris/Documents/misc/Programs/sage3/local/lib/python3.7/sitepackages/sage/geometry/triangulation/point_configuration.py in facets_of_simplex(simplex) 2001 facet = frozenset(rest) 2002 normal = sum(normals) > 2003 normal.set_immutable() 2004 facet_normals[facet] = normal 2005 facets.append(facet) AttributeError: 'int' object has no attribute 'set_immutable'
comment:8 Changed 15 months ago by
 Commit changed from 97e59993ddfe7fda7df9329bb650fb137baf1dc2 to 082debd6ce6bc789d5dba1403ed80b43fbc1196c
Branch pushed to git repo; I updated commit sha1. New commits:
082debd  handling small dimensional cases

comment:9 Changed 15 months ago by
I opened some tickets because of small cases. They should work.
In case of empty polyhedron, there should be a reasonable error as well.
I'm passing the case of d+1 vertices down to center
now.
comment:10 Changed 14 months ago by
 Milestone changed from sage9.1 to sage9.2
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:11 Changed 14 months ago by
affine_hull
is deprecated. Use affine_hull_projection
instead.
See ticket #29326 (which you reported and authored)
comment:12 Changed 14 months ago by
 Status changed from needs_review to needs_work
The following code should appear before the INPUT/OUTPUT I think
+ If the polyhedron is not compact, a ``NotImplementedError`` is
+ raised.
Otherwise, it looks good. It might benefit from a rebase just to have clean bots go through it.
comment:13 Changed 14 months ago by
 Branch changed from public/29382 to public/29382reb
 Commit changed from 082debd6ce6bc789d5dba1403ed80b43fbc1196c to 3a3007d83ae5859288c880356d50f62af29b9bfd
 Status changed from needs_work to needs_review
Last 10 new commits:
591d3b1  fix pyflakes warning; added optional flag

a349c8c  undid change regarding strange conversion of normaliz `Sublattice` output

add61a5  undo false alignment

0797f5a  implement ambient volume using normaliz

548d302  Merge branch 'public/28873reb2' of git://trac.sagemath.org/sage into public/28873reb3

6a3d5b4  added reference

5edb725  compute the centroid of a polytope

3e0ddc8  typo

628ad49  handling small dimensional cases

3a3007d  fixed deprecated affine_hull; improved doc

comment:14 Changed 14 months ago by
 Commit changed from 3a3007d83ae5859288c880356d50f62af29b9bfd to 4a24902541f7dc6ba9c6ced558aa6c67fdace8b0
comment:15 Changed 14 months ago by
Did you squash commits?
comment:16 Changed 14 months ago by
Just ignore the commit messages in comment 13. I didn't use develop as a base. I thought it was clear from the commit messages (I based the branch on #28873, which is of course not needed).
comment:17 Changed 14 months ago by
 Reviewers set to Laith Rastanawi, JeanPhilippe Labbé
 Status changed from needs_review to positive_review
LGTM!
comment:18 Changed 14 months ago by
 Branch changed from public/29382reb to 4a24902541f7dc6ba9c6ced558aa6c67fdace8b0
 Resolution set to fixed
 Status changed from positive_review to closed
comment:19 Changed 14 months ago by
 Milestone changed from sage9.2 to sage9.1
New commits:
compute the centroid of a polytope