Projection of H-representation

This examples shows how to compute the projection of a H-representation. We use the project1.ine example from cddlib.

using Polyhedra

Projection with default library

h = LiftedHRepresentation{Float64}([
    1  0  0  0  1  0  0
    1  0  0  0  0  1  0
    1  0  0  0  0  0  1
    1  0  0  0 -1  0  0
    1  0  0  0  0 -1  0
    1  0  0  0  0  0 -1
    1  1  0  0 -1  0  0
    1  0  1  0  0 -1  0
    1  0  0  1  0  0 -1
    1 -1  0  0  1  0  0
    1  0 -1  0  0  1  0
    1  0  0 -1  0  0  1
    2  1  1  1 -1 -1 -1
    2 -1  1  1  1 -1 -1
    2  1 -1  1 -1  1 -1
    2  1  1 -1 -1 -1  1
    2 -1 -1  1  1  1 -1
    2  1 -1 -1 -1  1  1
    2 -1  1 -1  1 -1  1
    2 -1 -1 -1  1  1  1
])
p = polyhedron(convert(Polyhedra.Intersection{Float64,Vector{Float64},Int}, h))
Polyhedron DefaultPolyhedron{Float64, Polyhedra.Intersection{Float64, Vector{Float64}, Int64}, Polyhedra.Hull{Float64, Vector{Float64}, Int64}}:
20-element iterator of HalfSpace{Float64, Vector{Float64}}:
 HalfSpace([-0.0, -0.0, -0.0, -1.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0, -0.0, -1.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0, -0.0, -0.0, -1.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0, 1.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0, -0.0, 1.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0, -0.0, -0.0, 1.0], 1.0)
 HalfSpace([-1.0, -0.0, -0.0, 1.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -1.0, -0.0, -0.0, 1.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -1.0, -0.0, -0.0, 1.0], 1.0)
 HalfSpace([1.0, -0.0, -0.0, -1.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, 1.0, -0.0, -0.0, -1.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, 1.0, -0.0, -0.0, -1.0], 1.0)
 HalfSpace([-1.0, -1.0, -1.0, 1.0, 1.0, 1.0], 2.0)
 HalfSpace([1.0, -1.0, -1.0, -1.0, 1.0, 1.0], 2.0)
 HalfSpace([-1.0, 1.0, -1.0, 1.0, -1.0, 1.0], 2.0)
 HalfSpace([-1.0, -1.0, 1.0, 1.0, 1.0, -1.0], 2.0)
 HalfSpace([1.0, 1.0, -1.0, -1.0, -1.0, 1.0], 2.0)
 HalfSpace([-1.0, 1.0, 1.0, 1.0, -1.0, -1.0], 2.0)
 HalfSpace([1.0, -1.0, 1.0, -1.0, 1.0, -1.0], 2.0)
 HalfSpace([1.0, 1.0, 1.0, -1.0, -1.0, -1.0], 2.0)

The projection is going to first compute the V-representation, and then project this V-representation. Only the V-representation of the projected polyhedron will be known.

project(p, 1:3)
Polyhedron DefaultPolyhedron{Float64, Polyhedra.Intersection{Float64, Vector{Float64}, Int64}, Polyhedra.Hull{Float64, Vector{Float64}, Int64}}:
96-element iterator of Vector{Float64}:
 [2.0, 1.0, 2.0]
 [0.0, 1.0, 2.0]
 [1.0, 2.0, 2.0]
 [-1.0, 2.0, 2.0]
 [2.0, 2.0, 1.0]
 [0.0, 2.0, 1.0]
 [1.0, 0.0, 2.0]
 [-1.0, 0.0, 2.0]
 [0.0, 1.0, 2.0]
 [-2.0, 1.0, 2.0]
 [0.0, 2.0, 1.0]
 [-2.0, 2.0, 1.0]
 [1.0, 2.0, 0.0]
 [-1.0, 2.0, 0.0]
 [2.0, 0.0, 1.0]
 [0.0, 0.0, 1.0]
 [2.0, 1.0, 0.0]
 [0.0, 1.0, 0.0]
 [1.0, 0.0, 0.0]
 [-1.0, 0.0, 0.0]
  ⋮

