Opened 5 years ago
Closed 18 months ago
#25122 closed enhancement (fixed)
Construct RationalPolyhedralFan from possibly overlapping cones
Reported by:  Yuan Zhou  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  geometry  Keywords:  RationalPolyhedralFan, cone arrangement, IMAPolyGeom 
Cc:  Andrey Novoseltsev, Volker Braun, Moritz Firsching, JeanPhilippe Labbé, Matthias Köppe  Merged in:  
Authors:  Yuan Zhou  Reviewers:  Matthias Koeppe 
Report Upstream:  N/A  Work issues:  
Branch:  6bea882 (Commits, GitHub, GitLab)  Commit:  6bea8826faebc365483d3a468280b7231ba3b975 
Dependencies:  Stopgaps: 
Description (last modified by )
Given a cone arrangement where the cones are not necessarily facetoface, construct a rational polyhedral fan that is a subdivision of the cone arrangement. This could be useful for topological computations with nonconvex unions of polyhedral sets.
In the following example, the intersection of the cones c1 and c2 is not a face of each. Thus, they do not belong to the same rational polyhedral fan. By using the allow_arrangement=True
option in the Fan constructor, we construct a fan so that c1 and c2 are unions of cones in the fan. There is no guarantee that it will be "the" coarsest subdivision, though.
sage: c1 = Cone([(2,1,1), (2,1,1), (2,1,1), (2,1,1)]) sage: c2 = Cone([(1,2,1), (1,2,1), (1,2,1), (1,2,1)]) sage: Fan([c1,c2]) Traceback (most recent call last): ... ValueError: these cones cannot belong to the same fan! ... sage: fan = Fan([c1, c2], allow_arrangement=True) sage: fan.ngenerating_cones() 5 sage: fan.plot() Graphics3d Object
Change History (24)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
Cc:  Andrey Novoseltsev Volker Braun Moritz Firsching JeanPhilippe Labbé Matthias Köppe added 

Description:  modified (diff) 
Keywords:  RationalPolyhedralFan cone arrangement IMAPolyGeom added 
comment:3 Changed 5 years ago by
Branch:  → u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones 

comment:4 Changed 5 years ago by
Commit:  → 984ba246406648168236b7a9173a1ce5cb81291c 

Status:  new → needs_review 
New commits:
984ba24  implement allow_arrangement option in Fan constructor

comment:6 Changed 5 years ago by
Authors:  → Yuan Zhou 

comment:8 Changed 5 years ago by
Commit:  984ba246406648168236b7a9173a1ce5cb81291c → 4371ee7f1702396985c648a059902bd4c5e45b48 

Branch pushed to git repo; I updated commit sha1. New commits:
4371ee7  fix a typo in documentation

comment:9 Changed 3 years ago by
Milestone:  sage8.2 → sage9.2 

Moving some tickets to 9.2. This is not a promise that I will be working on them.
comment:10 Changed 2 years ago by
Status:  needs_review → needs_work 

********************************************************************** File "src/sage/geometry/fan.py", line 510, in sage.geometry.fan.? Failed example: for cone in fan.generating_cones(): print(cone.rays()) Expected: N(1, 0), N(2, 1) in 2d lattice N N(1, 2), N(2, 1) in 2d lattice N N(1, 2), N(0, 1) in 2d lattice N N(1, 2) in 2d lattice N Got: N(2, 1), N(1, 0) in 2d lattice N N(1, 2), N(2, 1) in 2d lattice N N(1, 2), N(0, 1) in 2d lattice N N(1, 2) in 2d lattice N **********************************************************************
This doctest should be rewritten so it does not depend on the unspecified orders of cones in the fan and rays in the cones.
comment:11 Changed 2 years ago by
Milestone:  sage9.2 → sage9.3 

comment:12 Changed 21 months ago by
Milestone:  sage9.3 → sage9.4 

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:13 Changed 20 months ago by
Branch:  u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones → u/mkoeppe/construct_rationalpolyhedralfan_from_possibly_overlapping_cones 

comment:14 Changed 20 months ago by
Commit:  4371ee7f1702396985c648a059902bd4c5e45b48 → dd32a1209f8b55cf1ad99b51506a2d54b4e3ec0e 

comment:15 Changed 20 months ago by
Milestone:  sage9.4 → sage9.3 

Status:  needs_work → needs_review 
comment:16 Changed 20 months ago by
Commit:  dd32a1209f8b55cf1ad99b51506a2d54b4e3ec0e → 2018fdaac23fb0182f0f65d20bb023b6dc762928 

Branch pushed to git repo; I updated commit sha1. New commits:
2018fda  src/sage/geometry/fan.py: Make a doctest more stable by using 'sorted'

comment:17 Changed 20 months ago by
Reviewers:  → Matthias Koeppe 

Status:  needs_review → positive_review 
comment:18 Changed 20 months ago by
Milestone:  sage9.3 → sage9.4 

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review.
comment:19 Changed 19 months ago by
Status:  positive_review → needs_work 

********************************************************************** File "src/sage/geometry/fan.py", line 512, in sage.geometry.fan.? Failed example: for cone in sorted(fan.generating_cones()): print(sorted(cone.rays())) Expected: N(1, 0), N(2, 1) in 2d lattice N N(1, 2), N(2, 1) in 2d lattice N N(0, 1), N(1, 2) in 2d lattice N N(1, 2) in 2d lattice N Got: [N(1, 2)] [N(0, 1), N(1, 2)] [N(1, 0), N(2, 1)] [N(1, 2), N(2, 1)] ********************************************************************** 1 item had failures: 1 of 52 in sage.geometry.fan.? [523 tests, 1 failure, 3.67 s]  sage t long warnlong 43.7 randomseed=0 src/sage/geometry/fan.py # 1 doctest failed 
comment:20 Changed 19 months ago by
Branch:  u/mkoeppe/construct_rationalpolyhedralfan_from_possibly_overlapping_cones → u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones 

comment:21 Changed 19 months ago by
Commit:  2018fdaac23fb0182f0f65d20bb023b6dc762928 → 7a4d5fac1ec4ce957767fd4a2116011462cfde5b 

Status:  needs_work → needs_review 
New commits:
7a4d5fa  fix doctest bug introduced in commit 2018fda regarding sorted

comment:22 Changed 19 months ago by
Commit:  7a4d5fac1ec4ce957767fd4a2116011462cfde5b → 6bea8826faebc365483d3a468280b7231ba3b975 

Branch pushed to git repo; I updated commit sha1. New commits:
6bea882  make tox happy: Returns changed to Return

comment:23 Changed 19 months ago by
Status:  needs_review → positive_review 

comment:24 Changed 18 months ago by
Branch:  u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones → 6bea8826faebc365483d3a468280b7231ba3b975 

Resolution:  → fixed 
Status:  positive_review → closed 
What the result should be? The coarsest subdivision? And in what situations is it necessary?