Union and Interseciton of Intervals

Question

Joris Lambrecht il 9 Giu 2011

0
Link

Link diretto a questa domanda

https://it.mathworks.com/matlabcentral/answers/9141-union-and-interseciton-of-intervals

Commentato: Dan Bindman il 2 Ott 2020

I want to be able to quickly determine the interval resulting from unions and intersections of various intervals. The number of intervals may vary, so the method needs to be somewhat flexible.

In regular Matlab I have only found a way to intersect sets (e.g. {1,2,3} u {2,4}) not intervals (e.g. [0.1 3.3) n (1.1 2.9])

where 'u' indicates union and 'n' indicates intersection.

Example: ([1.1, 2.3] u [2.8 3.2]) n ([1.9, 3.1] u [4.2 4.3]) n [1.7, 3.2] = [1.9,2.3] u [2.8, 3.1]

In MuPad, you can do the following: (Dom::Interval([1.1, 2.3]) union Dom::Interval(2.8, 3.2)) intersect (Dom::Interval([1.9, 3.1]) union Dom::Interval(4.2, 4.3)) intersect (Dom::Interval([1.7, 3.2]))

Any ideas on how to do this without MuPad? I've seen the 'interval merging' file exchange entry but it only handles unions of intervals.

Thanks!

3 Commenti
Mostra 1 commento meno recenteNascondi 1 commento meno recente

Dan Bindman il 11 Apr 2020

Hi, I needed the union of intervals myself, so I wrote up a little code. It assumes that the intervals are closed to keep it simple.

function unionOfIntervalsMat = unionOfIntervals(intervalsMat)
%unionOfIntervalsMat = unionOfIntervals(intervalsMat) takes a set of
%(closed) intervals and returns the unions of those intervals.
%Each row of the input variable intervalsMat is an interval, with the first column 
%giving the lower bounds for the intervals and the second column giving the upper bounds.
%Each row of the output variable unionOfIntervalsMat is also an interval, defined similarly.
intervalsMat=sortrows(intervalsMat,1);
nIntervals=size(intervalsMat,1);
unionOfIntervalsMat=nan(size(intervalsMat));
unionOfIntervalsMat(1,:)=intervalsMat(1,:);
unionCount=1;
for i=2:nIntervals
    if intervalsMat(i,1) <= intervalsMat(i-1,2)
        unionOfIntervalsMat(unionCount,2)=max(intervalsMat([i-1 i],2));
    else
        unionCount=unionCount+1;
        unionOfIntervalsMat(unionCount,:)=intervalsMat(i,:);
    end
end
unionOfIntervalsMat(isnan(unionOfIntervalsMat(:,1)),:)=[];
end

Here is an example:

>> intervalsMat=[4 10; 28 31;11 12; 1 7; 13 17; 16 23; 8 11; 25 29]
intervalsMat =
     4    10
    28    31
    11    12
     1     7
    13    17
    16    23
     8    11
    25    29
>> 
>> unionOfIntervalsMat = unionOfIntervals(intervalsMat)
unionOfIntervalsMat =
     1    12
    13    23
    25    31

Alex Bream il 30 Lug 2020

Dan Bindman answer is wrong, e.g. unionOfIntervalsMat([1 10; 2 3; 5 6]) returns [1 10; 5 6] instead of [1 10]

Dan Bindman il 2 Ott 2020

Thanks Alex! Indeed I messed up a bit. In the for loop, I used i in some cases when I should have been using unionCount... anyhoo here is the new code:

function unionOfIntervalsMat = unionOfIntervals(intervalsMat)
%unionOfIntervalsMat = unionOfIntervals(intervalsMat) takes a set of
%(closed) intervals and returns the unions of those intervals.
%Each row of the input variable intervalsMat is an interval, with the first column 
%giving the lower bounds for the intervals and the second column giving the upper bounds.
%Each row of the output variable unionOfIntervalsMat is also an interval, defined similarly.
intervalsMat=sortrows(intervalsMat,1);
nIntervals=size(intervalsMat,1);
unionOfIntervalsMat=zeros(size(intervalsMat));
unionOfIntervalsMat(1,:)=intervalsMat(1,:);
unionCount=1;
for i=2:nIntervals
    if intervalsMat(i,1) <= unionOfIntervalsMat(unionCount,2)
        unionOfIntervalsMat(unionCount,2)=max([intervalsMat(i,2) unionOfIntervalsMat(unionCount,2)]);
    else
        unionCount=unionCount+1;
        unionOfIntervalsMat(unionCount,:)=intervalsMat(i,:);
    end
end
unionOfIntervalsMat=unionOfIntervalsMat(1:unionCount,:);
end

I *think* it should now work in all situations. Here it is for your example:

>> unionOfIntervalsMat = unionOfIntervals([1 10; 2 3; 5 6])
unionOfIntervalsMat =
     1    10

And here it is for the original example (still the same correct output):

intervalsMat =
  10
  31
  12
   7
  17
  23
  11
  29
>> unionOfIntervalsMat = unionOfIntervals(intervalsMat)
unionOfIntervalsMat =
  12
  23
  31

Accedi per commentare.

Accedi per rispondere a questa domanda.

Answer 1

Sean de Wolski il 9 Giu 2011

0
Link

Link diretto a questa risposta

https://it.mathworks.com/matlabcentral/answers/9141-union-and-interseciton-of-intervals#answer_12586

doc intersect
doc union

and friends. Beware of floating points, however.

fpno = @(x)uint32(x*1000); %get rid of floating points
fpyes = @(x)double(x)/1000;  %bring 'em back
fpyes(intersect(fpno([1.1 2.2]), fpno(1.2:.1:3.4)))

But I still don't understand how you're defining the interval as I can't get the same results as your example.

2 Commenti
Mostra NessunoNascondi Nessuno

Joris Lambrecht il 9 Giu 2011

intersect and union functions only operate on sets (not intervals). Like you say, beware floating points:

intersect([1.1 2.2], [1.2 3.4])

ans =

Empty matrix: 1-by-0

I want the result [1.2 2.2]

I can multiply my floating point numbers by a factor (determining precision, e.g. 1000 will result in 3 decimal place precsion), round them to make integers, construct sets from the integers, operate on these sets (using intersect and union), and then divide by my factor to get back to floating point. However this seems unnecessary and will generate large arrays to compare if I want high precision.

Sean de Wolski il 9 Giu 2011

So what increment are you using to define an "interval"?

Accedi per commentare.

Answer 2

Walter Roberson il 9 Giu 2011

0
Link

Link diretto a questa risposta

https://it.mathworks.com/matlabcentral/answers/9141-union-and-interseciton-of-intervals#answer_12618

Union and intersection of intervals can be done with min() and max() and appropriate logic; I remember implementing the logic about 6 years ago (probably in perl.) I did not, however, have to worry about open vs closed intervals: the representation and logic gets messier for those.