FaceFan and NormalFan should work with (non-lattice) polyhedra

[mmarco]

It would be nice if face/normal fans could be constructed from a generic (QQ-)polytope and not just from a lattice polytope:

sage: R.<x,y,z>=ZZ[]
sage: f=x*R.random_element()+y*R.random_element()+z*R.random_element()
sage: Q=f.newton_polytope()
sage: NormalFan(Q)
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)

/home/mmarco/sage-5.0/<ipython console> in <module>()

/home/mmarco/sage-5.0/local/lib/python2.7/site-packages/sage/geometry/fan.pyc in NormalFan(polytope, lattice)
    626         (N(0, 1), N(-1, 0))
    627     """
--> 628     rays = (polytope.facet_normal(i) for i in range(polytope.nfacets()))
    629     cones = (vertex.facets() for vertex in polytope.faces(dim=0))
    630     fan = Fan(cones, rays, lattice=lattice, check=False)

AttributeError: 'Polyhedron_QQ_ppl' object has no attribute 'nfacets'

[vbraun]

NormalFan takes a lattice polytope as argument, not any QQ-polytope:

sage: NormalFan(Q.lattice_polytope())
Rational polyhedral fan in 3-d lattice N

Having said that, it would be nice if any polytope would work.

[novoselt]

Normal fans require full-dimensional polytopes, but it is not necessary to contain the origin.

[vbraun]

Updated patch

[vbraun]

True, I removed the interior point check.

[novoselt]

I think the normal fan is defined for non-compact polytopes as well - rays are normals to facets (hence we need full-dimensionality) and higher dimensional cones are given by smaller dimensional faces. I don't insist on implementing it, but perhaps NotImplementedError is more suitable than ValueError?

[novoselt]

novoselt@sage ~/sage/devel/sage-main $ hg qapplied
trac2607.patch
trac2607-whitespace.2.patch
trac_2607_renaming.3.patch
trac2607-doctest-and-spacing.patch
trac_12965_rational_class_group_lattice.patch
trac_13052-is-positive-definite-RDF-v2.patch
trac_12544_switch_cones_to_PointCollection_folded.patch
trac_13191_auto_fan_2d.patch
trac_13191_reviewer.patch
trac_13194_polytope_fan_construct.patch

11 doctests fail in fan.py with this queue (on 5.1.rc1) with messages like

AttributeError: 'list' object has no attribute 'incident'
AttributeError: 'Polyhedron_QQ_ppl' object has no attribute 'dilation'

Does this patch depend on new polyhedral code as well?

[vbraun]

This patch doesn't require anything on top of sage-5.9.beta2.

Note the follow-up #14394 since I though that this ticket had been merged a long time ago.