View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Curve intersections

Join the 15-year community celebration.

Play games and win prizes!

» Learn more

4.8 | 26 ratings Rate this file 284 Downloads (last 30 days) File Size: 2.47 KB File ID: #22441 Version: 1.5
image thumbnail

Curve intersections


NS (view profile)


14 Dec 2008 (Updated )

Fast computation of intersections and self-intersections of curves using vectorization.

| Watch this File

File Information

While a few other functions already exist in FEX that compute the intersection points of curves, this short piece of code was written with speed being the highest priority. No loops are used throughout, taking full advantage of MATLAB's vectorization capabilities

I welcome any comments, suggestions, bug reports etc.


INTERX Intersection of curves
    P = INTERX(L1,L2) returns the intersection points of two curves L1
    and L2. The curves L1,L2 can be either closed or open and are described
    by two-row-matrices, where each row contains its x- and y- coordinates.
    The intersection of groups of curves (e.g. contour lines, multiply
    connected regions etc) can also be computed by separating them with a
    column of NaNs as for example
          L = [x11 x12 x13 ... NaN x21 x22 x23 ...;
                y11 y12 y13 ... NaN y21 y22 y23 ...]
    P has the same structure as L1 and L2, and its rows correspond to the
    x- and y- coordinates of the intersection points of L1 and L2. If no
    intersections are found, the returned P is empty.
    P = INTERX(L1) returns the self-intersection points of L1. To keep
    the code simple, the points at which the curve is tangent to itself are
    not included. P = INTERX(L1,L1) returns all the points of the curve
    together with any self-intersection points.
        t = linspace(0,2*pi);
        r1 = sin(4*t)+2; x1 = r1.*cos(t); y1 = r1.*sin(t);
        r2 = sin(8*t)+2; x2 = r2.*cos(t); y2 = r2.*sin(t);
        P = InterX([x1;y1],[x2;y2]);


This file inspired Accurate Polygon Extension, Fast Parsing Of Line Segments In A Bw Mask, and Geom2d.

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (37)
16 Oct 2016 Hojoon Choo

This is exactly what I was looking for. Thanks!

Comment only
27 Jun 2016 E. Ch3yn3t  
13 Jun 2016 Nitin

Nitin (view profile)

21 Apr 2016 Kyungmin Kim

by the way, i wonder whether this code is adequated at the non-linear.

15 Apr 2016 farnaz hajipour

how i can download this file?

Comment only
11 Apr 2016 Matthias

Comment on my comment (see below): When you are interested not only in the points but also in the indices then I now think, that it's the best not to use 'unique' or 'uniquetol' at all. (This is especially important when you are investigating self-intersection. Then one intersection point causes multiple entries in P at different indices in i and j.)
Otherwise you might loose the correct assignment from points to indices i and j.

Comment only
06 Apr 2016 BboySlug

Works well given that both of your plotted data series matrices are the same size. I think this is the problem the "it does not work" guy ran into. For my task at hand, my two data series are not the same size and so it gives a horzcat error. That would be a nice way to update the code if it could also work with two matrices/data series that aren't the same size. :)

06 Apr 2016 Matthias

Very good and very fast.
I think I found a minor bug which is relevant only if you are interested in the indices i and j, where the intersection is expected.
I suggest to replace line 76 and 77 by:
[P,ind]=uniquetol([dx2(j).*S1(i) - dx1(i).*S2(j),dy2(j).*S1(i) - dy1(i).*S2(j)]./[L L],eps,'ByRows',true);

In this way the sorting (coming from unique or better uniquetol) is assigned also to the indices. Additionally I increased the indeces by 1, but this is more or less a matter of taste.

28 Mar 2016 AS

AS (view profile)

18 Mar 2016 Pouriya Zarbafian  
17 Mar 2016 Tillmann Stübler  
09 Mar 2016 Vitor Ramalho de Brito

Thank you for this fantastic piece of code.

