File Exchange

## Curve intersections

version 1.5 (2.47 KB) by

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

4.74074
56 Ratings

Updated

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.

Example:
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]);
plot(x1,y1,x2,y2,P(1,:),P(2,:),'ro')

Nikolay

aj2016t

### aj2016t (view profile)

curious what is 'D' in the given function? keeps giving error for the undefined variable D

Pushkar Mahajan

### Pushkar Mahajan (view profile)

Great. Simple to use. Thank you very much!!!

Randika Vithanage

### Randika Vithanage (view profile)

Cannot handle if the lines interests beyond the given points

Troy

### Troy (view profile)

Works great, would however be nice to know who the intersection is with when input contains multiple cureves

Ryan Meekins

### Ryan Meekins (view profile)

This code works great, however, this code says that lines intersect even if they only overlap. For example:
xA = [0 0 1]; yA = [0 1 1]; LineA = [xA;yA];
xB = [0 0 .25 .25 0 0 .25 .25 .5 .5 1]; yB = [0 .5 .5 .75 .75 1 1 .75 .75 1 1]; LineB = [xB;yB];
plot(xA,yA, xB,yB);
P = InterX(LineA,LineB)

P =

0 0 0 0.2500 0.5000
0.5000 0.7500 1.0000 1.0000 1.0000

I'm looking for a code that would say the lines only intersect if they actually cross. Any ideas?

Michael Mann

Joshua Collins

Glenn Gomes

Alexander Herman

r p

David Onywoki

### David Onywoki (view profile)

@JonathanCamilleri what was the problem. I am getting the same error

Cheng Zeng

KSSV

Laura Berkowitz

Bing Sen Tay

Samuel Petitjean

Emrecan Yener

### Emrecan Yener (view profile)

Awesome function, thanks!

Yuanjun Zhao

### Yuanjun Zhao (view profile)

Great code, help me a lot! Thx!!!

Syed Hossain

Erik Manders

### Erik Manders (view profile)

Great piece of Code! Thanks a lot!

Abrar Habib

### Abrar Habib (view profile)

Jonathan Camilleri

### Jonathan Camilleri (view profile)

ignore my previous comment. realised what was wrong.

Jonathan Camilleri

### Jonathan Camilleri (view profile)

hi, I am trying to use this function but i keep getting the following error:

Error in InterX (line 60)
S1 = dx1.*y1(1:end-1) - dy1.*x1(1:end-1);

Error in data_vis (line 66)
inter = InterX(f1, f2);

however, my curves, f1 and f2 are both the same size, 25525 x 1 double.#

any suggestions?

cebum

PH

Heather

PENG

### PENG (view profile)

some problem in the Example:
t = 0:pi/200:2*pi;
r1 = 2; x1 = r1.*cos(t)+2; y1 = r1.*sin(1*t);
x2 = t; y2 = t-3;
P = InterX([x1;y1],[x2;y2]);
plot(x1,y1,x2,y2,P(1,:),P(2,:),'ro')
axis equal

Haidy Loh

Asif Arain

### Asif Arain (view profile)

Excellent!
Is it possible to obtain intersection points along with a logical vector that indicates corresponding curves/lines involved in the intersection points? Later, I want to assign weights to the intersection points based on the lines/curves.
Any help is much appreciated. Thanks!

Far Bod

Nick Savino

### Nick Savino (view profile)

More detailed comment to come.

Tamás Balogh

### Tamás Balogh (view profile)

Harish Babu Kankanala

Hojoon Choo

### Hojoon Choo (view profile)

This is exactly what I was looking for. Thanks!

E. Cheynet

Nitin

Brian Kim

### Brian Kim (view profile)

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

farnaz hajipour

Matthias

### Matthias (view profile)

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.

BboySlug

### BboySlug (view profile)

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. :)

Matthias

### Matthias (view profile)

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);
P=P';
i=i(ind)+1;
j=j(ind)+1;

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.

AS

### AS (view profile)

Pouriya Zarbafian

Tillmann Stübler

### Tillmann Stübler (view profile)

Vitor Ramalho de Brito

### Vitor Ramalho de Brito (view profile)

Thank you for this fantastic piece of code.

Ashish

Yongshou Liang

### Yongshou Liang (view profile)

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: Liangys363@gmail.com. Thanks a lot.

Yongshou Liang

Eric V

### Eric V (view profile)

Thanks. That's great. Works fine.

Abel Brown

JUN YON LER

### JUN YON LER (view profile)

It does not work.

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

Abdulrahman

### Abdulrahman (view profile)

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

Speechless

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.

Ilya

### Ilya (view profile)

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

Matthew Arthington

### Matthew Arthington (view profile)

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.

NS

### NS (view profile)

• 1 file
• 4.74074

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.

Emil Olsen

### Emil Olsen (view profile)

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?

Pie Mes

### Pie Mes (view profile)

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

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

Best regards.

Hi NS

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.

Best

NS

### NS (view profile)

• 1 file
• 4.74074

To Aviator: yes, it should handle these cases.

Aviator

### Aviator (view profile)

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

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

Jeroen van Nugteren

Valerian

ayesha sohail

Zhang Yanxiang

### Zhang Yanxiang (view profile)

Does exactly what it says. No problems.

Oguzcan

### Oguzcan (view profile)

useful, efficient, and fast