Need to optimize this matlab code..vectorization will help or not?

Question

Possible Duplicate:
Optimization a recurring matlab code

Is vectorization a good option in optimizing this piece of code? What criteria decides, whether we vectorize a code or not? What else can be done?

function [oddNodes] = pointInPolygon (point,thePolygon)
% determine if a point is in the polygon (faster than matlab "inpolygon"
% command

 polyPoints=size(thePolygon,1);     %number of polygon points
 oddNodes = false;

j=polyPoints;
x=point(1); y=point(2);

for i=1:polyPoints
if (thePolygon(i,2)<y && thePolygon(j,2)>=y ||  thePolygon(j,2)<y && thePolygon(i,2)>=y)
    if (thePolygon(i,1)+(y-thePolygon(i,2))/(thePolygon(j,2)-thePolygon(i,2))*(thePolygon(j,1)-thePolygon(i,1))<x)
        oddNodes=~oddNodes;
    end
end
j=i; 
end

Whether vectorizing is good or not depends on what you want to achieve. If it's speed you want, you should run the profiler on your code, and then start chipping away at the lines that take forever. — Jonas, Oct 18 '12 at 15:07

score 2 · Answer 1 · edited May 23 '17 at 12:27

Please, do some research, the amount of useful hits on google is literally overwhelming:

etc.

Having said that: your code suggests you only want to determine whether a single point lies inside the polygon. In that case, why bother, since inpolygon can determine that in under 5 seconds for a million-vertex polygon.

Now if you want to do it for a large number of points, but not-so-many vertices in the polygon (or the other way around), you're better off passing a points array into the function:

function in = pointInPolygon(points, poly)

    nn = size(poly,1);
    in = false(nn,1);

    for ii = 1:size(points,2)

        x = points(ii,1);
        y = points(ii,2);

        yn = false;
        for jj = 1:size(poly,1)

            if (poly(jj,2)<y && poly(nn,2)>=y || ...
                poly(nn,2)<y && poly(jj,2)>=y)

                if (poly(jj,1)+(y-poly(jj,2))/(poly(nn,2)-poly(jj,2))*...
                   (poly(nn,1)-poly(jj,1))<x)
                    yn = ~yn;
                end

            end
            nn = jj;
        end

        in(ii) = yn;

    end

end

since this enabled Matlab to use JIT to both loops. A simple test:

poly = rand(6e6,2);
poly = [poly ; poly(1,:)];

xy   = rand(1e3,2);

tic         
    in = pointInPolygon(xy, poly);
toc

Results:

Elapsed time is 0.324801 seconds.

Now, if you want to do the test for a large number of points, with a large number of vertices in the polygon, you're really better off translating all this to C and write a mex file. It is after all a fairly heavy algorithm, and when you're also placing heavy demands on it, you'll have to switch your tool set.

Need to optimize this matlab code..vectorization will help or not?

1 Answers1