Minimum Common Region

2 次查看（过去 30 天）
Noushin Farnoud
Noushin Farnoud 2012-2-3
Hello Matlab Users I want to find the minimum region that is common between ranges of closed intervals; and also the associated frequency. For example: 100 200 120 300 140 220 250 350 should return: 140 200; freq. = 3 250 300; freq. = 2
Is there any solution for this problem that is not largely dependant on for-loops? I appreciate your help.
Regards, NF

请先登录，再回答此问题。

回答（3 个）

Image Analyst
Image Analyst 2012-2-3
What are your ranges? Is it 100-200, 120-300, 140-220, and 250-300? If so, there is no range that overlaps all those ranges. This is the code I used, which would work except that your 250-300 range doesn't overlap any of the prior 3 ranges:
ranges = [100 200 120 300 140 220 250 350];
% Reshape the array to put the low ends in column 1
% and the high ends in columns 2
ranges = [ranges(1:2:end); ranges(2:2:end)]'
% Get the low end of the overlapping region
lowEnd = max(ranges(:, 1))
% Get the high end of the overlapping region
highEnd = min(ranges(:, 2))
if highEnd < lowEnd
msgbox('There is no overlap range');
end
I also didn't understand what this means: "freq. = 3 250 300; freq. = 2" Makes no sense whatsoever to me. Please explain.
Noushin Farnoud
Noushin Farnoud 2012-2-3
Thanks for your reply. I apologize for the confusion as I did not use the 'code mode' when I wrote this. Here's what I meant:
A= [100 200;
120 300;
140 220;
250 350];
The minimum overlap is also all possible overlaps in this data set. In this example, the first 3 ranges overlap at 140-200 (with frequency = 3); and the 2nd and 4th ranges also overlap at 250-300 (frequency=2). Thanks
  1 个评论
Image Analyst
Image Analyst 2012-2-4
I don't know how to do it without for loops, but that should not be a problem unless your array is millions of rows long. You could just have three nested for loops. In the second loop (but outside the innermost third loop), have Walter's code. For every row in A, check how B (a different row in A) overlaps it. Then increment your histogram (what you call freq). The thing that will take long is that for any given A and B (say you compared row 3 with row 9) you have a possible overlap. Now you have to check ALL the other rows (1 through N EXCEPT for 3 and 9) to see if they contain the same range - that would be the innermost third loop. Be careful to avoid double counting (for example checking row 3 against row 9 and then later row 9 against row 3 otherwise you'll get double counting) - I assume you can figure out how to avoid that. What use is this strange procedure for anyway?

请先登录，再进行评论。

Walter Roberson
Walter Roberson 2012-2-3
If you have two closed intervals A and B, each a min/max pair, the region in common between them is
oint = [max(A(1),B(1)), min(A(2),B(2))];
if oint(2) < oint(1); oint = []; end
The operation is transitive: overlap(overlap(A,B),C) = overlap(A,overlap(B,C))
The operation is also commutative: overlap(A,B) = overlap(B,A)
  1 个评论
Walter Roberson
Walter Roberson 2012-2-4
Vectoring, taking advantage of the oddity that min(nan,Value) is Value and max(nan,Value) is Value:
oint = [max(A(:,1), B(:,1)), min(A(:,2), B(:,2))];
idx = oint(:,2) < oint(:,1);
oint(idx, :) = nan;

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Matrices and Arrays 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by