Faster intersection between a hyperrectangular set and an axis-aligned halfspace

[mforets]

The intersection between a hyperrectangular set and an axis-aligned halfspace is currently slow:

julia> H = rand(Hyperrectangle)
Hyperrectangle{Float64,Array{Float64,1},Array{Float64,1}}([-1.4381908949978408, -0.8011047849004614], [2.3769552574965234, 1.2955065044055676])

julia> G = HalfSpace([1.0, 0.0], 0.0)
HalfSpace{Float64,Array{Float64,1}}([1.0, 0.0], 0.0)

julia> @btime intersection($G, $H)
  46.620 μs (334 allocations: 22.80 KiB)

HPolytope{Float64}(HalfSpace{Float64,VN} where VN<:AbstractArray{Float64,1}[HalfSpace{Float64,SingleEntryVector{Float64}}([1.0, 0.0], 0.0), HalfSpace{Float64,SingleEntryVector{Float64}}([0.0, 1.0], 0.49440171950510614), HalfSpace{Float64,SingleEntryVector{Float64}}([-1.0, 0.0], 3.815146152494364), HalfSpace{Float64,SingleEntryVector{Float64}}([0.0, -1.0], 2.096611289306029)])

Compare with:

julia> Q = Hyperrectangle(low=[-10., -10.], high=[0., 10]); # contains the intersection of H and G

julia> @btime intersection($Q, $H)
  108.345 ns (5 allocations: 416 bytes)
Hyperrectangle{Float64,Array{Float64,1},Array{Float64,1}}([-1.907573076247182, -0.8011047849004616], [1.907573076247182, 1.2955065044055676])

Note that by using single entry vectors, with the signature intersection(::HalfSpace{N, <:SingleEntryVector{N}}, ::AbstractHyperrectangle{N}), we are able to dispatch on axis-aligned halfspaces, so no run-time checks are needed.

[IssueHuntBot]

@mforets has funded $10.00 to this issue.

---

• Submit pull request via IssueHunt to receive this reward.
• Want to contribute? Chip in to this issue via IssueHunt.
• Checkout the IssueHunt Issue Explorer to see more funded issues.
• Need help from developers? Add your repository on IssueHunt to raise funds.

[IssueHuntBot]

@mforets has rewarded $9.00 to @sebastianguadalupe. See it on IssueHunt

• 💰 Total deposit: $10.00
• 🎉 Repository reward(0%): $0.00
• 🔧 Service fee(10%): $1.00