Opened 3 years ago
Closed 3 years ago
#24847 closed enhancement (fixed)
Implement stacking onto a face of a polyhedron
Reported by:  jipilab  Owned by:  

Priority:  major  Milestone:  sage8.4 
Component:  geometry  Keywords:  days93, polytope 
Cc:  vdelecroix, moritz, mkoeppe, chapoton  Merged in:  
Authors:  JeanPhilippe Labbé  Reviewers:  Moritz Firsching, Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  e5838ed (Commits, GitHub, GitLab)  Commit:  e5838ed86d3b809a700caee05a1a7121c18e9180 
Dependencies:  #22572  Stopgaps: 
Description (last modified by )
From https://www.csun.edu/~ctoth/Handbook/chap15.pdf:
Stacking onto a face of a polytope adds a vertex slightly outside of the polytope positioned over a point in the interior of the face.
This is the "polar" of the truncation operation.
Change History (23)
comment:1 Changed 3 years ago by
 Branch set to u/jipilab/24847
 Commit set to 3bfb953c7768ca9d70f49f9fdd8afd0730972d28
 Dependencies set to #22572
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 3 years ago by
 Commit changed from 3bfb953c7768ca9d70f49f9fdd8afd0730972d28 to d5908a56214314913019b8a23cbce90b355e1015
Branch pushed to git repo; I updated commit sha1. New commits:
d5908a5  Cleaned two old deprecation warnings

comment:3 Changed 3 years ago by
comment:4 Changed 3 years ago by
 Commit changed from d5908a56214314913019b8a23cbce90b355e1015 to 9677be72e86bda92805002a60c8395f0c07b5ec1
Branch pushed to git repo; I updated commit sha1. New commits:
9677be7  Merge branch '8.2.b7' into 24847

comment:5 Changed 3 years ago by
 Branch changed from u/jipilab/24847 to u/moritz/24847
comment:6 Changed 3 years ago by
 Commit changed from 9677be72e86bda92805002a60c8395f0c07b5ec1 to 7f0af175384c559ef091af7c61abc0e1bc07f01f
Branch pushed to git repo; I updated commit sha1. New commits:
7f0af17  pep

comment:7 followup: ↓ 8 Changed 3 years ago by
That's a nice addition.
One question: Should we give the user more control over the base ring of the resulting stacked polytope? At the moment it quietly changes base ring:
sage: C = polytopes.cube() sage: C.base_ring() Integer Ring sage: C.stack(C.faces(2)[2], 1/2).base_ring() Rational Field sage: C.stack(C.faces(2)[2], 0.5).base_ring() Real Double Field
Also, in the dual method of facetruncation, there is an option linear_coefficients=None
. Should there be an analogous option here?
comment:8 in reply to: ↑ 7 Changed 3 years ago by
Replying to moritz:
That's a nice addition.
Thanks! :)
One question: Should we give the user more control over the base ring of the resulting stacked polytope? At the moment it quietly changes base ring:
sage: C = polytopes.cube() sage: C.base_ring() Integer Ring sage: C.stack(C.faces(2)[2], 1/2).base_ring() Rational Field sage: C.stack(C.faces(2)[2], 0.5).base_ring() Real Double Field
I do not think it is a good idea. The above is consistent with the Polyhedron
constructor and also the current behavior for scaling (and many other methods...):
sage: C = polytopes.cube() sage: 1/2*C A 3dimensional polyhedron in QQ^3 defined as the convex hull of 8 vertices sage: 0.5*C A 3dimensional polyhedron in RDF^3 defined as the convex hull of 8 vertices
The user should be aware of the type of inputs that are given, and the constructed object is somehow expected to be in the fraction field of the ring. The base_ring of self
can not be kept in general and if the user wants to keep the base ring, it should keep the input to be in the base ring...
I agree that it would be nice to make this step for the user, but it is a nightmare to implement in a uniform stable way... :/
Also, in the dual method of facetruncation, there is an option
linear_coefficients=None
. Should there be an analogous option here?
I thought about it, but it leads to a lot of case analysis. At least, I did not find a simple way to do this. it seems to me that the dual equivalent has more "accessible" freedom than that one. Although I may be wrong.
comment:9 followup: ↓ 11 Changed 3 years ago by
ok, I agree with your reasoning above.
One more thing:
The stacking seems to work nicely for unbounded polyhedra if you stack on bounded faces of them:
sage: [fac] = [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()] sage: P = Polyhedron(ieqs = [[1,1,0], [1,0,1], [1,0,1]]) sage: [fac] = [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()] sage: P = Polyhedron(ieqs = [[1,1,0], [1,0,1], [1,0,1]]); P A 2dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray sage: [fac] = [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()] sage: SP = P.stack(fac); SP A 2dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices and 1 ray sage: P.vertices(), SP.vertices() ((A vertex at (1, 1), A vertex at (1, 1)), (A vertex at (0, 0), A vertex at (1, 1), A vertex at (1, 1)))
Could you add this as an example?
What is the desired behavior when stacking on unbounded faces of unbounded polyhedra?
comment:10 Changed 3 years ago by
 Reviewers set to Moritz Firsching
