File Exchange Pick of the Week

Detect Curve Intersections, Quickly and Easily 3

Posted by Brett Shoelson,

Brett's Pick this week is "Fast and Robust Curve Intersections," by Douglas Schwarz.

If you've ever needed to find the intersections between (possibly complicated) curves, this file is for you. We've come to expect great things from Doug, and this file is no exception. I really like the interface to this function; it's very easy to use, and well written and documented. I also like Doug's responsiveness to his reviewers' comments; he modified the file to accommodate use cases suggested by a few different authors.

Suppose you had two sinusoids of different phase and amplitude, one of which is very noisy:

t= 0:pi/64:3*pi;
y = sin(t);
y2 = 0.6*sin(t-0.7)+0.1*randn(size(y));

      intersections makes finding the intersection points very easy.

      [xout,yout] = intersections(t,y,t,y2,1);
      plot(t,y,'linewidth',2)
      set(gca,'xlim',[min(t) max(t)],'ylim',[-1.1 1.1])
      hold on
      plot(t,y2,'g','linewidth',2)
      plot(xout,yout,'r.','markersize',18)

      I should note that there are other detectors of curve intersections on the File Exchange. I didn't have time to look at all of them, but you can browse them here. Also, Doug's submission inspired or was used by several other File Exchange submissions.

      Loren and Lucio recently provided a thoughtful discussion of methods used for the detection of line-segment intersections in Loren on the Art of MATLAB. You can find those posts here and here.

      Oh, and that cool on-figure magnifier? I used a previous Pick-of-the-Week submission for that!

      As always, comments to this blog post are welcome. Or leave a comment for Doug here.


      Get the MATLAB code

      Published with MATLAB® 7.12

3 CommentsOldest to Newest

If you test Doug’s algorithm against the “Curve intersections” algorithm by NS, you will find that it is much slower compared to NS’. For two ‘curves’ generated like

X1 = randn(1,1000);
X2 = randn(1,1000);
Y1 = randn(1,1000);
Y2 = randn(1,1000);

if I run

S = InterX([X1;Y1],[X2;Y2]);

takes 0.43 seconds on my machine to compute >200K intersections, whereas

[X0,Y0] = intersections(X1,Y1,X2,Y2);

takes about 16-17 seconds!! The norm of the difference in the returned results is about 1e-13, so both seem to be doing the same thing, but at a different…pace.

Even though I don’t really get how this code works, NS’ code is very short and doesn’t use any for loops. The only drawback of InterX is that it doesn’t return the indices of the intersection. But if you are after speed, the above submission is not the fastest one around!

These postings are the author's and don't necessarily represent the opinions of MathWorks.