如何根据区间的重叠程度对区间进行分类？

Question

我正在寻找一种算法，可以根据一组间隔的重叠（用字母）对它们进行分类。

• 输出应将每个重叠间隔与相同的字母相关联，从而构成一个唯一的组。

• 与多个组重叠的间隔将用与每个唯一组相对应的几个字母进行分类。

• 不重叠的区间也构成唯一的组。

问题如图所示：

我正在 R 中工作，我的时间间隔是这些：

structure(list(Interval = c(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), Start = c(5.3, 
6.5, 7.6, 7.8, 8, 8.3, 8.5, 8.7, 8.8, 9.9), End = c(7.5, 8.7, 
9.8, 10, 10.2, 10.5, 10.7, 10.9, 11, 12.1)), row.names = c(NA, 
-10L), spec = structure(list(cols = list(Interval = structure(list(), class = c("collector_double", 
"collector")), Start = structure(list(), class = c("collector_double", 
"collector")), End = structure(list(), class = c("collector_double", 
"collector"))), default = structure(list(), class = c("collector_guess", 
"collector")), delim = "\t"), class = "col_spec"), class = c("spec_tbl_df","tbl_df", "tbl", "data.frame"))

我认为

ivs

包可能有解决方案，但我不知道程序。

Answer 1

我认为这个功能可以满足您的需要。

label_overlaps <- function(data, Start = "Start", End = "End", 
                           label = "label", labs = letters) {
  data <- data[order(data[[Start]]), ]
  data[[label]] <- ""
  for(i in labs) {
    n <- which(data[[label]] == "")
    if(length(n) == 0) break
    n <- n[1]
    m <- which(data[[Start]] < data[[End]][n] & data[[End]] > data[[Start]][n])
    data[[label]][c(n, m)] <- paste0(data[[label]][c(n, m)], i)
  }
  if(any(!nzchar(data[[label]]))) warning("All labels exhausted")
  return(data)
}

使用非常简单：

label_overlaps(df)
#> # A tibble: 10 x 4
#>    Interval Start   End label
#>       <dbl> <dbl> <dbl> <chr>
#>  1        1   5.3   7.5 a    
#>  2        2   6.5   8.7 ab   
#>  3        3   7.6   9.8 b    
#>  4        4   7.8  10   bc   
#>  5        5   8    10.2 bc   
#>  6        6   8.3  10.5 bc   
#>  7        7   8.5  10.7 bc   
#>  8        8   8.7  10.9 bc   
#>  9        9   8.8  11   bc   
#> 10       10   9.9  12.1 c

我们可以这样绘制结果：

library(geomtextpath)

ggplot(label_overlaps(df), aes(Start, Interval)) +
  geom_textsegment(aes(label = label, xend = End, yend = Interval, 
                       color = label), textcolour = "black", gap = FALSE, 
                   vjust = -1, linewidth = 6, lineend = "round") +
  scale_color_manual(values = c("red", "orangered", "orange",
                                "green4", "dodgerblue"), guide = "none") +
  theme_minimal(base_size = 16)