# Faster alternative to polyxpoly

24 views (last 30 days)
MichailM on 16 Nov 2022
Edited: Bruno Luong on 14 Jan 2023
I have observed that polyxpoly is a little bit of slow function. Is there any faster alternative?
Adam Handley on 16 Nov 2022
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.

John D'Errico on 14 Jan 2023
Edited: John D'Errico on 14 Jan 2023
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

Bruno Luong on 14 Jan 2023
Edited: Bruno Luong on 14 Jan 2023
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 ### Categories

Find more on Least Squares in Help Center and File Exchange

### Community Treasure Hunt

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

Start Hunting!