Finde paarweise Überlappungen von Intervallen (Segmenten)

Question

Wir haben zwei Sätze von Intervallen A und B. Mit einem Intervall meine ich ein geordnetes Paar von Ganzzahlen wie c(2,5). Ich möchte alle Paare von Intervallen finden - eine von A und eine von B - die sich überlappen.

Zum Beispiel, wenn A und B sind wie folgt:

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

dann eine Matrix zurück, wie unten FindOverlap(A, B) soll (das einzige Nullelement ist, weil das dritte Intervall von A mit dem ersten Intervall überlappt nicht von B):

1 1 
1 1 
0 1 

Haben Sie eine effiziente Idee?

Answer 1

Das Paket Intervall scheint hier eine Lösung zu schaffen:

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) 

für eine schöne Demonstration sehen: Demo

hth

Answer 2

Hier ist eine kleine Funktion, die ich die gleiche Sache zu tun geschrieben. Es könnte verbessert werden im Wesentlichen. Interessantes Problem.

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