Skip to content

Inclusion check with VRep sets should use VRep algorithm #2708

@schillic

Description

@schillic

The following should work without Polyhedra:

julia> P = rand(VPolytope);
julia> P  P
ERROR: AssertionError: package 'Polyhedra' not loaded (it is required for executing `default_polyhedra_backend`)
Stacktrace:
 [1] macro expansion
   @ ~/.julia/dev/LazySets/src/Assertions/Assertions.jl:23 [inlined]
 [2] require(package::Symbol; fun_name::String, explanation::String)
   @ LazySets ~/.julia/dev/LazySets/src/init.jl:37
 [3] default_polyhedra_backend(P::VPolytope{Float64, Vector{Float64}})
   @ LazySets ~/.julia/dev/LazySets/src/Interfaces/AbstractPolyhedron_functions.jl:29
 [4] tohrep(P::VPolytope{Float64, Vector{Float64}})
   @ LazySets ~/.julia/dev/LazySets/src/Sets/VPolytope.jl:465
 [5] constraints_list(P::VPolytope{Float64, Vector{Float64}})
   @ LazySets ~/.julia/dev/LazySets/src/Sets/VPolytope.jl:386
 [6] _issubset_constraints_list(S::VPolytope{Float64, Vector{Float64}}, P::VPolytope{Float64, Vector{Float64}}, witness::Bool)
   @ LazySets ~/.julia/dev/LazySets/src/ConcreteOperations/issubset.jl:282
 [7] issubset(X::VPolytope{Float64, Vector{Float64}}, P::VPolytope{Float64, Vector{Float64}}, witness::Bool) (repeats 2 times)
   @ LazySets ~/.julia/dev/LazySets/src/ConcreteOperations/issubset.jl:297

This is the method that is currently used:

for ST in [AbstractPolytope, AbstractHyperrectangle, LineSegment]
@eval (X::($ST), P::AbstractPolyhedron, witness::Bool=false) = _issubset_constraints_list(X, P, witness)
end

We should probably use this method:

function (P::AbstractPolytope, S::LazySet, witness::Bool=false;
algorithm=_default_issubset(P, S))
@assert dim(P) == dim(S)
if algorithm == "constraints"
return _issubset_constraints_list(P, S, witness)
elseif algorithm == "vertices"
return _issubset_vertices_list(P, S, witness)
else
error("algorithm $algorithm unknown")
end
end

Note that this method should be adapted if both arguments prefer the VRep:

@inline function _default_issubset(P, S)
if applicable(constraints_list, S)
return "constraints"
else
return "vertices"
end
end

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions