Opened 7 years ago
Last modified 5 years ago
#18128 closed enhancement
Add a face truncation method to Polyhedron class — at Version 45
Reported by:  jipilab  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  geometry  Keywords:  face truncation, polytope 
Cc:  vbraun, mhampton, moritz  Merged in:  
Authors:  JeanPhilippe Labbé  Reviewers:  Vincent Delecroix, Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  u/jipilab/ge_truncation (Commits, GitHub, GitLab)  Commit:  55f9cf6e235cd0a0d7d2b0158ab51423510b172d 
Dependencies:  Stopgaps: 
Description (last modified by )
Currently, it is possible to do a truncation of a polytope via the method ".edge_truncation()".
See http://en.wikipedia.org/wiki/Truncation_%28geometry%29
I currently need the notion of edgetruncation, which is achieve by cutting the polytope along a "wellchosen" hyperplane whose normal vector lies in the normal cone of the edge. This edge truncation uses only one edge. Not all edges at once.
Further, one can define a face truncation similarly with the same code. I am implementing a method called ".face_truncation(face, normal_coefficient, cut_frac)" taking a face of the polytope, and two optional parameters to vary the angle of the cut.
This new method makes the old method illnamed. It should be renamed simply "truncation" or "complete_vertex_truncation".
While at it, I corrected a few writing conventions in the file.
Change History (45)
comment:1 Changed 7 years ago by
 Cc moritz added
comment:2 Changed 7 years ago by
 Branch set to u/jipilab/ge_truncation
comment:3 Changed 7 years ago by
 Commit set to 8bec9b2a593ea93e7ba49db17303565e82e29016
 Description modified (diff)
 Status changed from new to needs_review
comment:4 Changed 7 years ago by
All test passed on sage 6.6.b5. The tests do not take more than 0.1 sec more than before on my old laptop.
comment:5 Changed 7 years ago by
comment:6 Changed 6 years ago by
Conflicts, can you merge in the latest beta?
comment:7 Changed 6 years ago by
Sure, will do.
comment:8 Changed 6 years ago by
 Commit changed from 8bec9b2a593ea93e7ba49db17303565e82e29016 to b66b4edbf3ac68cfd2009eaa8edcaac11d953bb2
comment:9 Changed 6 years ago by
I don't really know why there are two commits for the merge. Perhaps I typed something more by accident(!?)
comment:10 Changed 6 years ago by
 Status changed from needs_review to needs_work
You checked in a conflict marker (the thing starting with <<<<<<< HEAD
).
comment:11 Changed 6 years ago by
 Commit changed from b66b4edbf3ac68cfd2009eaa8edcaac11d953bb2 to 0ba2629db975bd02cf40565ced0b13613358bdcb
Branch pushed to git repo; I updated commit sha1. New commits:
0ba2629  Solved forgotten conflict

comment:12 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:13 Changed 6 years ago by
 Commit changed from 0ba2629db975bd02cf40565ced0b13613358bdcb to eef9e96bb60c16feba8532d11addf8fbf2d723da
comment:14 Changed 6 years ago by
 Status changed from needs_review to needs_work
two failing doctests (should be easy to fix)
comment:15 Changed 6 years ago by
 Commit changed from eef9e96bb60c16feba8532d11addf8fbf2d723da to 6a555a5f3626aa7d4986cf1ca31c3c3c3cc0ce52
Branch pushed to git repo; I updated commit sha1. New commits:
6a555a5  Merge branch 'u/jipilab/ge_truncation' of trac.sagemath.org:sage into ticket18128

comment:16 Changed 6 years ago by
 Status changed from needs_work to needs_review
It seems there was a conflict with the latest version. Also, the test seem to pass on 6.10.b2.
Let's see what the bot says.
comment:17 Changed 6 years ago by
 Commit changed from 6a555a5f3626aa7d4986cf1ca31c3c3c3cc0ce52 to 92d0490bb3e87eab8444bdc82dfeb280a533261f
