Faster alternative to polyxpoly
33 views (last 30 days)
Show older comments
I have observed that polyxpoly is a little bit of slow function. Is there any faster alternative?
1 Comment
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.
Answers (2)
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
Find intersections on the FEX for download, here:
0 Comments
Bruno Luong
on 14 Jan 2023
Edited: Bruno Luong
on 14 Jan 2023
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
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1263415/image.png)
0 Comments
See Also
Categories
Find more on Logical in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!