Intersection of two sets of intervals

l1 <- rbind(c(1,3), c(5,10), c(13,24))
l2 <- rbind(c(2,4), c(7,14), c(20,30))
l1

l2

# create matrix for overlaps
start <- cbind(c(l1[,1], l2[,1]), 1)
end <- cbind(c(l1[,2], l2[, 2]), -1)
over <- rbind(start, end)
# order
over <- over[order(over[,1]),]
# get overlap count
over <- cbind(over, overlap=cumsum(over[,2]))
# create the overlap matrix
inter <- cbind(start=over[(over[,2] == 1) & (over[,3] == 2), 1],

inter

Stavros, you are quite correct -- I discovered that the hard way a little
while ago when testing my two-line solution. Use of pmin/pmax don't handle,
for instance, cases where more than one interval in one set is wholly
contained by an interval in the other. (I have a mis-posted msg awaiting
moderator approval in R-help with a concrete example.)

Your tip to check out the intervals pkg looks promising. FYI, there the
general intersection is computed as the complement of the union of the
complements, i.e. A*B = (A'+B')' , aka DeMorgan.

Thanks for the help,

-tom

On 4/15/2009 11:27 AM, Stavros Macrakis wrote:

I can see how pmax/pmin would easily allow the intersection of
corresponding elements of two sequences of intervals, but I don't see
how they help in intersecting two *sets* of intervals, which was the
original problem statement.

? ? ? ? ? ?-s



On Wed, Apr 15, 2009 at 9:14 AM, ONKELINX, Thierry
<Thierry.ONKELINX at inbo.be> wrote:

Not of the self but still not complicated:

list1 <- data.frame(open=c(1,5), close=c(2,10))
list2 <- data.frame(open=c(1.5,3), close=c(2.5,10))

Intersec <- data.frame(Open = pmax(list1$open, list2$open), Close =
pmin(list1$close, list2$close))
Intersec[Intersec$Open > Intersec$Close, ] <- NA
Intersec

HTH,

Thierry

------------------------------------------------------------------------
----
ir. Thierry Onkelinx
Instituut voor natuur- en bosonderzoek / Research Institute for Nature
and Forest
Cel biometrie, methodologie en kwaliteitszorg / Section biometrics,
methodology and quality assurance
Gaverstraat 4
9500 Geraardsbergen
Belgium
tel. + 32 54/436 185
Thierry.Onkelinx at inbo.be
www.inbo.be

To call in the statistician after the experiment is done may be no more
than asking him to perform a post-mortem examination: he may be able to
say what the experiment died of.
~ Sir Ronald Aylmer Fisher

The plural of anecdote is not data.
~ Roger Brinner

The combination of some data and an aching desire for an answer does not
ensure that a reasonable answer can be extracted from a given body of
data.
~ John Tukey

-----Oorspronkelijk bericht-----
Van: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org]
Namens Thomas Meyer
Verzonden: woensdag 15 april 2009 14:59
Aan: r-help at r-project.org
Onderwerp: [R] Intersection of two sets of intervals

Hi,

Algorithm question: I have two sets of "intervals", where an interval is

an ordered pair [a,b] of two numbers. Is there an efficient way in R to
generate the intersection of two lists of same?

For concreteness: I'm representing a set of intervals with a data.frame:

?> list1 = as.data.frame(list(open=c(1,5), close=c(2,10)))
?> list1
?open close
1 ? ?1 ? ? 2
2 ? ?5 ? ?10

?> list2 = as.data.frame(list(open=c(1.5,3), close=c(2.5,10)))
?> list2
?open close
1 ?1.5 ? 2.5
2 ?3.0 ?10.0

How do I get the intersection which would be something like:
?open close
1 ?1.5 ? 2.0
2 ?5.0 ?10.0

I wonder if there's some ready-built functionality that might help me
out. I'm new to R and am still learning to vectorize my code and my
thinking. Or maybe there's a package for interval arithmetic that I can
just pull off the shelf.

Thanks,

-tom

--
Thomas Meyer

Here is one way to find the overlaps:

l1 <- rbind(c(1,3), c(5,10), c(13,24))
l2 <- rbind(c(2,4), c(7,14), c(20,30))
l1

     [,1] [,2]
