Code covered by the BSD License

### Highlights from Interval merging

4.0
4.0 | 2 ratings Rate this file 12 Downloads (last 30 days) File Size: 3.48 KB File ID: #24254 Version: 1.2

# Interval merging

### Bruno Luong (view profile)

25 May 2009 (Updated )

Merging intervals in the bracket form

File Information
Description

A handily simple function for a merging task:

Given N input closed intervals in bracket form:
Ii := [left(i),right(i)], i = 1,2...,N (mathematical notation).

The set union{Ii) can be written as a canonical partition by intervals Jk; i.e., union{Ii) = union(Jk), where Jk are M intervals (with M<=N, so the partition is minimum cardinal), and {Jk} are disjoint to each other (their intersections are empty).

This function returns Jk = [lower(k),upper(k)], k=1,2,...M, in the ascending sorted order.

Acknowledgements

This file inspired Range Intersection.

MATLAB release MATLAB 7.8 (R2009a)
Tags for This File   Please login to tag files.
Comments and Ratings (6)
15 Jun 2015 Arbi

### Arbi (view profile)

you should see this

Comment only
31 Jan 2015 Ulrik

### Ulrik (view profile)

Thanks...
Your code can be optimized a bit to run even faster. (tested with the profiler)

function [lower,upper] = MergeBrackets(Left, Right)

% Detect when right < left (empty Ii), and later remove it (line #29, 30)
Right = Right(:);
Left = Left(:);

IdxKeep = Right>=Left;
Right = Right(IdxKeep);
Left = Left(IdxKeep);
% sort the rest by left bound
[Left,iorder] = sort(Left);
Right = Right(iorder);

% Allocate, as we don't know yet the size, we assume the largest case
lower = zeros(size(Left));
upper = zeros(size(Right));

% Nothing to do
if isempty(lower)
return
end

% Initialize
l = Left(1);
u = Right(1);
k = 0;
% Loop on brakets
for i=1:length(Left)
if Left(i) > u % new Jk detected
% Stack the old one
k = k+1;
lower(k) = l;
upper(k) = u;
% Reset l and u
l = Left(i);
u = Right(i);
else
u = max(u, Right(i));
end
end
% Stack the last one
k = k+1;
lower(k) = l;
upper(k) = u;
IdxKeep = true(k,1);
% Remove the tails
lower = lower(IdxKeep);
upper = upper(IdxKeep);

10 Jun 2011 Xavier Xavier

### Xavier Xavier (view profile)

The method describe above is working really well but is time consuming.

I submitted a faster method here
http://www.mathworks.com/matlabcentral/fileexchange/31753

Comment only
03 Jul 2010 Xavier Xavier

### Xavier Xavier (view profile)

Thank you very much, this is working perfectly!

Regards
Xavier

Comment only
01 Jul 2010 Bruno Luong

### Bruno Luong (view profile)

Hi Xavier,

You could do this ([lower(i), upper(i)] will compose C):

Aleft=[0 6];
Aright=[2 9];
Bleft=[1 8];
Bright=[7 12];

iitersect = @(i,j) deal(max([Aleft(i) Bleft(j)]),min([Aright(i) Bright(j)]));
[I J]=ndgrid(1:numel(Aleft),1:numel(Bleft));
[left right]=arrayfun(iitersect, I, J);
[lower upper] = MergeBrackets(left, right);

Bruno

Comment only
30 Jun 2010 Xavier Xavier

### Xavier Xavier (view profile)

Hello Bruno!

Thanks for this function, it's really usefull.
But now i have to do the intersection of intervals.
For example:
u stands for union, n stands for intersection
A=[0 2] u [6 9]
B=[1 7] u [8 12]
C=A n B = [1 2] u [6 7] u [8 9]

Do you have a function which is able to do that?
My problem is that A and B can be the union of N intervals so the shape of C is variable.
Cheers
Xavier