Opened 3 years ago
Closed 4 weeks ago
#25122 closed enhancement (fixed)
Construct RationalPolyhedralFan from possibly overlapping cones
Reported by:  yzh  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  geometry  Keywords:  RationalPolyhedralFan, cone arrangement, IMAPolyGeom 
Cc:  novoselt, vbraun, moritz, jipilab, mkoeppe  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 3 years ago by
comment:2 Changed 3 years ago by
 Cc novoselt vbraun moritz jipilab mkoeppe added
 Description modified (diff)
 Keywords RationalPolyhedralFan cone arrangement IMAPolyGeom added
comment:3 Changed 3 years ago by
 Branch set to u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones
comment:4 Changed 3 years ago by
 Commit set to 984ba246406648168236b7a9173a1ce5cb81291c
 Status changed from new to needs_review
New commits:
984ba24  implement allow_arrangement option in Fan constructor

comment:5 Changed 3 years ago by
Please put your name as an author, yzh
comment:6 Changed 3 years ago by
comment:7 Changed 3 years ago by
allow_arrangement
is misspelled once in the documentation
comment:8 Changed 3 years ago by
 Commit changed from 984ba246406648168236b7a9173a1ce5cb81291c to 4371ee7f1702396985c648a059902bd4c5e45b48
Branch pushed to git repo; I updated commit sha1. New commits:
4371ee7  fix a typo in documentation

comment:9 Changed 14 months ago by
 Milestone changed from sage8.2 to sage9.2
Moving some tickets to 9.2. This is not a promise that I will be working on them.
comment:10 Changed 13 months ago by
 Status changed from needs_review to 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 10 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:12 Changed 3 months ago by
 Milestone changed from sage9.3 to sage9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:13 Changed 3 months ago by
 Branch changed from u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones to u/mkoeppe/construct_rationalpolyhedralfan_from_possibly_overlapping_cones
comment:14 Changed 3 months ago by
 Commit changed from 4371ee7f1702396985c648a059902bd4c5e45b48 to dd32a1209f8b55cf1ad99b51506a2d54b4e3ec0e
comment:15 Changed 3 months ago by
 Milestone changed from sage9.4 to sage9.3
 Status changed from needs_work to needs_review
comment:16 Changed 3 months ago by
 Commit changed from dd32a1209f8b55cf1ad99b51506a2d54b4e3ec0e to 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 3 months ago by
 Reviewers set to Matthias Koeppe
 Status changed from needs_review to positive_review
comment:18 Changed 3 months ago by
 Milestone changed from sage9.3 to 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 6 weeks ago by
 Status changed from positive_review to 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 6 weeks ago by
 Branch changed from u/mkoeppe/construct_rationalpolyhedralfan_from_possibly_overlapping_cones to u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones
comment:21 Changed 6 weeks ago by
 Commit changed from 2018fdaac23fb0182f0f65d20bb023b6dc762928 to 7a4d5fac1ec4ce957767fd4a2116011462cfde5b
 Status changed from needs_work to needs_review
New commits:
7a4d5fa  fix doctest bug introduced in commit 2018fda regarding sorted

comment:22 Changed 6 weeks ago by
 Commit changed from 7a4d5fac1ec4ce957767fd4a2116011462cfde5b to 6bea8826faebc365483d3a468280b7231ba3b975
Branch pushed to git repo; I updated commit sha1. New commits:
6bea882  make tox happy: Returns changed to Return

comment:23 Changed 6 weeks ago by
 Status changed from needs_review to positive_review
comment:24 Changed 4 weeks ago by
 Branch changed from u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones to 6bea8826faebc365483d3a468280b7231ba3b975
 Resolution set to fixed
 Status changed from positive_review to closed
What the result should be? The coarsest subdivision? And in what situations is it necessary?