is_intersection_empty for polytopes

[mforets]

julia> using LazySets, Polyhedra

julia> A, B = HPolytope(rand(10, 2), rand(10)), HPolytope(rand(10, 2), rand(10));

julia> is_intersection_empty(A, B)
ERROR: MethodError: no method matching is_intersection_empty(::LazySets.HPolytope{Float64}, ::LazySets.HPolytope{Float64})
Closest candidates are:
  is_intersection_empty(::LazySets.AbstractSingleton{N<:Real}, ::LazySets.LazySet{N<:Real}) where N<:Real at /Users/forets/.julia/v0.6/LazySets/src/is_intersection_empty.jl:109
  is_intersection_empty(::LazySets.AbstractSingleton{N<:Real}, ::LazySets.LazySet{N<:Real}, ::Bool) where N<:Real at /Users/forets/.julia/v0.6/LazySets/src/is_intersection_empty.jl:109
  is_intersection_empty(::LazySets.LazySet{N<:Real}, ::LazySets.AbstractSingleton{N<:Real}) where N<:Real at /Users/forets/.julia/v0.6/LazySets/src/is_intersection_empty.jl:149
  ...

@kostakoida

[schillic]

I guess that this is just a call to Polyhedra, and that there is also the same function for vertex representation.

[mforets]

A naive implementation (that i would propose to write as a first algorithm) is to compute the concrete intersection and then check if the result has zero vertices.

A quick search shows that testing intersection can be done in better ways:

https://www.cs.jhu.edu/~misha/Spring16/Dobkin83.pdf
https://pdfs.semanticscholar.org/ea04/2850121948a98b7461b1430123a94f8f9634.pdf
https://stackoverflow.com/questions/753140/how-do-i-determine-if-two-convex-polygons-intersect