[R] Union/Intersect two continuous sets

[William Dunlap]

Late last month Hans Borchers suggested the following
solution (which I trivially converted to a function):

u0 <- function(M)
{
    # Mnew the union of intervals in M, an (nx2)-matrix with n > 1:
    o <- order(M[, 1], M[, 2])
    L <- M[o, 1]; R <- M[o, 2]
    k <- 1
    Mnew <- matrix(c(L[k], R[k]), 1, 2)
    for (i in 2:nrow(M)) {
        if (L[i] <= Mnew[k, 2]) {
            Mnew[k, 2] <- max(R[i], Mnew[k, 2])
        } else {
            k <- k+1
            Mnew <- rbind(Mnew, c(L[i], R[i]))
        }
    }
    Mnew
}

I believe the following does the same thing.  It
is quicker.  It may easily be changed to give you
the intervals where p or more of the input intervals
overlap instead of the current 1 or more.

u1 <- function(M)
{
    o <- order(c(M[, 1], M[, 2]))
    n <- cumsum( rep(c(1, -1), each=nrow(M))[o])
    startPos <- c(TRUE, n[-1]==1 & n[-length(n)]==0)
    endPos <- c(FALSE, n[-1]==0 & n[-length(n)]==1)
    M <- M[o]
    cbind(M[startPos], M[endPos])
}

Bill Dunlap
Spotfire, TIBCO Software
wdunlap tibco.com 

> -----Original Message-----
> From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org] On Behalf Of Hans W Borchers
> Sent: Thursday, December 22, 2011 7:50 AM
> To: r-help at stat.math.ethz.ch
> Subject: Re: [R] Union/Intersect two continuous sets
> 
> 谢一鸣 <cutexym <at> gmail.com> writes:
> 
> > Dear All,
> >
> > It is my first time using this mail list to post a question. And I
> > sincerely hope that this will not bother any subscribers.
> > So far as I know, there are functions like union( ), which can help to
> > combine two sets of discrete data. But what if the data sets are with
> > continuous data. For instance, I got three sets like [2, 4], [5, 6], [3.4,
> > 5.5]. I wonder if there is a quick solution to recognize their union is [2,
> > 6], and return the size of this union 6-2=4 to me. The similar demand is
> > for the intersection operation.
> > If you get any idea, please inform me. Thanks in advance!
> >
> > Xie
> 
> I got interested in your request as I could use it myself (not for intervals,
> but a similar kind of problem).
> I assume, you represent your set of intervals as a matrix M with two columns,
> first column the left endpoints, second the right ones.
> 
> Intersection is easy, as it is the interval from the maximum of left end
> points to the minimum of the right end points (or NULL if the maximum is
> greater than the minimum).
> 
> For the union I didn't see a simple, i.e. one or two lines, solution ahead,
> so here is my dumb, looped version. Surely there are more elegant solutions
> coming.
> 
>     # Mnew the union of intervals in M, an (nx2)-matrix with n > 1:
>     o <- order(M[, 1], M[, 2])
>     L <- M[o, 1]; R <- M[o, 2]
>     k <- 1
>     Mnew <- matrix(c(L[k], R[k]), 1, 2)
>     for (i in 2:nrow(M)) {
>         if (L[i] <= Mnew[k, 2]) {
>             Mnew[k, 2] <- max(R[i], Mnew[k, 2])
>         } else {
>             k <- k+1
>             Mnew <- rbind(Mnew, c(L[i], R[i]))
>         }
>     }
> 
>     # Inew the intersection of intervals in M, an (nx2)-matrix with n > 1:
>     L <- max(M[, 1]); R <- min(M[, 2])
>     Inew <- if (L <= R) c(L, R) else c()
> 
> ______________________________________________
> 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.