Can anyone help me improve this code?

I'm working on a function which takes an n-by-1 array (called "ts") as input and creates a n-by-n matrix (called "V"), where each element of V is either 0 or 1.

Now imagine "ts" as a plot: If one can connect an arbitrary point (e.g. ts(5)) with another arbitrary point (e.g. ts(47)) using a straight line without intersecting the time series, then the matrix elements V(5,47) and V(47,5) should be 1. If the two points can't be connected without intersecting the time series then the corresponding elements in the matrix should be 0. This is supposed to be done for all possible pairs of points in "ts".

Here's my code: It works, but it's very inefficient (especially because of the three nested loops). Any idea on how to improve the code would be much appreciated...

function V = someFunction(ts)

 len = length(ts);
 V = zeros(len, len);

 for a = 1:len,
    for b = 1:len,
        intersection = [];
        for c = min(a,b)+1 : max(a,b)-1,

            t_a = a;
            y_a = ts(a);
            t_b = b;
            y_b = ts(b);
            t_c = c;
            y_c = ts(c);

            if (y_c < y_b + (y_a - y_b) * ((t_b - t_c) / (t_b - t_a))),
                intersection = [intersection; 0];
            else
                intersection = [intersection; 1];
            end

        end

        if all(intersection==0),
            V(a,b) = 1;
        end

    end
end

%Set the diagonal to zero.
V(1:len+1:len*len) = 0;

end

EDIT: Small sample of "ts": 74.7900 75.1100 73.3100 72.0100 71.4700 70.8300 68.4800 69.5200 70.0700 68.9800 68.8300

[Matt Kindig]

Hmmm--your algorithm might be able to be vectorized, which might help with inefficiency. Can you provide some sample input (ts) and output (V) to illustrate your algorithm for us?

[Matt J]

So, "non-intersecting" means all y(c) for a<c<b lie below the line joining (a,y(a)) and (b,y(b))? What if they all lie above?

Also, give us the typical values for n.

[dave]

If y(c) is above the line connecting points a and b, then it's considered an intersection. The typical length of "ts" would be between 50 and several tousands.

@Matt Kindig: I'm not quite sure how to provide you with input and output samples on Matlab Answers..

[Matt Kindig]

Just edit your question to include them (for a small ts vector--maybe 10 samples or so).

Answer 1

[Iain]

A few things come to mind.

1. Only do half of the loops as you point out, V = V', so you only need to do one triangle of it.

2. You can use "break" to finish loops quickly - and you can do your check on each loop in c. - Or you could just do that comparison as a vector operation, eg:

 c = min(a,b)+1 : max(a,b)-1;
 yc = ts(c);
 intersection = (y_c < y_b + (y_a - y_b) .* ((t_b - c) / (t_b - t_a)));

3. I think your calc to see if there has been an intersection is wrong, but that could be that you meant something else.

[dave]

Thanks for the suggestions - I'll implement them. However, any ideas on how to completely vectorize the code would be great.