Branch pushed to git repo; I updated commit sha1. New commits:
92d0490  Made tests pass in smallgraphs.py

comment:18 Changed 6 years ago by
 Milestone changed from sage6.6 to sage6.10
 Status changed from needs_review to needs_work
CONFLICT (content): Merge conflict in src/sage/geometry/polyhedron/base.py
comment:19 Changed 6 years ago by
 Commit changed from 92d0490bb3e87eab8444bdc82dfeb280a533261f to b7cbccf5b241f585b8c1715db61ea0939104ec9e
Branch pushed to git repo; I updated commit sha1. New commits:
b7cbccf  Fixed conflicts with 6.10.b7

comment:20 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:21 Changed 6 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to needs_work
Hello,
Why did you changed the default value of the argument cut_frac
?
The following is by far not enough to understand what the method is doing
+  ``linear_coefficients``  tuple of integer. Specify the coefficient + of the normal vector of the cutting hyperplane.
You should add more description in the docstring. (that would help me to understand what this method is doing)
In your examples you are only showing how combinatorially the method behave. I guess that the actual added vertices are indeed interesting. (that would help me to understand what this method is doing (bis))
There is a trailing whitespace after the docstring and many before the return
.
You should replace
if False not in map(lambda x: facet.contains(x) and not facet.interior_contains(x), face_vertices):
by
if any(facet.contains(x) and not facet.interior_contains(x) for x in face_vertices):
Also replace
linear_evaluation.difference(set([B]))
by
linear_evaluation.difference(B)
And add an example where the base ring does change.
Vincent
comment:22 Changed 6 years ago by
Dear Vincent,
Thanks a lot for the detailed review!
I'm on it!
comment:23 Changed 6 years ago by
 Commit changed from b7cbccf5b241f585b8c1715db61ea0939104ec9e to 38f4695c49dd65da680386a692cc8d8a6f2418cb
comment:24 Changed 6 years ago by
 Commit changed from 38f4695c49dd65da680386a692cc8d8a6f2418cb to d29756915ab7a9c66189c4cacca52dc2bebf62d5
Branch pushed to git repo; I updated commit sha1. New commits:
d297569  Pep8 convention

comment:25 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:26 Changed 6 years ago by
 Milestone changed from sage6.10 to sage6.11
comment:27 followup: ↓ 30 Changed 6 years ago by
 Status changed from needs_review to needs_info
Salut JeanPhilippe,
I am confused with terminology. The truncation
(= the old edge_truncation
) is an operation that can be obtained by several applications of your face_truncation
isn't it? But if I want to do that it would be a nightmare since the coefficient would changed depending on whether or not the face has been touched before...
If true, wouldn't be possible to join the two methods? For example I might want to truncate all faces of dimension 1 in the cube with the same coefficient. This would be a sort of intermediate between the two currently available methods.
Vincent
comment:28 Changed 6 years ago by
Salut Vincent,
I was also confused with the choice edge_truncation
already. I have no idea why it was named this way. The only reason I can find is if you think of a polytope as a graph only and you cut all the edges simultaneously twice: close to each of their ends. But geometrically, there is much much more happening.
As I said, this method does the truncations all at the same time, giving a different result than cutting a single face at a time, where you then also have to take care of how deep you cut.
The previous edge_truncation
(which is now truncation
inspired by the wikipedia page above), actually performs face truncations with faces being vertices, again all simultaneously.
I tried to think of how to join the two methods. Doing the truncation
using the function face_truncation
one vertex at a time while also recording the old data for where to cut each vertex next seemed like over doing what it was already doing with very simple code.
So, I don't really see an advantage in joining the functions...
comment:29 Changed 6 years ago by
What I meant is that instead of feeding the function with one face, you might want to feed it with several. In which case the coefficient cut_frac
would make reference to the original faces. The function truncation
would just be a shortcut for p.face_truncation(p.faces(0))
.
Vincent
comment:30 in reply to: ↑ 27 Changed 6 years ago by
Replying to vdelecroix:
If true, wouldn't be possible to join the two methods? For example I might want to truncate all faces of dimension 1 in the cube with the same coefficient. This would be a sort of intermediate between the two currently available methods.
So I would say that the answer is No. The truncation method does things simultaneously while face_truncation really needs the current whole polytope in order to truncate a face with the appropriate proportion. This operation does not commute with itself as even the second face may not be a face of the result anymore. So I would leave the function as it currently is...
I'm currently working on the conflict...
comment:31 Changed 6 years ago by
 Commit changed from d29756915ab7a9c66189c4cacca52dc2bebf62d5 to 09f517c7319727c52fab2af102edfcd8ab0817be
