Finding the common segments of two noncontinuous vectors

Question

I'm looking for a quick and elegant manner to solve this problem: I have two noncontinuous line, like the black ones in this image:

For each, I have two vectors - one defining the starting points of each segment and the other defining the ending points.

I am looking for a MATLAB script that will give me the start and end points for the blue line, which is the intersection of the two lines.

I could, of course, create two vectors, each containing all the elements in the black lines, and then use "intersect". However, since the numbers here are in billions, the size of these vectors will be huge and the intersection will take long.

Any ideas?

Answer 1

Nice question!

This is a solution without loops for combining n discontinuous lines (n is 2 in the original post).

Consider n discontinuous lines, each defined by its start and stop points. Consider also an arbitrary test point P. Let S denote the solution, that is, a discontinuous line defined as the intersection of all the input lines. The key idea is: P is in S if and only if the number of start points to the left of P minus the number of stop points to the left of P equals n (considering all points from all lines).

This idea can be applied compactly with vectorized operations:

start = {[1 11 21], [2 10 15 24]}; %// start points
stop  = {[3 14 25], [3 12 18 27]}; %// stop points
  %// start and stop are cell arrays containing n vectors, with n arbitrary

n = numel(start);
start_cat = horzcat(start{:}); %// concat all start points
stop_cat = horzcat(stop{:}); %// concat all stop points
m = [ start_cat stop_cat; ones(1,numel(start_cat)) -ones(1,numel(stop_cat)) ].';
  %'// column 1 contains all start and stop points.
  %//  column 2 indicates if each point is a start or a stop point
m = sortrows(m,1); %// sort all start and stop points (column 1),
  %// keeping track of whether each point is a start or a stop point (column 2)
ind = find(cumsum(m(:,2))==n); %// test the indicated condition
result_start = m(ind,1).'; %'// start points of the solution
result_stop = m(ind+1,1).'; %'// stop points of the solution

With the above data, the result is

result_start =
     2    11    24

result_stop =
     3    12    25

Answer 2

Your idea of discretizising is fine, but instead of using fixed step sizes I reduced it to the relevant points. The start or endpoint of the union are start or end point from one of the inputs.

%first input
v{1}=[1,3,5,7;2,4,6,8];
%second input
v{2}=[2.5,6.5;4,8];
%solution can only contain these values:
relevantPoints=union(v{1}(:),v{2}(:));

%logical matrix: row i column j is true if input i contains segment j
%numel(relevantPoints) Points = numel(relevantPoints)-1 Segments
bn=false(size(v,2),numel(relevantPoints)-1);
for vector=1:numel(v)
    c=v{vector};
    for segment=1:size(c,2)
        thissegment=c(:,segment);
        %set all segments of bn to true, which are covered by the input segment
        bn(vector,find(relevantPoints==thissegment(1)):find(relevantPoints==thissegment(2))-1)=true;
    end
end
%finally the logic we want to apply
resultingSegments=and(bn(1,:),bn(2,:));
seg=[relevantPoints(find(resultingSegments))';relevantPoints(find(resultingSegments)+1)'];