Code covered by the BSD License  

Highlights from
Interval merging

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

Interval merging

by

Bruno Luong (view profile)

 

25 May 2009 (Updated )

Merging intervals in the bracket form

| Watch this File

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.
Please login to add a comment or rating.
Comments and Ratings (5)
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

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

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

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
22 Apr 2013

New feature, intersection of a set of interval-unions

23 Apr 2013

Simplified engine for RangeIntersection

Contact us