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
Hi,
I wonder where we can find or how can we get the intersection function?
best regards
Ricardo
You have the link right under the title…
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
if I run
takes 0.43 seconds on my machine to compute >200K intersections, whereas
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!