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: sage-9.4
Component: geometry Keywords: RationalPolyhedralFan, cone arrangement, IMA-PolyGeom
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:

Status badges

Description (last modified by yzh)

Given a cone arrangement where the cones are not necessarily face-to-face, construct a rational polyhedral fan that is a subdivision of the cone arrangement. This could be useful for topological computations with non-convex 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 novoselt

What the result should be? The coarsest subdivision? And in what situations is it necessary?

comment:2 Changed 3 years ago by yzh

  • Cc novoselt vbraun moritz jipilab mkoeppe added
  • Description modified (diff)
  • Keywords RationalPolyhedralFan cone arrangement IMA-PolyGeom added

comment:3 Changed 3 years ago by yzh

  • Branch set to u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones

comment:4 Changed 3 years ago by yzh

  • Commit set to 984ba246406648168236b7a9173a1ce5cb81291c
  • Status changed from new to needs_review

New commits:

984ba24implement allow_arrangement option in Fan constructor

comment:5 Changed 3 years ago by moritz

Please put your name as an author, yzh

comment:6 Changed 3 years ago by yzh

  • Authors set to Yuan Zhou

comment:7 Changed 3 years ago by mkoeppe

allow_arrangement is misspelled once in the documentation

comment:8 Changed 3 years ago by git

  • Commit changed from 984ba246406648168236b7a9173a1ce5cb81291c to 4371ee7f1702396985c648a059902bd4c5e45b48

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

4371ee7fix a typo in documentation

comment:9 Changed 14 months ago by mkoeppe

  • Milestone changed from sage-8.2 to sage-9.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 mkoeppe

  • 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 2-d lattice N
    N(1, 2),
    N(2, 1)
    in 2-d lattice N
    N(1, 2),
    N(0, 1)
    in 2-d lattice N
    N(-1, -2)
    in 2-d lattice N
Got:
    N(2, 1),
    N(1, 0)
    in 2-d lattice N
    N(1, 2),
    N(2, 1)
    in 2-d lattice N
    N(1, 2),
    N(0, 1)
    in 2-d lattice N
    N(-1, -2)
    in 2-d 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 mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:12 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

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

comment:13 Changed 3 months ago by mkoeppe

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

  • Commit changed from 4371ee7f1702396985c648a059902bd4c5e45b48 to dd32a1209f8b55cf1ad99b51506a2d54b4e3ec0e

Rebased on 9.3.beta6


New commits:

dd32a12implement allow_arrangement option in Fan constructor

comment:15 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.3
  • Status changed from needs_work to needs_review

comment:16 Changed 3 months ago by git

  • Commit changed from dd32a1209f8b55cf1ad99b51506a2d54b4e3ec0e to 2018fdaac23fb0182f0f65d20bb023b6dc762928

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

2018fdasrc/sage/geometry/fan.py: Make a doctest more stable by using 'sorted'

comment:17 Changed 3 months ago by mkoeppe

  • Reviewers set to Matthias Koeppe
  • Status changed from needs_review to positive_review

comment:18 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.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 vbraun

  • 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 2-d lattice N
    N(1, 2),
    N(2, 1)
    in 2-d lattice N
    N(0, 1),
    N(1, 2)
    in 2-d lattice N
    N(-1, -2)
    in 2-d 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 --warn-long 43.7 --random-seed=0 src/sage/geometry/fan.py  # 1 doctest failed
----------------------------------------------------------------------

comment:20 Changed 6 weeks ago by yzh

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

  • Commit changed from 2018fdaac23fb0182f0f65d20bb023b6dc762928 to 7a4d5fac1ec4ce957767fd4a2116011462cfde5b
  • Status changed from needs_work to needs_review

New commits:

7a4d5fafix doctest bug introduced in commit 2018fda regarding sorted

comment:22 Changed 6 weeks ago by git

  • Commit changed from 7a4d5fac1ec4ce957767fd4a2116011462cfde5b to 6bea8826faebc365483d3a468280b7231ba3b975

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

6bea882make tox happy: Returns changed to Return

comment:23 Changed 6 weeks ago by mkoeppe

  • Status changed from needs_review to positive_review

comment:24 Changed 4 weeks ago by vbraun

  • Branch changed from u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones to 6bea8826faebc365483d3a468280b7231ba3b975
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.