How to take union of interval elements in Interval Vector?

General Usage
1

Hello,

I have an interval vector of the form as

X = [ [0,0.1], [1,2], [0.1,0.2], [9,10], [2,3], [0.2,0.3], [10,11], [2,3], [9,10] ]

I wish to get it in the form as

Y = [ [0,0.3], [1,3], [9,11] ]

I am using the “IntervalArithmetic.jl” package.
In an actual case, there are 100s of such elements.
How can I get the union of interval elements which are continuous (the higher end point of one interval is the same as the lower end point of the second interval, e.g. [1,2] and [2,3] are continuous)?

Thank you in advance

2

What do you want to do with intervals that are inside another e.g. [ [0, 3], [1, 2] ] or partially overlap e.g. [ [0, 2], [1, 3] ]?

Assuming you just want unions, this is a straightforward way. However, bear in mind that the way you wrote X, it is promoted to Vector{Vector{Float64}}, that is all the integers become floats. You could try to change the type of X to contain Vector{Int64} too, but the code has to become more complicated to update intervals when int intervals and float intervals overlap e.g. [ [0, 2], [1.2, 3.1] ].

function XtoY!(X) # sorts X in-place
    Y = eltype(X)[]
    # sort X in-place by inner vector's 1st element
    sort!(X; by = function (x) x[begin] end)
    # start Y with sorted X's 1st element
    push!(Y, first(X))
    for Xi in X
        # extend end if interval overlaps
        if Xi[begin] <= last(Y)[end]
            last(Y)[end] = Xi[end]
        else # add new interval to Y
            push!(Y, Xi)
        end
    end
    return Y
end
1 Like
3

You could use Home · Intervals.jl (invenia.github.io) which has the intersect function for IntervalSets that returns a vector of intervals.

5 Likes
4

A vector does not seem like an appropriate data structure for representing intervals, since they do not structurally encode the information that an interval is described by exactly two numbers. Vectors are also inefficient.

Have you considered using an more lightweight and efficient data structure like Tuple{Float64, Float64}?

1 Like
5

It’s not meant to be an actual alternative to @Benny’s solution, but just an exercise on Julia’s functions


using IterTools

X1=unique(sort(X, by=first))

ie(f,vi)=f.(f.(groupby(let s=[vi[1]]; c-> s = c[1] == last(s)[2]  ? push!(s,c) : [c]  end, vi)))

ff=ie(first,X1)
ll=ie(last,X1)

res=tuple.(ff,ll)



reduce((s,c)-> c[1] <=last(s)[2] ? [s[1:end-1];[[s[end][1],c[2]]]] : [s;[c]], sort(X, by=first),init=[X[1]])
 

using Base.Iterators
Xu=[-Inf; unique(sort(X,by=first));+Inf]

collect(partition(collect(flatten(Iterators.filter(x->first(x)< last(x),partition(flatten(Xu),2))))[2:end-1],2))
1 Like
6

To make SteffenPL’s answer more explicit, here is some code:

julia> using Intervals

julia> [Interval(v[1],v[2]) for v in X]
9-element Vector{Interval{Float64, Closed, Closed}}:
 Interval{Float64, Closed, Closed}(0.0, 0.1)
 Interval{Float64, Closed, Closed}(1.0, 2.0)
 Interval{Float64, Closed, Closed}(0.1, 0.2)
 Interval{Float64, Closed, Closed}(9.0, 10.0)
 Interval{Float64, Closed, Closed}(2.0, 3.0)
 Interval{Float64, Closed, Closed}(0.2, 0.3)
 Interval{Float64, Closed, Closed}(10.0, 11.0)
 Interval{Float64, Closed, Closed}(2.0, 3.0)
 Interval{Float64, Closed, Closed}(9.0, 10.0)

