Fast Line Segment Intersection

Finds the pairwise intersection points between line segments in 2D Cartesian space.

Description

OUT = LINESEGMENTINTERSECT(XY1,XY2) generates intersection analysis between the line segment sets given in XY1 and XY2. Code can handle coincident and parallel lines.

The main emphasis is on speed. The code is fully vectorized and it runs pretty fast (orders of magnitude) compared to some of the previous postings.

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Fast and Robust Curve Intersections
This submission has inspired the following:
Segments Intersection Test Functions

• MATLAB release: MATLAB 7.9 (2009b)

[Fabio Pinna]

It worked fine and fast for me! Good work!
Good vectorization.
The complex output prevent further vectorization but it is already fast enough

[Alex]

 

[Alex]

Quick and effective. However, I believe there is a typo in the documentation:

'intNormalizedDistance2To1' : N1xN2 matrix where the (i,j) entry is the normalized distance from the start point of line segment XY1(j,:) to the intersection point with XY2(i,:).

This description is the same as intNormalizedDistance1To2 except that i and j are swapped in the description, and that doesn't really make any sense. I believe XY1 and XY2 should also be swapped.

[Maher HAMDI]

 

[piet fue]

 

[Brandon]

 

[Francesco Montorsi]

I've found your function very useful, thanks! However I recently wanted to squeeze out some additional performance and ended up rewriting the thing in MEX C code, which can be compiled and run from MATLAB... I posted my code at http://www.mathworks.it/matlabcentral/fileexchange/35492-segments-intersection-test-functions .