Class Polyhedron

A class for polyhedral objects.  Architecture is still in flux.
Do not instantiate with both vertex/ray and ieq/linearity data:
no consistency check is made.

EXAMPLES:
    sage: square_from_vertices = Polyhedron(vertices = [[1, 1], [1, -1], [-1, 1], [-1, -1]])
    sage: square_from_ieqs = Polyhedron(ieqs = [[1, 0, 1], [1, 1, 0], [1, 0, -1], [1, -1, 0]])
    sage: square_from_ieqs.vertices()
    [[1, -1], [1, 1], [-1, 1], [-1, -1]]
    sage: square_from_vertices.ieqs()
    [[1, 0, 1], [1, 1, 0], [1, 0, -1], [1, -1, 0]]

Overrides: object.__init__

Returns a description of the object.

EXAMPLES:
    sage: poly_test = Polyhedron(vertices = [[1,2,3,4],[2,1,3,4],[4,3,2,1]])
    sage: poly_test._repr_()
    'A Polyhedron with 3 vertices.'
    sage: grammar_test = Polyhedron(vertices = [[1,1,1,1,1,1]])
    sage: grammar_test._repr_()
    'A Polyhedron with 1 vertex.'

Returns the dimension of the polyhedron.

EXAMPLES:
    sage: standard_simplex = Polyhedron(vertices = [[1,0,0,0],[0,0,0,1],[0,1,0,0],[0,0,1,0]])
    sage: standard_simplex.dim()
    3

Tests for simplicity of a polytope.

EXAMPLES:
    sage: p = Polyhedron([[0,0,0],[1,0,0],[0,1,0],[0,0,1]])
    sage: p.remove_redundant_vertices()
    sage: p.is_simple()
    True
    sage: p = Polyhedron([[0,0,0],[4,4,0],[4,0,0],[0,4,0],[2,2,2]])
    sage: p.is_simple()
    False

Addition of two polyhedra is defined as their Minkowski sum.

EXAMPLES:
    sage: four_cube = n_cube(4)
    sage: four_simplex = Polyhedron(vertices = [[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]])
    sage: unholy_union = four_cube + four_simplex
    sage: unholy_union.dim()
    4

Returns the vertices of the polyhedron.

EXAMPLES:
    sage: a_simplex = Polyhedron(ieqs = [[0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1]], linearities = [[1,-1,-1,-1,-1]])
    sage: a_simplex.vertices()
    [[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]]

Return the inequalities (half-planes) defining the polyhedron.

EXAMPLES:
    sage: permuto4 = Polyhedron(vertices = permutations([1,2,3,4,5]))
    sage: ieqs = permuto4.ieqs()
    sage: ieqs[0]
    [-1, 0, 0, 0, 1, 0]
    sage: ieqs[-1]
    [5, -1, 0, 0, 0, 0]

Returns a list of vertex indices and their adjacent vertices.

EXAMPLES:
    sage: permuto3 = Polyhedron(vertices = permutations([1,2,3,4]))
    sage: permuto3.vertex_adjacencies()[0:3]
    [[3, [5, 1, 9]], [5, [3, 4, 11]], [16, [22, 10, 17]]]

Returns a list of face indices and the indices of faces adjacent to them.

EXMAPLES:
    sage: permuto3 = Polyhedron(vertices = permutations([1,2,3,4]))
    sage: permuto3.facial_adjacencies()[0:3]
    [[0, [1, 2, 3, 8, 12, 13, 14]],
    [1, [0, 2, 9, 13, 14]],
    [2, [0, 1, 3, 4, 5, 9, 14]]]

Returns the linear constraints of the polyhedron. As with
inequalities, each constraint is given as [b -a1 -a2 ... an]
where for variables x1, x2,..., xn, the polyhedron satisfies
the equation b = a1*x1 + a2*x2 + ... + an*xn.

EXAMPLES:
    sage: test_p = Polyhedron(vertices = [[1,2,3,4],[2,1,3,4],[4,3,2,1],[3,4,1,2]])
    sage: test_p.linearities()
    [[-10, 1, 1, 1, 1]]

Removes vertices from the description of the polyhedron which
do not affect the convex hull.  Now done automatically when a
polyhedron is defined by vertices.

EXAMPLES:
    sage: a_triangle = Polyhedron([[0,0,0],[4,0,0],[0,4,0],[1,1,0]])
    sage: a_triangle.vertices()
    [[0, 0, 0], [4, 0, 0], [0, 4, 0]]
    sage: a_triangle.remove_redundant_vertices()
    sage: a_triangle.vertices()
    [[0, 0, 0], [4, 0, 0], [0, 4, 0]]

Returns the rays.  This function does not ensure that redundant
rays have been removed.

EXAMPLES:
    sage: positive_orthant = Polyhedron(ieqs = [[0,1,0,0],[0,0,1,0],[0,0,0,1]])
    sage: positive_orthant.rays()
    [[1, 0, 0], [0, 1, 0], [0, 0, 1]]

Returns the face-vertex incidences in the form [face_index, [v_i_0, v_i_1,,v_i_2]]

EXAMPLES:
    sage: p = Polyhedron(vertices = [[5,0,0],[0,5,0],[5,5,0],[0,0,0],[2,2,5]])
    sage: p.facial_incidences()
    [[0, [1, 3, 4]],
    [1, [0, 3, 4]],
    [2, [0, 2, 4]],
    [3, [1, 2, 4]],
    [4, [0, 1, 2, 3]]]

WARNING: EXPERIMENTAL
Returns a list of the form [face_index, [v_i_0, v_i_1,,v_i_2]]
where the face_index refers to the original defining inequality.
For a given face, the collection of triangles formed by each
triple of v_i should triangulate that face.
This is computed by randomly lifting each face up a dimension; this does not always work!

NOTE:
    The doctest below is very weak, since it does not have to create a triangulation.

EXAMPLES:
    sage: p = Polyhedron(vertices = [[5,0,0],[0,5,0],[5,5,0],[2,2,5]])
    sage: len(p.triangulated_facial_incidences())
    4

For polytopes in 2 or 3 dimensions, returns the edges
as a list of lines.

EXAMPLES:
    sage: p = Polyhedron([[1,2,],[1,1],[0,0]])
    sage: p_wireframe = p.render_wireframe()
    sage: p_wireframe._Graphics__objects
    [Line defined by 2 points, Line defined by 2 points, Line defined by 2 points]