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: sage-7.6
Component: geometry Keywords: face truncation, polytope
Cc: vbraun, mhampton, moritz Merged in:
Authors: Jean-Philippe 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:

Status badges

Description (last modified by 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.

Change History (45)

comment:1 Changed 7 years ago by jipilab

  • Cc moritz added

comment:2 Changed 7 years ago by jipilab

  • Branch set to u/jipilab/ge_truncation

comment:3 Changed 7 years ago by jipilab

  • Commit set to 8bec9b2a593ea93e7ba49db17303565e82e29016
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

2182d7eInitial commit: added a face truncation method
8bec9b2Added deprecation warning

comment:4 Changed 7 years ago by 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.

comment:5 Changed 7 years ago by jipilab

  • Authors set to Jean-Philippe Labbé

comment:6 Changed 6 years ago by vbraun

Conflicts, can you merge in the latest beta?

comment:7 Changed 6 years ago by jipilab

Sure, will do.

comment:8 Changed 6 years ago by git

  • Commit changed from 8bec9b2a593ea93e7ba49db17303565e82e29016 to b66b4edbf3ac68cfd2009eaa8edcaac11d953bb2

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

d26a570Merge branch 'develop' into edge_truncation
b66b4edMerge branch sage6.7.beta3 into ticket18128

comment:9 Changed 6 years ago by jipilab

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 vbraun

  • 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 git

  • Commit changed from b66b4edbf3ac68cfd2009eaa8edcaac11d953bb2 to 0ba2629db975bd02cf40565ced0b13613358bdcb

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

0ba2629Solved forgotten conflict

comment:12 Changed 6 years ago by jipilab

  • Status changed from needs_work to needs_review

comment:13 Changed 6 years ago by git

  • Commit changed from 0ba2629db975bd02cf40565ced0b13613358bdcb to eef9e96bb60c16feba8532d11addf8fbf2d723da

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

cf567e8Merge branch 'sage-6.8.beta2' into edge_truncation
eef9e96Made test pass on 6.8.beta2

comment:14 Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

two failing doctests (should be easy to fix)

comment:15 Changed 6 years ago by git

  • Commit changed from eef9e96bb60c16feba8532d11addf8fbf2d723da to 6a555a5f3626aa7d4986cf1ca31c3c3c3cc0ce52

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

6a555a5Merge branch 'u/jipilab/ge_truncation' of trac.sagemath.org:sage into ticket18128

comment:16 Changed 6 years ago by jipilab

  • 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 git

  • Commit changed from 6a555a5f3626aa7d4986cf1ca31c3c3c3cc0ce52 to 92d0490bb3e87eab8444bdc82dfeb280a533261f

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

92d0490Made tests pass in smallgraphs.py

comment:18 Changed 6 years ago by vdelecroix

  • Milestone changed from sage-6.6 to sage-6.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 git

  • Commit changed from 92d0490bb3e87eab8444bdc82dfeb280a533261f to b7cbccf5b241f585b8c1715db61ea0939104ec9e

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

b7cbccfFixed conflicts with 6.10.b7

comment:20 Changed 6 years ago by jipilab

  • Status changed from needs_work to needs_review

comment:21 Changed 6 years ago by vdelecroix

  • 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 jipilab

Dear Vincent,

Thanks a lot for the detailed review!

I'm on it!

comment:23 Changed 6 years ago by git

  • Commit changed from b7cbccf5b241f585b8c1715db61ea0939104ec9e to 38f4695c49dd65da680386a692cc8d8a6f2418cb

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

7389ccbComplemented the doc and corrected some code
a482887Added some tests
4470af6Merge branch 'ticket18128' into sage 6.10.rc1
38f4695Added examples to explain more

comment:24 Changed 6 years ago by git

  • Commit changed from 38f4695c49dd65da680386a692cc8d8a6f2418cb to d29756915ab7a9c66189c4cacca52dc2bebf62d5

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

d297569Pep8 convention

comment:25 Changed 6 years ago by jipilab

  • Status changed from needs_work to needs_review

comment:26 Changed 6 years ago by jipilab

  • Milestone changed from sage-6.10 to sage-6.11

comment:27 follow-up: Changed 6 years ago by vdelecroix

  • Status changed from needs_review to needs_info

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

comment:28 Changed 6 years ago by 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...

comment:29 Changed 6 years ago by 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

comment:30 in reply to: ↑ 27 Changed 6 years ago by 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...

comment:31 Changed 6 years ago by git

  • Commit changed from d29756915ab7a9c66189c4cacca52dc2bebf62d5 to 09f517c7319727c52fab2af102edfcd8ab0817be

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

09f517cSolved conflict

comment:32 Changed 6 years ago by jipilab

  • Milestone changed from sage-7.0 to sage-7.1
  • Status changed from needs_info to needs_review

comment:33 Changed 6 years ago by git

  • Commit changed from 09f517c7319727c52fab2af102edfcd8ab0817be to ee4ac08d0a934e5792294c82b4aedef511bf4f45

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

ee4ac08Made tests pass

comment:34 Changed 6 years ago by jipilab

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

comment:35 Changed 6 years ago by chapoton

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

comment:36 Changed 6 years ago by jipilab

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

Needs proper review again then!

comment:37 Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

does not apply..

comment:38 Changed 5 years ago by git

  • Commit changed from ee4ac08d0a934e5792294c82b4aedef511bf4f45 to ec17f2b3e1e9cef04a5c3fd2ce8eb42e17f2e715

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

ec17f2bMerge branch 'u/jipilab/ge_truncation' of trac.sagemath.org:sage into 18128

comment:39 Changed 5 years ago by jipilab

  • 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 follow-up: Changed 5 years ago by chapoton

  • Milestone changed from sage-7.1 to sage-7.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 ; follow-up: Changed 5 years ago by 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!

comment:42 Changed 5 years ago by git

  • Commit changed from ec17f2b3e1e9cef04a5c3fd2ce8eb42e17f2e715 to 55f9cf6e235cd0a0d7d2b0158ab51423510b172d

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

55f9cf6Removed brackets in sum and set

comment:43 Changed 5 years ago by jipilab

  • Status changed from needs_review to positive_review

comment:44 in reply to: ↑ 41 Changed 5 years ago by 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.

comment:45 Changed 5 years ago by jipilab

  • Description modified (diff)
Note: See TracTickets for help on using tickets.