# Faster alternative to polyxpoly

37 Ansichten (letzte 30 Tage)
MichailM am 16 Nov. 2022
Bearbeitet: Bruno Luong am 14 Jan. 2023
I have observed that polyxpoly is a little bit of slow function. Is there any faster alternative?
##### 1 Kommentar-1 ältere Kommentare anzeigen-1 ältere Kommentare ausblenden
Adam Handley am 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.

Melden Sie sich an, um zu kommentieren.

### Antworten (2)

John D'Errico am 14 Jan. 2023
Bearbeitet: John D'Errico am 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
##### 0 Kommentare-2 ältere Kommentare anzeigen-2 ältere Kommentare ausblenden

Melden Sie sich an, um zu kommentieren.

Bruno Luong am 14 Jan. 2023
Bearbeitet: Bruno Luong am 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
##### 0 Kommentare-2 ältere Kommentare anzeigen-2 ältere Kommentare ausblenden

Melden Sie sich an, um zu kommentieren.

### Kategorien

Mehr zu Logical finden Sie in Help Center und File Exchange

### Community Treasure Hunt

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

Start Hunting!

Translated by