Intersection points of multiple straight line segments

4 次查看（过去 30 天）
Peter
Peter 2025-5-4
回答： Peter 2025-5-6
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
  3 个评论
显示 1更早的评论
Peter
Peter 2025-5-5
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
Peter 2025-5-6
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.

请先登录，再进行评论。

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

回答（2 个）

Image Analyst
Image Analyst 2025-5-5
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
  2 个评论
Peter
Peter 2025-5-6
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
Image Analyst 2025-5-6
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.

请先登录，再进行评论。

Peter
Peter 2025-5-6
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.

类别

在 Help Center 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息

标签

产品


版本

R2024a

Community Treasure Hunt

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

Start Hunting!

Translated by