julia> IntervalSet([Interval(v[1],v[2]) for v in X])
3-interval IntervalSet{Interval{Float64, Closed, Closed}}:
[0.0 .. 0.3]
[1.0 .. 3.0]
[9.0 .. 11.0]

intersect is useful, but why would it be needed here?

BTW:

julia> @btime IntervalSet([Interval(v[1],v[2]) for v in $X]);
  70.044 ns (1 allocation: 208 bytes)

Intervals seems very efficient.

5 Likes
7

Could you check something? I looked into the docs and source code, and the method that does the work seems to be union!(intervals::IntervalSet). Interestingly, union!/union is not called in the IntervalSet constructor, but in the Base.show method for displaying IntervalSet in the REPL. Since trailing semicolons suppress REPL display, maybe your benchmark is not doing union at all. However, I’m not sure whether semicolons elide show or ignore it after its call. Could you benchmark a union! call and see if that changes things?

2 Likes
8 
julia> @btime IntervalSet([Interval(v[1],v[2]) for v in $X])
  70.460 ns (1 allocation: 208 bytes)
3-interval IntervalSet{Interval{Float64, Closed, Closed}}:
[0.0 .. 0.3]
[1.0 .. 3.0]
[9.0 .. 11.0]

julia> @btime union!(IntervalSet([Interval(v[1],v[2]) for v in $X]))
  255.945 ns (2 allocations: 272 bytes)
3-interval IntervalSet{Interval{Float64, Closed, Closed}}:
[0.0 .. 0.3]
[1.0 .. 3.0]
[9.0 .. 11.0]

Slower, but still efficient. Good observation @Benny

2 Likes
9

Dear @Benny

Thank you.

Yes, I want to do union with intervals that are inside another e.g. [ [0, 3], [1, 2] ] or partially overlap e.g. [ [0, 2], [1, 3] ].
Also, I am using “IntervalArithmetic.jl” package to solve my problem.

1 Like
10

Dear @Dan,

Thank you.

When I am using “Intervals.jl” with “IntervalArithmetic.jl” package, then my code is showing some errors, e.g. .. and mince are not defined. I am using “IntervalArithmetic.jl” package in my algorithm. Can’t we use both packages together?

Thank you

11

There is also exist an UnitRangesSortedSets.jl with standard union and intersect operations.

1 Like
12

You could do something like within IntervalArithemtic:

julia> using IntervalArithmetic

julia> X = [Interval(0.0, 0.1), Interval(1,2), Interval(0.1, 0.2), Interval(9,10), Interval(2,3), Interval(0.2, 0.3), Interval(10,11), Interval(2,3), Interval(9,10)];

julia> XY = Set{Interval{Float64}}()
Set{Interval{Float64}}()

julia> for x in X
    any(x .⊆ XY) && continue
    for y in X
        (x == y || isempty(x ∩ y)) && continue
        x = hull(x, y)
    end
    push!(XY, x)
end

julia> XY
Set{Interval{Float64}} with 3 elements:
  [0, 0.3]
  [1, 3]
  [9, 11]
2 Likes
13

Thank you so much @lbenet. This solution worked really well for my problem.

1 Like
14

what should be the output for this X?

X1= [Interval(1,2), Interval(0.1, 0.2),  Interval(0.0, 0.1),   Interval(0.3,0.4), Interval(0.2, 0.3)]
2 Likes
15

To demonstrate rocco_sprmnt21’s point:

julia> X= [Interval(1, 2),  Interval(3,4), Interval(2, 3)];

julia> XY = Set{Interval{Float64}}();

julia> for x in X
           any(x .⊆ XY) && continue
           for y in X
        (x == y || isempty(x ∩ y)) && continue
        x = hull(x, y)
           end
           push!(XY, x)
       end