Branch pushed to git repo; I updated commit sha1. New commits:
09f517c  Solved conflict

comment:32 Changed 6 years ago by
 Milestone changed from sage7.0 to sage7.1
 Status changed from needs_info to needs_review
comment:33 Changed 6 years ago by
 Commit changed from 09f517c7319727c52fab2af102edfcd8ab0817be to ee4ac08d0a934e5792294c82b4aedef511bf4f45
Branch pushed to git repo; I updated commit sha1. New commits:
ee4ac08  Made tests pass

comment:34 Changed 6 years ago by
I have difficulty decoding what is the test which fails on the bot.
comment:35 Changed 6 years ago by
The patchbot librae currently misbehaves. Look at the other bots instead.
comment:36 Changed 6 years ago by
Okay, so the other bots seems to give a green flag...
Needs proper review again then!
comment:38 Changed 5 years ago by
 Commit changed from ee4ac08d0a934e5792294c82b4aedef511bf4f45 to ec17f2b3e1e9cef04a5c3fd2ce8eb42e17f2e715
Branch pushed to git repo; I updated commit sha1. New commits:
ec17f2b  Merge branch 'u/jipilab/ge_truncation' of trac.sagemath.org:sage into 18128

comment:39 Changed 5 years ago by
 Status changed from needs_work to needs_review
This is a rebased version on 7.6.b2, solved the conflicts.
All test passed on the three modified files. Let's see what the bot says.
comment:40 followup: ↓ 41 Changed 5 years ago by
 Milestone changed from sage7.1 to sage7.6
 Reviewers changed from Vincent Delecroix to Vincent Delecroix, Frédéric Chapoton
Salut,
two remarks, otherwise this is good to go:
1) in
+ normal_vector = sum([linear_coefficients[i]*normal_vectors[i] for i + in range(len(normal_vectors))])
there is no need for the [ ] just inside sum()
2) similarly in
+ linear_evaluation = set([normal_vector * (v.vector()) for v in + self.vertices()])
inside set()
Once done and checked, you can set a positive review on my behalf.
comment:41 in reply to: ↑ 40 ; followup: ↓ 44 Changed 5 years ago by
Salut!
Replying to chapoton:
Salut,
two remarks, otherwise this is good to go:
1) in
+ normal_vector = sum([linear_coefficients[i]*normal_vectors[i] for i + in range(len(normal_vectors))])there is no need for the [ ] just inside sum()
2) similarly in
+ linear_evaluation = set([normal_vector * (v.vector()) for v in + self.vertices()])inside set()
Just for my information, where is this feature coming from? python3, sage?
Once done and checked, you can set a positive review on my behalf.
Great! Thanks a lot!
comment:42 Changed 5 years ago by
 Commit changed from ec17f2b3e1e9cef04a5c3fd2ce8eb42e17f2e715 to 55f9cf6e235cd0a0d7d2b0158ab51423510b172d
Branch pushed to git repo; I updated commit sha1. New commits:
55f9cf6  Removed brackets in sum and set

comment:43 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:44 in reply to: ↑ 41 Changed 5 years ago by
Just for my information, where is this feature coming from? python3, sage?
This is just python. One can feed them an iterator, this avoids to build the list twice.
comment:45 Changed 5 years ago by
 Description modified (diff)
New commits:
Initial commit: added a face truncation method
Added deprecation warning