Faster alternative to polyxpoly

조회 수: 58 (최근 30일)
MichailM
MichailM 2022년 11월 16일
편집: Bruno Luong 2023년 1월 14일
I have observed that polyxpoly is a little bit of slow function. Is there any faster alternative?
  댓글 수: 1
Adam Handley
Adam Handley 2022년 11월 16일
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.

댓글을 달려면 로그인하십시오.

답변 (2개)

John D'Errico
John D'Errico 2023년 1월 14일
편집: John D'Errico 2023년 1월 14일
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:

Bruno Luong
Bruno Luong 2023년 1월 14일
편집: Bruno Luong 2023년 1월 14일
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

카테고리

Help CenterFile Exchange에서 Logical에 대해 자세히 알아보기

태그

제품

Community Treasure Hunt

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

Start Hunting!

Translated by