[R] Intersection of two sets of intervals

[jim holtman]

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
>>>
>>> ______________________________________________
>>> R-help at r-project.org mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide
>>> http://www.R-project.org/posting-guide.html
>>> and provide commented, minimal, self-contained, reproducible code.
>>>
>>> Dit bericht en eventuele bijlagen geven enkel de visie van de schrijver
>>> weer
>>> en binden het INBO onder geen enkel beding, zolang dit bericht niet
>>> bevestigd is
>>> door een geldig ondertekend document. The views expressed in  this
>>> message
>>> and any annex are purely those of the writer and may not be regarded as
>>> stating
>>> an official position of INBO, as long as the message is not confirmed by
>>> a duly
>>> signed document.
>>>
>>> ______________________________________________
>>> R-help at r-project.org mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide
>>> http://www.R-project.org/posting-guide.html
>>> and provide commented, minimal, self-contained, reproducible code.
>>>
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>



-- 
Jim Holtman
Cincinnati, OH
+1 513 646 9390

What is the problem that you are trying to solve?