Add a face truncation method to Polyhedron class

[Jean-Philippe Labbé]

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 edge-truncation, which is achieve by cutting the polytope along a "well-chosen" 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 ill-named. It should be renamed simply "truncation" or "complete_vertex_truncation".

While at it, I corrected a few writing conventions in the file.

[Jean-Philippe Labbé]

New commits:

​2182d7e	Initial commit: added a face truncation method
​8bec9b2	Added deprecation warning

[Jean-Philippe Labbé]

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.

[Volker Braun]

Conflicts, can you merge in the latest beta?

[Jean-Philippe Labbé]

Sure, will do.

[git]

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

​d26a570	Merge branch 'develop' into edge_truncation
​b66b4ed	Merge branch sage6.7.beta3 into ticket18128

[Jean-Philippe Labbé]

I don't really know why there are two commits for the merge. Perhaps I typed something more by accident(!?)

[Volker Braun]

You checked in a conflict marker (the thing starting with <<<<<<< HEAD).

[git]

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

​0ba2629

Solved forgotten conflict

[git]

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

​cf567e8	Merge branch 'sage-6.8.beta2' into edge_truncation
​eef9e96	Made test pass on 6.8.beta2

[Frédéric Chapoton]

two failing doctests (should be easy to fix)

[git]

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

[Jean-Philippe Labbé]

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.

[git]

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

​92d0490

Made tests pass in smallgraphs.py

[Vincent Delecroix]

CONFLICT (content): Merge conflict in src/sage/geometry/polyhedron/base.py

[git]

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

​b7cbccf

Fixed conflicts with 6.10.b7

[Vincent Delecroix]

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

[Jean-Philippe Labbé]

Dear Vincent,

Thanks a lot for the detailed review!

I'm on it!

[git]

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

​7389ccb	Complemented the doc and corrected some code
​a482887	Added some tests
​4470af6	Merge branch 'ticket18128' into sage 6.10.rc1
​38f4695	Added examples to explain more

[git]

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

​d297569

Pep8 convention

[Vincent Delecroix]

Salut Jean-Philippe,

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

[Jean-Philippe Labbé]

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

[Vincent Delecroix]

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

[Jean-Philippe Labbé]

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

[git]

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

​09f517c

Solved conflict

[git]

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

​ee4ac08

Made tests pass

[Jean-Philippe Labbé]

I have difficulty decoding what is the test which fails on the bot.

[Frédéric Chapoton]

The patchbot librae currently misbehaves. Look at the other bots instead.

[Jean-Philippe Labbé]

Okay, so the other bots seems to give a green flag...

Needs proper review again then!

[Frédéric Chapoton]

does not apply..

[git]

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

[Jean-Philippe Labbé]

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.

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

[Jean-Philippe Labbé]

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!

[git]

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

​55f9cf6

Removed brackets in sum and set

[Frédéric Chapoton]

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.

[Jean-Philippe Labbé]

This is just python. One can feed them an iterator, this avoids to build the list twice.

Good to know! Thanks!