version 1.5.0.0 (2.47 KB) by
NS

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

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')

NS (2021). Curve intersections (https://www.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections), MATLAB Central File Exchange. Retrieved .

Created with
R2008a

Compatible with any release

**Inspired:**
Thermodynamic models and tools for H2O, H2, CO2 and Air, Accurate polygon extension, Fast Parsing of Line Segments in a BW Mask, geom2d

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

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

Maria CostaDebarshee GhoshWorks really well. Saved me a lot of time !

mlauduEliasIn addition to the comment by Patrik Forssén:

Change line 68 to:

if isempty(i),P = zeros(2,0);i=[];j=[];return; end;

so the modified function still works, even when the two curves are not intersecting

Eliasnicole fevolanguyen nhan tinhthanks NS.

Could you help me to understand the C1 and C2 in detail or the logical theory.

Ali MoshrefzadehMoayed JumahWhy can't I use this function to find the intersection point of any two straight lines?

Patrik ForssénGreat submission! The one thing missing is the indices of the intersecting segments. However, this is easily fixed with some minor code modifications. Change the function header to,

[P, i, j] = InterXMod(L1, varargin)

and change row 76 to,

[P, ind] = unique([dx2(j).*S1(i) - dx1(i).*S2(j), ...

dy2(j).*S1(i) - dy1(i).*S2(j)]./[L L],'rows','stable');

P = P'; i = i(ind); j = j(ind);

Then you should have the intersecting segment indices for the first supplied polyline(s) in the output variable “i" and the ones for the second supplied polyline(s) in the output variable “j”.

Jesus PortillaMarcus BukerAdolfo VelizValeri DiskoSiddhanth ShettyGayan De SilvaWorks perfectly. Thank you very much.

Chuck HaydenGuanting SUYang LuHi NS,

I tried to translate it to fortran. Could you help me to understand the C1 and C2 in detail or the logical theory behind it?

Salman KhanGreat Function. I used it to automate reading of x-axis where my curves intersect a horizontal line. It worked flawlessly after following instructions for INTERX(L1,L2).

ChamanthHighly resourceful function.

LucasThanks for this very useful function!

I need to determine only the intersection points that are above a set of decreasing line functions (i.e., with negative slope). How can I change this code to reach these points?

Regards,

John Michael HickeyNed QiJoseph LilekSimon ChouMustapha El HamdaouiA very useful function. Thanks!

Tobias KistlerLeopoldo BrasilMaura E. MonvilleHi,

I tried your code on finding if a square intersects a closed curve (polygonal). I get the following error:

Error using bsxfun

Non-singleton dimensions of the two input arrays must match each other.

Error in InterX (line 63)

C1 = feval(hF,D(bsxfun(@times,dx1,y2)-bsxfun(@times,dy1,x2),S1),0);

Error in Pixelize_Collimator_Aperture_v2 (line 107)

P = InterX([X;Y],[sqx;sqy]);

The polygonal is a closed curve made up of 42 points.

The square is a closed square curve made up of 5 points

Must the two curves have the same number of points? That is not specified in your description.

I can send my curves and squares if you like.

Thank you

Maura

MindaugasInterX function returns empty list of poits, if self-intersection point is in input.

For example, InterX returns empty list, but self-intersection point is [1 1] in this code:

x=[0 1 2 1 1];

y=[1 1 1 2 0];

figure; hold('on');

for i=1:length(x)-1; plot(x([i i+1]),y([i i+1]),'LineWidth',i); end;

P=InterX([x;y])

William Reedno such command in R2019a

Jules RayIt work but is not that fast as promised. After a test comparing against the "intersections" function give quite similar results:

InterX = Elapsed time is 10.502146 seconds.

intersections = Elapsed time is 10.567976 seconds.

both compared using the same two curves formed each by 1200 points.

Dominik Mattiolisaleem khanHi, I am new to Matlab, I am getting this error while trying to run this code, someone please help me.

parse error near line 176 of file C:\Users\Omar-PC\Desktop\Algo Problem\data Set\octave\code_samp

les\octave.m

nested functions not implemented in this context

>>> function u = D(x,y)

any help will be Much appreciated, Thank you!

Kathryn FellerHi, i'm trying to calculate the intersection between a vertical line and a curve described by two vectors of data. This function seems to work, but its giving me two sets of coordinates, and there is only one possible intersection give the information I entered. Perhaps this is related to the fact that the curve is an array of data points and not a mathematical curve? Because the curve is from a list of entered datapoints, the x value I am trying to determine a y value for is between two points. Any help deciphering this output would be tremendous.

Amanda Bernardymy matlab tells me "InterX" is an undefined function

Pim van MilYang LuHi NS,

The code works very good. I find the value of the intersections but now I want to find the indexes. When I use the find function, it does not find the right indexes of the intersections point but the empty value. Could you help me to find the way to find the right indexes of the intersections point?

Thanks in advance!

Yang.

Aurea94Jorge CeledónHere is the matlab function https://es.mathworks.com/help/map/ref/polyxpoly.html

MANALI DODIYAhello, I keep getting error as below.

Error using symengine (line 59)

Array sizes must match.

Error in sym/privBinaryOp (line 903)

Csym = mupadmex(op,args{1}.s, args{2}.s,

varargin{:});

Error in .* (line 238)

X = privBinaryOp(A, B, 'symobj::zip', '_mult');

Error in InterX (line 60)

S1 = dx1.*y1(1:end-1) - dy1.*x1(1:end-1);

Error in solve_equation (line 28)

P = InterX(L1,L2) ;

Samuel KelseyDavid StolnisDoes not work. Have 2 lines that indeed cross but I get no Xing info.... empty array! Looks like others had luck though.

DominikBen MohankumarGreat script - works perfectly. I have a question - I have several intersections to compute and I was wondering how easy it would be to vectorise the calculation to improve code performance? Cheers, Ben

Michael RedlingEmna SGHAIERLeopoldo Brasilyenting chenTinashe Martin GoneseSyed Ammar AbbasIt is giving empty intersection point for these lines when they actually do interestect.

L1 = [1152.3 1069.6;

559.6 656.1]

L2 = [1570.3 1564.1;

884.1 937.2]

Ozan CelikHi, the code works very good. Thanks!

I have a question, is it possible to use this function to find the intersection of multiple curves in a vectorized fashion? Say we have a set of curves which are stored as the columns of matrix A and we have another set of curves which are stored as the columns of matrix B. Is it possible to find the intersection of A(:,i) with B(:,i) without using for loops?

sundarWorks perfect! Thanks so much for the code.

Mahta MazloumiIt worked very well! thank you

Nedim Gökhan AydinPretty fast, simple and useful.

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

Pushkar MahajanGreat. Simple to use. Thank you very much!!!

Randika VithanageCannot handle if the lines interests beyond the given points

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

Ali HassanzadehRyan MeekinsThis 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 MannJoshua CollinsGlenn GomesAlexander Hermanr pDavid Onywoki@JonathanCamilleri what was the problem. I am getting the same error

Cheng ZengKSSVLaura BerkowitzBing Sen TaySamuel PetitjeanEmrecan YenerAwesome function, thanks!

Yuanjun ZhaoGreat code, help me a lot! Thx!!!

Syed HossainErik MandersGreat piece of Code! Thanks a lot!

Abrar HabibJonathan Camilleriignore my previous comment. realised what was wrong.

Jonathan Camillerihi, 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?

cebumPHHeatherPENGsome 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 LohAsif ArainExcellent!

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 BodBluePoseidon1643More detailed comment to come.

Tamás BaloghHarish Babu KankanalaHojoon ChooThis is exactly what I was looking for. Thanks!

E. CheynetNitinBrian Kimby the way, i wonder whether this code is adequated at the non-linear.

farnaz hajipourhow i can download this file?

MatthiasComment 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.

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

MatthiasVery 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.

ASPouriya ZarbafianTillmann StüblerVitor Ramalho de BritoThank you for this fantastic piece of code.

AshishYongshou LiangYongshou LiangHi, 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.

Eric VThanks. That's great. Works fine.

Abel BrownJUN YON LERIt does not work.

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

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

Speechless

Ilyait 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.

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

Matthew ArthingtonI'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.

NSTo 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 OlsenI 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 MesReally good, fast and versatile piece of code. BIG UPS.

MuhammadHi NS

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

Best regards.

MuhammadHi 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

NSTo Aviator: yes, it should handle these cases.

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

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

Jeroen van NugterenValerianayesha sohailreally very helpful..... many thanks

Zhang YanxiangAdamDoes exactly what it says. No problems.

Oguzcanuseful, efficient, and fast