Intersection points of multiple straight line segments

This feels as though it should be easy, but other than creating loops which for large data sets run for ever I can't see how to do this

I have mulitple line segments with end points in the form [x11 y11 x12 y12; x21 y21 x22 y22;...] [x13 y13 x14 y14; x23 y23 x24 y24;...]

I am trying to find intersection points between any pair of line segments in the two lists

I know how to find where any specific two intersect, using xy = [x1*y2-x2*y1,x3*y4-x4*y3]/[y2-y1,y4-y3;-(x2-x1),-(x4-x3)]; and looping through each list in turn

but can't see an efficient way of testing all possible pairs

Any help gratefully received

[Torsten]

Maybe

https://uk.mathworks.com/matlabcentral/fileexchange/27205-fast-line-segment-intersection

or

https://uk.mathworks.com/matlabcentral/fileexchange/106385-fast-line-2-line-intersection-point-two-line-segments?s_tid=prof_contriblnk

? I didn't test them yet.

[Peter]

Thanks Torsten...The first one looks like it should work, although it misses a small number of intersections in my test data. Will try the other one too

[Peter]

And after rechecking my data I can confirm the code for the first link works properly, and is much faster than the original looping...Many thanks for pointing me to this one.

Answer 1

[Image Analyst]

How about just do a brute force loop

numSegments = size(lineSegments, 1); % Num rows in the matrix.
numIntersections = numSegments * (numSegments - 1);
xyIntersections = nan(numIntersections, 2); % x,y of all intersections.
row = 1;
for k1 = 1 : numIntersections
    line1 = lineSegments(k1, :); % [x1, y1, x2, y2]
    for k2 = 1 : numIntersections
        if k1 == k2
            % Same line compared with itself so skip it.
            continue;
        end
        line2 = lineSegments(k2, :);
        
        % Get x1, x2, etc.
        x1 = line1(1);
        x2 = line1(3);
        x3 = line2(1);
        x4 = line2(3);
        % Get y1, y2, etc.
        y1 = line1(2);
        y2 = line1(4);
        y3 = line2(2);
        y4 = line2(4);
        
        % Compute this intersection using your formula.
        % Haven't checked your formula but I assume it produces 
        % a 1x2 row vector containing the (x,y) intersection coordinates.
        xyIntersections(row) = [x1*y2-x2*y1,x3*y4-x4*y3] / [y2-y1,y4-y3;-(x2-x1),-(x4-x3)];
        row = row + 1;
    end
end

[Peter]

Thanks. This is pretty much my original approach, but I have many line segments, and the loop was taking forever. Hence trying to find a loop free way of doing this

[Image Analyst]

I don't know how much a loop would speed it up. I doubt it's the looping itself that's using up the time. It's the computations inside and that same computation would need to be done with a vectorized method.

How many line segments do you have? A hundred thousand? I did a double nested for loop with each one iterating a hundred thousand times, so that's 10 billion loop iterations. That double for loop took only 3.4 seconds on my laptop. That's really fast for 10 billion iterations, I think.

Answer 2

[Peter]

Interesting.... and I guess it's a combination of the two. Certainly on my data set I have seen something that ran for several hours reduce significantly since I used the vectorised approach. But still slower than I need. Eventually the data I will be using will be upwards of 100k segments. My immediate focus is to find ways of restricting the tests since there are combinations that can't occur. Once I have done that, then will look at both methods again. Really appreciate your input.