File Exchange

image thumbnail

Interval merging

version 1.2 (3.48 KB) by

Merging intervals in the bracket form

6 Downloads

Updated

View License

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.

Comments and Ratings (6)

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);

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

Xavier Xavier

Xavier Xavier (view profile)

Thank you very much, this is working perfectly!

Regards
Xavier

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

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

Updates

1.2

Simplified engine for RangeIntersection

1.1

New feature, intersection of a set of interval-unions

MATLAB Release
MATLAB 7.8 (R2009a)
Acknowledgements

Inspired: Range intersection

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video