Opened 8 years ago
Last modified 6 years ago
#18128 closed enhancement
Add a face truncation method to Polyhedron class — at Version 45
Reported by:  JeanPhilippe Labbé  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  geometry  Keywords:  face truncation, polytope 
Cc:  Volker Braun, mhampton, Moritz Firsching  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 8 years ago by
Cc:  Moritz Firsching added 

comment:2 Changed 8 years ago by
Branch:  → u/jipilab/ge_truncation 

comment:3 Changed 8 years ago by
Commit:  → 8bec9b2a593ea93e7ba49db17303565e82e29016 

Description:  modified (diff) 
Status:  new → needs_review 
comment:4 Changed 8 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 8 years ago by
Authors:  → JeanPhilippe Labbé 

comment:8 Changed 8 years ago by
Commit:  8bec9b2a593ea93e7ba49db17303565e82e29016 → b66b4edbf3ac68cfd2009eaa8edcaac11d953bb2 

comment:9 Changed 8 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 8 years ago by
Status:  needs_review → needs_work 

You checked in a conflict marker (the thing starting with <<<<<<< HEAD
).
comment:11 Changed 8 years ago by
Commit:  b66b4edbf3ac68cfd2009eaa8edcaac11d953bb2 → 0ba2629db975bd02cf40565ced0b13613358bdcb 

Branch pushed to git repo; I updated commit sha1. New commits:
0ba2629  Solved forgotten conflict

comment:12 Changed 8 years ago by
Status:  needs_work → needs_review 

comment:13 Changed 8 years ago by
Commit:  0ba2629db975bd02cf40565ced0b13613358bdcb → eef9e96bb60c16feba8532d11addf8fbf2d723da 

comment:14 Changed 7 years ago by
Status:  needs_review → needs_work 

two failing doctests (should be easy to fix)
comment:15 Changed 7 years ago by
Commit:  eef9e96bb60c16feba8532d11addf8fbf2d723da → 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 7 years ago by
Status:  needs_work → 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 7 years ago by
Commit:  6a555a5f3626aa7d4986cf1ca31c3c3c3cc0ce52 → 92d0490bb3e87eab8444bdc82dfeb280a533261f 

Branch pushed to git repo; I updated commit sha1. New commits:
92d0490  Made tests pass in smallgraphs.py

comment:18 Changed 7 years ago by
Milestone:  sage6.6 → sage6.10 

Status:  needs_review → needs_work 
CONFLICT (content): Merge conflict in src/sage/geometry/polyhedron/base.py
comment:19 Changed 7 years ago by
Commit:  92d0490bb3e87eab8444bdc82dfeb280a533261f → b7cbccf5b241f585b8c1715db61ea0939104ec9e 

Branch pushed to git repo; I updated commit sha1. New commits:
b7cbccf  Fixed conflicts with 6.10.b7

comment:20 Changed 7 years ago by
Status:  needs_work → needs_review 

comment:21 Changed 7 years ago by
Reviewers:  → Vincent Delecroix 

Status:  needs_review → 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:23 Changed 7 years ago by
Commit:  b7cbccf5b241f585b8c1715db61ea0939104ec9e → 38f4695c49dd65da680386a692cc8d8a6f2418cb 

comment:24 Changed 7 years ago by
Commit:  38f4695c49dd65da680386a692cc8d8a6f2418cb → d29756915ab7a9c66189c4cacca52dc2bebf62d5 

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

comment:25 Changed 7 years ago by
Status:  needs_work → needs_review 

comment:26 Changed 7 years ago by
Milestone:  sage6.10 → sage6.11 

comment:27 followup: 30 Changed 7 years ago by
Status:  needs_review → 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 7 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 7 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 Changed 7 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 7 years ago by
Commit:  d29756915ab7a9c66189c4cacca52dc2bebf62d5 → 09f517c7319727c52fab2af102edfcd8ab0817be 

Branch pushed to git repo; I updated commit sha1. New commits:
09f517c  Solved conflict

comment:32 Changed 7 years ago by
Milestone:  sage7.0 → sage7.1 

Status:  needs_info → needs_review 
comment:33 Changed 7 years ago by
Commit:  09f517c7319727c52fab2af102edfcd8ab0817be → ee4ac08d0a934e5792294c82b4aedef511bf4f45 

Branch pushed to git repo; I updated commit sha1. New commits:
ee4ac08  Made tests pass

comment:34 Changed 7 years ago by
I have difficulty decoding what is the test which fails on the bot.
comment:35 Changed 7 years ago by
The patchbot librae currently misbehaves. Look at the other bots instead.
comment:36 Changed 7 years ago by
Okay, so the other bots seems to give a green flag...
Needs proper review again then!
comment:38 Changed 6 years ago by
Commit:  ee4ac08d0a934e5792294c82b4aedef511bf4f45 → 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 6 years ago by
Status:  needs_work → 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 6 years ago by
Milestone:  sage7.1 → sage7.6 

Reviewers:  Vincent Delecroix → 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 followup: 44 Changed 6 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 6 years ago by
Commit:  ec17f2b3e1e9cef04a5c3fd2ce8eb42e17f2e715 → 55f9cf6e235cd0a0d7d2b0158ab51423510b172d 

Branch pushed to git repo; I updated commit sha1. New commits:
55f9cf6  Removed brackets in sum and set

comment:43 Changed 6 years ago by
Status:  needs_review → positive_review 

comment:44 Changed 6 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 6 years ago by
Description:  modified (diff) 

New commits:
Initial commit: added a face truncation method
Added deprecation warning