Find pairwise overlaps of intervals (segments)

Question

We are given two sets of intervals A and B. By an interval, I mean an ordered pair of integers such as c(2,5). I want to find all pairs of intervals - one from A and one from B - that have overlap.

For instance if A and B are as follows:

A=c(c(1,7), c(2,5), c(4, 16))
B=c(c(2,3), c(2,20))

Then FindOverlap(A, B) should return a matrix like below (the only zero element is because the 3rd interval of A does not overlap with the first interval of B):

1 1
1 1
0 1

Do you have any efficient idea?

score 6 · Accepted Answer · edited Apr 17 '18 at 13:50

6

The intervals package seems to provide a solution here:

require("intervals")
A <- rbind(A1=c(1,7), A2=c(2,5), A3=c(4, 16))
B <- rbind(B1=c(2,3), B2=c(2,20))

# here you can also define if it is an closed or open interval
Aint <- Intervals(A)
Bint <- Intervals(B)

# that should be what you are looking for    
interval_overlap(Aint, Bint)

A nice demonstration

edited Apr 17 '18 at 13:50

Andrew Brēza

7,705
3
34
40

answered Aug 15 '13 at 08:16

holzben

1,459
16
24

score 1 · Answer 2 · answered Aug 15 '13 at 08:57

Here's a little function I wrote to do the same thing. It could be improved substantially. Interesting problem though.

f <- function(A,B){
  tmpA <-  lapply( A , function(x) min(x):max(x) )
  tmpB <-  lapply( B , function(x) min(x):max(x) )
  ids <- expand.grid( seq_along( tmpA ) , seq_along( tmpB ) )
  res <- mapply( function(i,j) any( tmpA[[i]] %in% tmpB[[j]] ) , i = ids[,1] , j = ids[ ,2] )
  out <- matrix( res , nrow = length( tmpA ) )
  return( out * 1 )
  }

 f(A,B)
     [,1] [,2]
[1,]    1    1
[2,]    1    1
[3,]    0    1

Thanks for your answer. It is an interesting idea using only basic R capabilities, although the time complexity is O(n * m * p) which n is the number of items in A, m is the number of items in B, and p is the maximum length of an interval. — Ali, Aug 15 '13 at 10:17

Find pairwise overlaps of intervals (segments)

2 Answers2