Comment only
06 Jul 2015 Ashish

Ashish (view profile)

25 May 2015 Yongshou Liang

Hi, NS. Thanks for this excellent code. It runs really fast. However, I also have the problem as Emil's. When the input points are vectors more than 20000 columns, it's out of memory. The version of my matlab is 2014a (64 bits on windows). Could you send me that modified code or give me some suggestion? My Email is: Thanks a lot.

Comment only
25 May 2015 Yongshou Liang  
17 Nov 2014 Eric V

Eric V (view profile)

Thanks. That's great. Works fine.

20 Oct 2014 Abel Brown  
06 Oct 2014 JUN YON LER

It does not work.

Comment only
20 Aug 2014 Chad Greene

Chad Greene (view profile)

This function has proven very helpful for me. Thank you for sharing, and thank you for writing such a nice, neat code.

06 Mar 2014 Abdulrahman

THANK YOU SO MUCH. Great algorithm and works perfectly and super fast.


07 Jan 2014 Ilya

Ilya (view profile)

it would be helpful to show how to get the (all) values of "t", at which the intersections occur.

Namely, two values of the parameter "t" correspond to each self-intersection.

06 Jan 2014 Ilya

Ilya (view profile)

it would be helpful to show how to get the (all) values of "t", at which the intersections occur.

12 Dec 2013 Matthew Arthington

I've searched for a fast intersections function and I can't find one faster than this.

I'm a bit surprised that repeated subfunction calls are as fast as they are for large curves. Vectorising some of the operations speeds up the function, but only for smaller curves.

15 Dec 2012 NS

NS (view profile)

To Emil: Thank you for your comment. Unfortunately there is not much that can be done about that, unless one uses for-loops, which are likely to delay the execution time considerably.

To make the execution time as fast as possible, I need to create N x M matrices, where N and M are the number of segments in each curve.

Perhaps you can try some other contribution on File Exchange that does not utilize vectorization, but it is likely to be very slow (there should be about 4e10 tests for intersections for vectors of that size!)

Alternatively, contact me to send you a modification to my code to test with your data. However, I cannot guarantee accuracy of the results, as I did not do extensive tests to it, but it seems to work.

Comment only
14 Dec 2012 Emil Olsen

I frequently use this function to analyze threshold crossings in locomotion data and I love it! However since using it in 2012b on a 64bit windows machine I keep running out of memory even if just testing 20000 column vectors. Any ideas for a fix for this?

08 Mar 2012 Pie Mes

Really good, fast and versatile piece of code. BIG UPS.

04 Mar 2012 Muhammad

Please ignore the above comment. I have found a way and using your code.

Best regards.

Comment only
04 Mar 2012 Muhammad


Thanks for the share.
In my case, i have two lines in the point data form. For example, I have 3 columns of the data Y,X1 and X2. first line L1 is obtained by plotting and connecting (X1,Y) and the second line L2 is obtained by plotting and connecting (X2,Y).
Can you please explain me how can i convert this point data to "two-row-matrices" as described here.


Comment only
24 Feb 2012 NS

NS (view profile)

To Aviator: yes, it should handle these cases.

Comment only
23 Feb 2012 Aviator

Does this code accommodate intersection points if a segment of the graph is vertical?

Comment only
18 Jan 2012 Adam

Adam (view profile)

Thanks a lot for this function!!!Works correct where other intersection functions didn't!!

25 Jul 2011 Jeroen van Nugteren  
20 Apr 2011 Valerian  
30 Nov 2010 ayesha sohail

really very helpful..... many thanks

01 Dec 2009 Zhang Yanxiang  
27 Oct 2009 Adam

Adam (view profile)

Does exactly what it says. No problems.

15 May 2009 Oguzcan

useful, efficient, and fast

26 Nov 2009 1.3

Faster execution & better memory management

24 Sep 2010 1.5

Fixed a bug identified by Liu Minjie that would sometimes occur for two-point line segments.

Contact us