Compute the centroid of a polytope

[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/

CC: @jplab @LaisRast @vbraun

Component: geometry

Keywords: polytopes, centroid

Author: Volker Braun, Jonathan Kliem

Branch/Commit: 4a24902

Reviewer: Laith Rastanawi, Jean-Philippe Labbé

Issue created by migration from https://trac.sagemath.org/ticket/29382

[kliem]

New commits:

0e893ce

compute the centroid of a polytope

[kliem]

Commit: 0e893ce

[kliem]

Branch: public/29382

[fchapoton]

comment:2

typo in the sentence "the induces Lebesgue measure"

[sagetrac-git]

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

97e5999

typo

[sagetrac-git]

Changed commit from 0e893ce to 97e5999

[kliem]

comment:4

Ok.

[jplab]

comment:5

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

[kliem]

comment:6

Ok, did that.

[DaveWitteMorris]

comment:7

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'

[sagetrac-git]

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

082debd

handling small dimensional cases

[sagetrac-git]

Changed commit from 97e5999 to 082debd

[kliem]

comment:9

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]

comment:10

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.

[LaisRast]

comment:11

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

[jplab]

comment:12

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.

[kliem]

Changed branch from public/29382 to public/29382-reb

[kliem]

Changed commit from 082debd to 3a3007d

[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

[sagetrac-git]

Changed commit from 3a3007d to 4a24902

[sagetrac-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

[jplab]

comment:15

Did you squash commits?

[kliem]

comment:16

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

[jplab]

Reviewer: Laith Rastanawi, Jean-Philippe Labbé

[jplab]

comment:17

LGTM!

[vbraun]

Changed branch from public/29382-reb to 4a24902