Faster alternative to polyxpoly

I have observed that polyxpoly is a little bit of slow function. Is there any faster alternative?

[Adam Handley]

Depends on the function you are expecting. You could generate a polypiecewise polynomial and use the coefficients to solve algebraically or compute some coefficients yourself to solve.

Just had to do this myself but my functions can be assumed to be nearly linear so I can easily compute an average gradients and calculate a axis intercepts of each line. Then a simple case of solving for an x and y intercept of the two lines.

Answer 1

[John D'Errico]

Nothing is ever as fast as we want it to be. polyxpoly (part of the mapping toolbox) does a lot of work. And it needs to check for intersections between all pairs of segments. Of course this will take time that should grow roughly quadratically with the number of segments in the given polylines.

You could try Doug Schwarz's intersections code, found on the file exchange.

N = [25 50 100 150 200 250 300]';
T = NaN(5,2);
for i = 1:numel(N)
  n = N(i);
  xy1 = rand(n,2);xy2 = rand(n,2);
  T(i,1) = timeit(@() polyxpoly(xy1(:,1),xy1(:,2),xy2(:,1),xy2(:,2)));
  T(i,2) = timeit(@() intersections(xy1(:,1),xy1(:,2),xy2(:,1),xy2(:,2)));
end
loglog(N,T,'-o')
legend('polyxpoly','intersections')
grid on

Intersections seems to have better behavior as the number of segments grows. The nearly linear slope in the loglog plot does have a slope of approximately 2, which reflects my claim of quadratic time algorithm. I don't think you can do much better than that.

And, as you can see, intersections was roughly 5 times as fast for curves with 300 segments. That disparity probably grows for larger problems. For smaller problems, polyxpoly seemed to have come out on top, at least in this test. But for smaller problems both tools were pretty fast.

polyfit(log(N),log(T(2,:)),1)
ans =
1.9177      -12.973

Find intersections on the FEX for download, here:

https://www.mathworks.com/matlabcentral/fileexchange/11837-fast-and-robust-curve-intersections?s_tid=ta_fx_results

Answer 2

[Bruno Luong]

I would add my own BLU_polyxpoly which derived from here https://fr.mathworks.com/matlabcentral/fileexchange/27673-2d-polygon-edges-intersection?s_tid=srchtitle

I should revisit my FEX that has not been maintained for such long time; but obviously still competitive in term of runtime.

N = [25 50 100 150 200 250 300]';
T = NaN(5,3);
for i = 1:numel(N)
    n = N(i);
    xy1 = rand(n,2);xy2 = rand(n,2);
    T(i,1) = timeit(@() polyxpoly(xy1(:,1),xy1(:,2),xy2(:,1),xy2(:,2)));
    T(i,2) = timeit(@() intersections(xy1(:,1),xy1(:,2),xy2(:,1),xy2(:,2)));
    T(i,3) = timeit(@() BLU_polyxpoly(xy1.',xy2.'));;
end
loglog(N,T,'-o')
legend('polyxpoly','intersections','BLU\_polyxpoly','Location','NorthWest')
grid on

This is the result on my laptop (I don't have mapping toolbox) for longer polygonal