Add a face truncation method to Polyhedron class

[jipilab]

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.

[jipilab]

New commits:

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

[jipilab]

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.

[vbraun]

Conflicts, can you merge in the latest beta?

[jipilab]

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

[jipilab]

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

[vbraun]

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

[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

[jipilab]

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

[vdelecroix]

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

[vdelecroix]

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

[jipilab]

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

[vdelecroix]

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

[jipilab]

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

[vdelecroix]

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

[jipilab]

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

[jipilab]

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

[chapoton]

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

[jipilab]

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

Needs proper review again then!

[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

[jipilab]

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.

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

[jipilab]

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

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

[jipilab]

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

Good to know! Thanks!