Looking for faster inpolygon - testing whether points are inside a polygon

I downloaded and tried both insidepoly and inpoly and both give the same erroneous results on my test problem (a couple 7-gons spattered with random points, the actual application involves irregular polygons that are not simply connected), results that do not agree with matlab's inpolygon. In the attached image, dots are results from inpolygon and circles are from insidepoly. Red is outside, blue is inside, so dots in a different color circle represent errors. Is there a fix for this or an alternative package that gives the same results as inpolygon for less time?

[Matt J]

Exactly what are your needs in terms of speed? According to the test below, inpolygon crunches about 4 million points per second. On my laptop, I get about twice that. How much faster do you need to get?

P=1e6; %number of points
N=7; %number of polygon vertices

t=linspace(0,2*pi,N+1)'; t(end)=[]; 
xy=num2cell(4*rand(P,2)-2,1);  

xv=cos(t); yv=sin(t); %polygon vertices
[xq,yq]=deal(xy{:});%query points

pgon=polyshape([xv,yv]);

pq=[xq,yq];

tic;
  in=inpolygon(xq,yq,xv,yv);
points_per_sec=P/toc

points_per_sec = 4.1046e+06

%%Visualize

plot(pgon,'FaceColor','none');
hold on

scatter(xq(in),yq(in));
scatter(xq(~in),yq(~in));

hold off

[Bruno Luong]

"I downloaded and tried both insidepoly and inpoly and both give the same erroneous results on my test problem (a couple 7-gons spattered with random points, the actual application involves irregular polygons that are not simply connected)"

Normal, mathematicaly there is no such thing as non-simply-conected polygons by definition (all the edges mucst form a chain, and close).

insidepolygon() (I'm the author) won't work for such object.

Answer 1

[darova]

If your polygons are regular try to check points for inside radius first

• Calculate radius r and R of polygon
• Calculate distance of point to center of polygon
• Check if point is inbetween circles
• Use inpolygon if needed

[Joshua Soneson]

Thanks for responding. This was a test case, my application involves irregular polygons that are not simply connected. I probably should have stated that, will edit the original post.

Answer 2

[Matt J]

Because your polygons are convex, you can obtain the inequality representation A*x<=b of each polygon and then do

X=[x1,y1,z1;  x2,y2,z2;  ___; xn,yn,zn].';

isInside=all(A*X<b,1)

[Joshua Soneson]

My actual application involves polygons which are not convex in general. However, I tested using a nonconvex polygon and inpoly gives the same results as inpolygon. Interesting.