CDDLib

With CDDLib, you the default projection when the eliminated variables is not only the last dimension is BlockElimination: For this method, the H-representation of the projected set is obtained:

import CDDLib
p = polyhedron(h, CDDLib.Library())
Polyhedron CDDLib.Polyhedron{Float64}:
20-element iterator of HalfSpace{Float64, Vector{Float64}}:
 HalfSpace([-0.0, -0.0, -0.0, -1.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0, -0.0, -1.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0, -0.0, -0.0, -1.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0, 1.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0, -0.0, 1.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0, -0.0, -0.0, 1.0], 1.0)
 HalfSpace([-1.0, -0.0, -0.0, 1.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -1.0, -0.0, -0.0, 1.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -1.0, -0.0, -0.0, 1.0], 1.0)
 HalfSpace([1.0, -0.0, -0.0, -1.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, 1.0, -0.0, -0.0, -1.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, 1.0, -0.0, -0.0, -1.0], 1.0)
 HalfSpace([-1.0, -1.0, -1.0, 1.0, 1.0, 1.0], 2.0)
 HalfSpace([1.0, -1.0, -1.0, -1.0, 1.0, 1.0], 2.0)
 HalfSpace([-1.0, 1.0, -1.0, 1.0, -1.0, 1.0], 2.0)
 HalfSpace([-1.0, -1.0, 1.0, 1.0, 1.0, -1.0], 2.0)
 HalfSpace([1.0, 1.0, -1.0, -1.0, -1.0, 1.0], 2.0)
 HalfSpace([-1.0, 1.0, 1.0, 1.0, -1.0, -1.0], 2.0)
 HalfSpace([1.0, -1.0, 1.0, -1.0, 1.0, -1.0], 2.0)
 HalfSpace([1.0, 1.0, 1.0, -1.0, -1.0, -1.0], 2.0)

FourierMotzkin can be used instead as follows. This method also obtains the H-representation of the projected set.

project(p, 1:3, FourierMotzkin())
Polyhedron CDDLib.Polyhedron{Float64}:
4835-element iterator of HalfSpace{Float64, Vector{Float64}}:
 HalfSpace([-0.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -1.0], 2.0)
 HalfSpace([-0.0, -0.0, 1.0], 2.0)
 HalfSpace([-0.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -1.0, -0.0], 2.0)
 HalfSpace([-0.0, -1.0, -0.0], 3.0)
 HalfSpace([-0.0, -1.0, -0.0], 3.0)
 HalfSpace([-0.0, 1.0, -0.0], 2.0)
 HalfSpace([-0.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -1.0], 3.0)
 HalfSpace([-0.0, -0.0, -1.0], 6.0)
 HalfSpace([-0.0, -0.0, -0.0], 1.0)
 HalfSpace([-0.0, -0.0, -1.0], 6.0)
  ⋮

To compute the projection by first computing the V-representation and then projecting it like it was done for the default library, use ProjectGenerators.

project(p, 1:3, ProjectGenerators())
Polyhedron CDDLib.Polyhedron{Float64}:
96-element iterator of Vector{Float64}:
 [-1.0, -2.0, 0.0]
 [-1.0, -2.0, 2.0]
 [-1.0, 0.0, 0.0]
 [-1.0, 0.0, 2.0]
 [1.0, -2.0, 0.0]
 [1.0, -2.0, 2.0]
 [1.0, 0.0, 0.0]
 [1.0, 0.0, 2.0]
 [0.0, 1.0, 2.0]
 [0.0, 1.0, 0.0]
 [0.0, -1.0, 2.0]
 [0.0, -1.0, 0.0]
 [-2.0, 1.0, 2.0]
 [-2.0, 1.0, 0.0]
 [-2.0, -1.0, 2.0]
 [-2.0, -1.0, 0.0]
 [-1.0, 0.0, 0.0]
 [-1.0, 0.0, 2.0]
 [-1.0, 2.0, 0.0]
 [-1.0, 2.0, 2.0]
  ⋮

This page was generated using Literate.jl.