Opened 7 months ago

Closed 6 months ago

Last modified 6 months ago

#29382 closed enhancement (fixed)

Compute the centroid of a polytope

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords: polytopes, centroid
Cc: jipilab, gh-LaisRast, vbraun Merged in:
Authors: Volker Braun, Jonathan Kliem Reviewers: Laith Rastanawi, Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: 4a24902 (Commits) 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/compute-the-centroid-of-a-polytope/

Change History (19)

comment:1 Changed 7 months ago by gh-kliem

  • Branch set to public/29382
  • Commit set to 0e893ced596c0728e40dab701a9c8f7a216cd2dc
  • Status changed from new to needs_review

New commits:

0e893cecompute the centroid of a polytope

comment:2 Changed 7 months ago by chapoton

typo in the sentence "the induces Lebesgue measure"

comment:3 Changed 7 months ago by git

  • Commit changed from 0e893ced596c0728e40dab701a9c8f7a216cd2dc to 97e59993ddfe7fda7df9329bb650fb137baf1dc2

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

97e5999typo

comment:4 Changed 7 months ago by gh-kliem

Ok.

comment:5 Changed 7 months ago by jipilab

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

comment:6 Changed 7 months ago by gh-kliem

Ok, did that.

comment:7 Changed 7 months ago by 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'

comment:8 Changed 7 months ago by git

  • Commit changed from 97e59993ddfe7fda7df9329bb650fb137baf1dc2 to 082debd6ce6bc789d5dba1403ed80b43fbc1196c

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

082debdhandling small dimensional cases

comment:9 Changed 7 months ago by 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.

comment:10 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.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 6 months ago by gh-LaisRast

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

comment:12 Changed 6 months ago by jipilab

  • 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 6 months ago by gh-kliem

  • Branch changed from public/29382 to public/29382-reb
  • Commit changed from 082debd6ce6bc789d5dba1403ed80b43fbc1196c to 3a3007d83ae5859288c880356d50f62af29b9bfd
  • Status changed from needs_work to needs_review

Last 10 new commits:

591d3b1fix pyflakes warning; added optional flag
a349c8cundid change regarding strange conversion of normaliz `Sublattice` output
add61a5undo false alignment
0797f5aimplement ambient volume using normaliz
548d302Merge branch 'public/28873-reb2' of git://trac.sagemath.org/sage into public/28873-reb3
6a3d5b4added reference
5edb725compute the centroid of a polytope
3e0ddc8typo
628ad49handling small dimensional cases
3a3007dfixed deprecated affine_hull; improved doc

comment:14 Changed 6 months ago by git

  • Commit changed from 3a3007d83ae5859288c880356d50f62af29b9bfd to 4a24902541f7dc6ba9c6ced558aa6c67fdace8b0

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

a006ec4compute the centroid of a polytope
e4271a8typo
56f54d8handling small dimensional cases
4a24902fixed deprecated affine_hull; improved doc

comment:15 Changed 6 months ago by jipilab

Did you squash commits?

comment:16 Changed 6 months ago by 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).

comment:17 Changed 6 months ago by jipilab

  • Reviewers set to Laith Rastanawi, Jean-Philippe Labbé
  • Status changed from needs_review to positive_review

LGTM!

comment:18 Changed 6 months ago by vbraun

  • Branch changed from public/29382-reb to 4a24902541f7dc6ba9c6ced558aa6c67fdace8b0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:19 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.1
Note: See TracTickets for help on using tickets.