Opened 11 years ago

Last modified 4 weeks ago

#11564 new enhancement

Implement polyhedron unfolding (i.e net) for 3-polytopes

Reported by: Eric Webster Owned by: mhampton
Priority: major Milestone: sage-9.8
Component: geometry Keywords: unfolding, net
Cc: Moritz Firsching, Jean-Philippe Labbé, gh-kliem Merged in:
Authors: Mara Kortenkamp Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: u/gh-marakortenkamp/poly_net (Commits, GitHub, GitLab) Commit: 9d4f22788cc1feafd12a03131f10a6390a9ec40e
Dependencies: Stopgaps:

Status badges

Description (last modified by Jean-Philippe Labbé)

An unfolding or a net of a polyhedron is an arrangement of edge-joined polygons in the plane which can be folded (along edges) to become the faces of the polyhedron.

There might be an overlap between polygons (this is an open problem).

This ticket implement ...

Attachments (2)

polyhedron_unfold.py (13.8 KB) - added by Eric Webster 11 years ago.
trac_11564_preliminary_effort.patch (12.1 KB) - added by mhampton 11 years ago.
Just for comparison with other effort, don't review

Download all attachments as: .zip

Change History (23)

Changed 11 years ago by Eric Webster

Attachment: polyhedron_unfold.py added

comment:1 Changed 11 years ago by mhampton

Funny timing, I was about to create a ticket with solution for this same issue. It was the outcome of an undergraduate research project. I will try to review your solution, maybe it is possible to merge the two approaches.

comment:2 Changed 11 years ago by Andrey Novoseltsev

It would be great also to handle higher dimensions, i.e. unfolding a 4-d polytope into 3-d...

comment:3 Changed 11 years ago by Eric Webster

How does the code look? Any ideas to make it better would be appreciated

comment:4 Changed 11 years ago by mhampton

Sorry, I am traveling right now and its hard to find time for Sage development. I do have some comments though.

Not all the functions in your patch have documentation/doctests. These are mandatory for every function, so they need to be added.

I think it will make sense to merge our efforts. I haven't completely fixed up my student's effort but I am attaching the current state so you can take a look at what we did. There are different strengths and weaknesses in our efforts. Ours can handle tougher problems, but we don't have a function to check for overlaps.

If you haven't looked at the master's thesis of Schlickenrieder (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.2631&rep=rep1&type=pdf) I highly recommend it. It was based on his work that my student choose to implement the steepest-edge algorithm.

A good test problem is what Schlickenrieder calls "turtles", for example:

tpoints = [[i,j,i^2+j^2] for i in srange(-5,6,1) for j in srange(-5,6,1)]
tp = Polyhedron(vertices=tpoints)

Changed 11 years ago by mhampton

Just for comparison with other effort, don't review

comment:5 Changed 10 years ago by Eric Webster

What's the status on this thing? I think it would be nice to have in sage...

comment:6 Changed 10 years ago by mhampton

My status is that I am too busy with other duties to finish this off, although I would really like to.

The code in my "trac_11564_preliminary_effort.patch" patch is from a student project. It works, but it could really use some refactoring.

Its possible I would find time to put more effort into this over my winter vacation, but don't count on it. Otherwise, if no one else works on it I would hope to tackle it in the spring or summer.

As I mentioned before, your code mainly needed full documentation (doctests). While it would be nice if it could handle some tough cases, for this kind of functionality something is better than nothing so feel free to finish your version up and I should be able to find time to review it.

comment:7 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:8 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:9 Changed 8 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:10 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:11 Changed 5 years ago by Moritz Firsching

Cc: Moritz Firsching added

comment:12 Changed 2 years ago by gh-marakortenkamp

Authors: QuantumKingMara Kortenkamp
Branch: u/gh-marakortenkamp/poly_net
Cc: Jean-Philippe Labbé gh-kliem added
Commit: c353bce99541d6e992ea134744bf130e32ffaf18

comment:13 Changed 2 years ago by git

Commit: c353bce99541d6e992ea134744bf130e32ffaf186f9867c697296d36f54a1db23c5f31cd5280592c

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

6f9867cUnfolding class

comment:14 Changed 2 years ago by Jean-Philippe Labbé

Here are a few things to fix:

  • Is the function faceorder used? It doesn't seem so.
  • In the description of `faceorder I would say:
Return a linear ordering of the edges in a spanning tree for the facet adjacency graph of `poly`.
  • Many comments are in German: it would be good to have them in English.
  • Many OUTPUT and EXAMPLES are missing.
  • Many lines contain (likely old) "Versuch". They should be deleted once every works well...
  • Class Unfolding needs docstring for the class and its methods
  • Some conventions should be checked (spaces around = -> = and such...

I know it is a bit premature for me to give feedback, but it can be used later for a checklist.

I guess also there should be a method in base.py called something like def unfolding(...): that will return the picture?

comment:15 Changed 2 years ago by Jean-Philippe Labbé

Description: modified (diff)
Milestone: sage-6.4sage-9.3
Reviewers: Jean-Philippe Labbé
Summary: Implement polyhedron unfolding (i.e net)Implement polyhedron unfolding (i.e net) for 3-polytopes

Once the ticket is more advanced, it would be good to complete the description...

comment:16 Changed 20 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:17 Changed 18 months ago by git

Commit: 6f9867c697296d36f54a1db23c5f31cd5280592c9d4f22788cc1feafd12a03131f10a6390a9ec40e

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

9d4f227added examples

comment:18 Changed 15 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:19 Changed 10 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:20 Changed 6 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:21 Changed 4 weeks ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.