[R] Intersection of two sets of intervals

[William Dunlap]

The pmin/pmax approach fails if an open interval in
the first list intersects with more than one open
interval in the second.  You can deal with that by
a sorting trick that gives you the number of intervals
each time point is in and then selecting the time points
when the number of intervals covering it rises to 2 and
falls below 2.  This version ignores the possibility
that intervals in one list might overlap each other.

> f2 <-
function(list1, list2)
{
        n1 <- nrow(list1)
        n2 <- nrow(list2)
        times <- c(list1$open, list2$open, list1$close, list2$close)
        o <- order(times)
        times <- times[o]
        nOpen <- cumsum(rep(c(1, 1, -1, -1), c(n1, n2, n1, n2))[o])
        bothOpen <- nOpen == 2
        # ==1 for eitherOpen
        change <- diff(c(FALSE, bothOpen))
        data.frame(open = times[change == 1], close = times[change ==
-1])
}
> print(list3 <- data.frame(open = c(1, 5), close = c(4, 10)))
  open close
1    1     4
2    5    10
> list2
  open close
1  1.5   2.5
2  3.0  10.0
> f2(list2,list3)
  open close
1  1.5   2.5
2  3.0   4.0
3  5.0  10.0

Bill Dunlap
TIBCO Software Inc - Spotfire Division
wdunlap tibco.com 

-------------------------------------------------------------------
[R] Intersection of two sets of intervals

Thomas Meyer tm35 at cornell.edu 
Wed Apr 15 16:52:48 CEST 2009
Previous message: [R] Intersection of two sets of intervals
Next message: [R] Intersection of two sets of intervals
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
pmax/pmin did the trick nicely -- the right-size tool I was hoping for.

Thanks to all,

-tom

On 4/15/2009 9:14 AM, ONKELINX, Thierry 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
>