Compute the centroid of a polytope

[gh-kliem]

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/compute-the-centroid-of-a-polytope/

[gh-kliem]

New commits:

​0e893ce

compute the centroid of a polytope

[chapoton]

typo in the sentence "the induces Lebesgue measure"

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​97e5999

typo

[gh-kliem]

Ok.

[jipilab]

You should add a comment to the asksage question and point to this ticket.

[gh-kliem]

Ok, did that.

[gh-DaveWitteMorris]

Thanks for doing this.

One small comment (and I apologize if this is noise) is that the code seems to give an error on 0-dimensional 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 0-dimensional 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/site-packages/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)
<ipython-input-34-3e9b24a83d1c> in <module>()
----> 1 P.centroid()

    [snip]

/Users/dmorris/Documents/misc/Programs/sage3/local/lib/python3.7/site-packages/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)
<ipython-input-35-9c7468245456> in <module>()
----> 1 P.triangulate()

    [snip]

/Users/dmorris/Documents/misc/Programs/sage3/local/lib/python3.7/site-packages/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'

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​082debd

handling small dimensional cases

[gh-kliem]

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.

[mkoeppe]

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.

[gh-LaisRast]

affine_hull is deprecated. Use affine_hull_projection instead. See ticket #29326 (which you reported and authored)

[jipilab]

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.

[gh-kliem]

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/28873-reb2' of git://trac.sagemath.org/sage into public/28873-reb3
​6a3d5b4	added reference
​5edb725	compute the centroid of a polytope
​3e0ddc8	typo
​628ad49	handling small dimensional cases
​3a3007d	fixed deprecated affine_hull; improved doc

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​a006ec4	compute the centroid of a polytope
​e4271a8	typo
​56f54d8	handling small dimensional cases
​4a24902	fixed deprecated affine_hull; improved doc

[jipilab]

Did you squash commits?

[gh-kliem]

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).

[jipilab]

LGTM!