[1,]    1    3
[2,]    5   10
[3,]   13   24

l2

     [,1] [,2]
[1,]    2    4
[2,]    7   14
[3,]   20   30

# create matrix for overlaps
start <- cbind(c(l1[,1], l2[,1]), 1)
end <- cbind(c(l1[,2], l2[, 2]), -1)
over <- rbind(start, end)
# order
over <- over[order(over[,1]),]
# get overlap count
over <- cbind(over, overlap=cumsum(over[,2]))
# create the overlap matrix
inter <- cbind(start=over[(over[,2] == 1) & (over[,3] == 2), 1],

+                end=over[(over[,2] == -1) & (over[, 3] == 1), 1])

inter

     start end
[1,]     2   3
[2,]     7  10
[3,]    13  14
[4,]    20  24


On Wed, Apr 15, 2009 at 12:06 PM, Thomas Meyer <tm35 at cornell.edu> wrote:

Stavros, you are quite correct -- I discovered that the hard way a little
while ago when testing my two-line solution. Use of pmin/pmax don't handle,
for instance, cases where more than one interval in one set is wholly
contained by an interval in the other. (I have a mis-posted msg awaiting
moderator approval in R-help with a concrete example.)

Your tip to check out the intervals pkg looks promising. FYI, there the
general intersection is computed as the complement of the union of the
complements, i.e. A*B = (A'+B')' , aka DeMorgan.

Thanks for the help,

-tom

On 4/15/2009 11:27 AM, Stavros Macrakis wrote:

I can see how pmax/pmin would easily allow the intersection of
corresponding elements of two sequences of intervals, but I don't see
how they help in intersecting two *sets* of intervals, which was the
original problem statement.

           -s



On Wed, Apr 15, 2009 at 9:14 AM, ONKELINX, Thierry
<Thierry.ONKELINX at inbo.be> wrote:

Not of the self but still not complicated:

list1 <- data.frame(open=c(1,5), close=c(2,10))
list2 <- data.frame(open=c(1.5,3), close=c(2.5,10))

Intersec <- data.frame(Open = pmax(list1$open, list2$open), Close =
pmin(list1$close, list2$close))
Intersec[Intersec$Open > Intersec$Close, ] <- NA
Intersec

HTH,

Thierry

------------------------------------------------------------------------
----
ir. Thierry Onkelinx
Instituut voor natuur- en bosonderzoek / Research Institute for Nature
and Forest
Cel biometrie, methodologie en kwaliteitszorg / Section biometrics,
methodology and quality assurance
Gaverstraat 4
9500 Geraardsbergen
Belgium
tel. + 32 54/436 185
Thierry.Onkelinx at inbo.be
www.inbo.be

To call in the statistician after the experiment is done may be no more
than asking him to perform a post-mortem examination: he may be able to
say what the experiment died of.
~ Sir Ronald Aylmer Fisher

The plural of anecdote is not data.
~ Roger Brinner

The combination of some data and an aching desire for an answer does not
ensure that a reasonable answer can be extracted from a given body of
data.
~ John Tukey

-----Oorspronkelijk bericht-----
Van: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org]
Namens Thomas Meyer
Verzonden: woensdag 15 april 2009 14:59
Aan: r-help at r-project.org
Onderwerp: [R] Intersection of two sets of intervals

Hi,

Algorithm question: I have two sets of "intervals", where an interval is

an ordered pair [a,b] of two numbers. Is there an efficient way in R to
generate the intersection of two lists of same?

For concreteness: I'm representing a set of intervals with a data.frame:

 > list1 = as.data.frame(list(open=c(1,5), close=c(2,10)))
 > list1

 open close
1    1     2
2    5    10

 > list2 = as.data.frame(list(open=c(1.5,3), close=c(2.5,10)))
 > list2

 open close
1  1.5   2.5
2  3.0  10.0

How do I get the intersection which would be something like:
 open close
1  1.5   2.0
2  5.0  10.0

I wonder if there's some ready-built functionality that might help me
out. I'm new to R and am still learning to vectorize my code and my
thinking. Or maybe there's a package for interval arithmetic that I can
just pull off the shelf.

Thanks,

-tom

--
Thomas Meyer