Opened 5 years ago

Closed 18 months ago

# Construct RationalPolyhedralFan from possibly overlapping cones

Reported by: Owned by: Yuan Zhou major sage-9.4 geometry RationalPolyhedralFan, cone arrangement, IMA-PolyGeom Andrey Novoseltsev, Volker Braun, Moritz Firsching, Jean-Philippe Labbé, Matthias Köppe Yuan Zhou Matthias Koeppe N/A 6bea882 6bea8826faebc365483d3a468280b7231ba3b975

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
```

### comment:1 Changed 5 years ago by Andrey Novoseltsev

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

### comment:2 Changed 5 years ago by Yuan Zhou

Cc: Andrey Novoseltsev Volker Braun Moritz Firsching Jean-Philippe Labbé Matthias Köppe added modified (diff) RationalPolyhedralFan cone arrangement IMA-PolyGeom added

### comment:3 Changed 5 years ago by Yuan Zhou

Branch: → u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones

### comment:4 Changed 5 years ago by Yuan Zhou

Commit: → 984ba246406648168236b7a9173a1ce5cb81291c new → needs_review

New commits:

 ​984ba24 `implement allow_arrangement option in Fan constructor`

### comment:6 Changed 5 years ago by Yuan Zhou

Authors: → Yuan Zhou

### comment:7 Changed 5 years ago by Matthias Köppe

`allow_arrangement` is misspelled once in the documentation

### comment:8 Changed 5 years ago by git

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 Matthias Köppe

Milestone: sage-8.2 → sage-9.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 Matthias Köppe

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 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 2 years ago by Matthias Köppe

Milestone: sage-9.2 → sage-9.3

### comment:12 Changed 21 months ago by Matthias Köppe

Milestone: sage-9.3 → sage-9.4

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

### comment:13 Changed 20 months ago by Matthias Köppe

Branch: u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones → u/mkoeppe/construct_rationalpolyhedralfan_from_possibly_overlapping_cones

### comment:14 Changed 20 months ago by Matthias Köppe

Rebased on 9.3.beta6

New commits:

 ​dd32a12 `implement allow_arrangement option in Fan constructor`

### comment:15 Changed 20 months ago by Matthias Köppe

Milestone: sage-9.4 → sage-9.3 needs_work → needs_review

### comment:16 Changed 20 months ago by git

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 Matthias Köppe

Reviewers: → Matthias Koeppe needs_review → positive_review

### comment:18 Changed 20 months ago by Matthias Köppe

Milestone: sage-9.3 → 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 19 months ago by Volker Braun

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 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 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 19 months ago by Yuan Zhou

Branch: u/mkoeppe/construct_rationalpolyhedralfan_from_possibly_overlapping_cones → u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones

### comment:21 Changed 19 months ago by Yuan Zhou

Commit: 2018fdaac23fb0182f0f65d20bb023b6dc762928 → 7a4d5fac1ec4ce957767fd4a2116011462cfde5b needs_work → needs_review

New commits:

 ​7a4d5fa `fix doctest bug introduced in commit 2018fda regarding sorted`

### comment:22 Changed 19 months ago by git

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 Matthias Köppe

Status: needs_review → positive_review

### comment:24 Changed 18 months ago by Volker Braun

Branch: u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones → 6bea8826faebc365483d3a468280b7231ba3b975 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.