0

问我问题的最好方法是通过一个明确的例子。考虑 2 个时间线（例如，以秒为单位的时间）A 和 B，其中每个时间线的间隔为：

intervals_a = 
   0 1
   1 4
   4 7
   7 9

intervals_b = 
   0 2
   2 3
   3 5
   5 8

请注意，第一个 a 间隔与第一个 b 间隔重叠。第二个 a 间隔与第一个、第二个和第三个 b 间隔重叠，依此类推。

最终，我需要一个输出来显示与 b 间隔重叠的 a 间隔的索引，如下所示：

output = 
   1 1   \\ 1st a-interval overlaps 1st b-interval
   2 1   \\ 2nd a-interval overlaps 1st b-interval
   2 2   \\ 2nd a-interval overlaps 2nd b-interval
   2 3   \\ 2nd a-interval overlaps 3rd b-interval
   3 3   \\ etc...
   3 4
   4 4

最大的挑战是：解决方案不能包含 for/while 循环（“为什么”无关紧要）。这可以使用向量/矩阵/数组/排序或其他工具有效地完成吗？MATLAB 实现将是完美的，但任何其他语言都可以。提前致谢！

4

2 回答 2

1

要查找重叠区间，您需要检查一个区间的开始时间或结束时间是否在另一个区间的边界内。要一次对所有间隔执行此操作，您可以使用bsxfun：

ovlp = @(x, y)bsxfun(@ge, x(:, 1), y(:, 1)') & bsxfun(@le, x(:, 1), y(:, 2)');
idx = ovlp(intervals_a, intervals_b) | ovlp(intervals_b, intervals_a)';
[row, col] = ind2sub(size(idx), find(idx));
output = [row, col];

例子

让我们看看这对您的示例是如何工作的：

intervals_a = [0 1; 1 4; 4 7; 7 9]
intervals_b = [0 2; 2 3; 3 5; 5 8]

匿名函数ovlp检查x（即x(:, 1)）中的开始时间是否在 中给定的区间内y。因此，ovlp(intervals_a, intervals_b)产生：

ans =
     1     0     0     0
     1     0     0     0
     0     0     1     0
     0     0     0     1

“1”表示interval_a 的开始时间落在interval_b 内的位置。行号是区间的索引，intervals_a列号是区间的索引intervals_b。

我们需要对开始时间执行相同的过程intervals_b以找到所有重叠间隔，并且我们在两个结果之间进行逻辑或：

idx = ovlp(intervals_a, intervals_b) | ovlp(intervals_b, intervals_a)'

请注意，第二个结果被转置，以保持与intervals_a和 not对应的行intervals_b。得到的矩阵idx是：

idx =
     1     0     0     0
     1     1     1     0
     0     0     1     1
     0     0     0     1

最后一步是将矩阵转换为和中的idx索引，因此我们获得 '1' 的行号和列号并将它们连接起来：intervals_aintervals_b

[row, col] = ind2sub(size(idx), find(idx));
output = [row, col];

最终结果是：

output =
     1     1
     2     1
     2     2
     2     3
     3     3
     3     4
     4     4
于 2013-03-24T17:53:25.770 回答
0

您想要 int_A 和 int_B 的索引 (ii,jj) 使得 int_A(ii,1) > int_B(jj,1) 和 int_A(ii,2) 

NA = size(A_int,1);
NB = size(int_B,1);
ABlower= repmat(A_int(:,1),[1,NB]);
ABupper= repmat(A_int(:,2),[1,NB]);
BAlower= repmat(B_int(:,1),[1,NA])';
BAupper= repmat(B_int(:,2),[1,NA])';

inInt = find((ABlower>BAlower & ABlower < BAupper) | (ABupper>BAlower & ABupper<BAupper);
[ii,jj]=ind2sub([NA,NB], inInt);

我现在无法访问 Matlab，但我相信这非常接近......

于 2013-03-24T01:12:19.730 回答