comment:11 in reply to: ↑ 9 Changed 3 years ago by
The stacking seems to work nicely for unbounded polyhedra if you stack on bounded faces of them:
sage: [fac] = [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()] sage: P = Polyhedron(ieqs = [[1,1,0], [1,0,1], [1,0,1]]) sage: [fac] = [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()] sage: P = Polyhedron(ieqs = [[1,1,0], [1,0,1], [1,0,1]]); P A 2dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray sage: [fac] = [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()] sage: SP = P.stack(fac); SP A 2dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices and 1 ray sage: P.vertices(), SP.vertices() ((A vertex at (1, 1), A vertex at (1, 1)), (A vertex at (0, 0), A vertex at (1, 1), A vertex at (1, 1)))
Could you retrieve the first P
above? It seems to be missing.
Could you add this as an example?
Sure!
What is the desired behavior when stacking on unbounded faces of unbounded polyhedra?
If one takes "stacking" as adding a vertex "just outside" a face as a definition, then it is not very difficult to extend it to unbounded faces using .representative_point()
for face.as_polyhedron()
and pushing it out a little.
comment:12 Changed 3 years ago by
 Branch changed from u/moritz/24847 to public/stackpoly
 Commit changed from 7f0af175384c559ef091af7c61abc0e1bc07f01f to 664df999f6260084f2817bd557ea77d1c31a3d68
New commits:
664df99  deal with unbounded faces

comment:13 Changed 3 years ago by
 Commit changed from 664df999f6260084f2817bd557ea77d1c31a3d68 to 2a59f674ce2c9da6a79624ebcc4cffa07182422d
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
7f5e125  fixed typos in polyhedra_quickref.rst

bd6c356  LateX > LaTeX in polytope_tikz.rst

b1ce45b  Several other corrections

d526f70  renamed tutorial files

d7896f8  Merge branch 'develop' into 22572

597b802  Merge branch sage8.2.rc1 into 22572

eee533a  Corrections from review

b74ae85  Made tests pass

b5470d8  Merge branch tutorial into stackpoly

2a59f67  Added stack to quickref

comment:14 Changed 3 years ago by
 Description modified (diff)
I made the function a bit more robust: checking if the face
is a PolyhedronFace
object, and fixed it so that it accepts unbounded faces.
@moritz: I think that the new examples show the possibilities properly.
Needs review again!
comment:15 Changed 3 years ago by
 Status changed from needs_review to needs_work
branch does not merge
comment:16 Changed 3 years ago by
 Commit changed from 2a59f674ce2c9da6a79624ebcc4cffa07182422d to e5838ed86d3b809a700caee05a1a7121c18e9180
Branch pushed to git repo; I updated commit sha1. New commits:
e5838ed  Merge branch 'stackpoly' into 24847

comment:17 Changed 3 years ago by
 Milestone changed from sage8.2 to sage8.3
comment:18 Changed 3 years ago by
Now merges cleanly.
In the ticket, I also remove two old deprecation warnings...
comment:19 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:20 Changed 3 years ago by
 Reviewers changed from Moritz Firsching to Moritz Firsching, Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, let it be
comment:21 Changed 3 years ago by
Thanks for the review!
comment:22 Changed 3 years ago by
 Milestone changed from sage8.3 to sage8.4
update milestone 8.3 > 8.4
comment:23 Changed 3 years ago by
 Branch changed from public/stackpoly to e5838ed86d3b809a700caee05a1a7121c18e9180
 Resolution set to fixed
 Status changed from positive_review to closed
Here's a first working version.
I hesitated between different approaches. This is not the most flexible implementation, but at least a solid enough implementation.
New commits:
first version of stacking