julia> XY
Set{Interval{Float64}} with 2 elements:
  [1, 3]
  [2, 4] :(
2 Likes
16

Another option for ArithmeticIntervals package:

function mergeclosed(X)
    b=-1
    r=Interval[]
    foldl(sort!([[(x,-1) for x in inf.(X)];
                 [(x,1) for x in sup.(X)]]); init=0) do s,(p,e)
        s==0 && (b = p)
        s=s+e
        s==0 && push!(r,Interval(b,p))
        s
    end
    r 
end

Example:

julia> X = [Interval(0.0, 0.1), Interval(1,2), Interval(0.1, 0.2), Interval(9,10), Interval(2,3), Interval(0.2, 0.3), Interval(10,11), Interval(2,3), Interval(9,10)]
9-element Vector{Interval{Float64}}:
    [0, 0.100001]
   [1, 2]
       [0.1, 0.200001]
  [9, 10]
   [2, 3]
       [0.2, 0.3]
 [10, 11]
   [2, 3]
  [9, 10]

julia> mergeclosed(X)
3-element Vector{Interval}:
   [0, 0.3]
  [1, 3]
 [9, 11]
17 

function hullify(X)
    XY = Set{Interval{Float64}}()
    for x in X
        any(x .⊆ XY) && continue
        for y in X
            (x == y || isempty(x ∩ y)) && continue
            x = hull(x, y)
        end
        push!(XY, x)
    end
    XY==X && return XY
    hullify(XY)
end

PS
Convergence should be ensured by the fact that at each step the length of X decreases by 1, eventually reaching 1.

1 Like
18

Thank you so much @rocco_sprmnt21. It’s really helpful.

19

This function (not thoroughly tested) should be more efficient as it avoids the second for loop nested in the first and takes advantage of recursion, which would be necessary anyway.

function hullify1(X)
    XY = Vector{Interval{Float64}}()
    push!(XY,first(X))
     for y in X[2:end]
        h=findfirst(e->!isempty(e ∩ y),XY)
        if isnothing(h) 
            push!(XY,y)
        else
            XY[h]=hull(XY[h],y)
        end
     end
     #println(XY)
    XY==X && return XY
    hullify1(XY)
end
Summary 
julia> using IntervalArithmetic, BenchmarkTools

julia> X = [Interval(0.0, 0.1), Interval(1,2), Interval(0.1, 0.2), Interval(9,10), Interval(2,3), Interval(0.2, 0.3), Interval(10,11), Interval(2,3), Interval(9,10)];

julia> function hullify1(X)
           XY = Vector{Interval{Float64}}()
           push!(XY,first(X))
            for y in X[2:end]
               h=findfirst(e->!isempty(e ∩ y),XY)
               if isnothing(h) 
                   push!(XY,y)
               else
                   XY[h]=hull(XY[h],y)
               end
            end
            #println(XY)
           XY==X && return XY
           hullify1(XY)
       end
hullify1 (generic function with 1 method)

julia> function hullify(X)
           XY = Set{Interval{Float64}}()
           for x in X
               any(x .⊆ XY) && continue
               for y in X
                   (x == y || isempty(x ∩ y)) && continue
                   x = hull(x, y)
               end
               push!(XY, x)
           end
           XY==X && return XY
           hullify(XY)
       end
hullify (generic function with 1 method)

julia> X = [Interval(0.0, 0.1), Interval(1,2), Interval(0.1, 0.2), Interval(9,10), Interval(2,3), Interval(0.2, 0.3), Interval(10,11), Interval(2,3), Interval(9,10)];


julia> @btime hullify(X)
  1.610 μs (45 allocations: 3.31 KiB)
Set{Interval{Float64}} with 3 elements:
  [0, 0.3]
  [1, 3]
  [9, 11]

julia> @btime hullify1(X)
  371.717 ns (6 allocations: 704 bytes)
3-element Vector{Interval{Float64}}:
   [0, 0.3]
  [1, 3]
 [9, 11]

In fact, the version that uses only one level of for loops is faster.
PS
Does anyone have any idea why the print on the REPL in the second case has those weird indentations?

1 Like