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

18 次查看（过去 30 天）
Joshua Soneson
Joshua Soneson 2021-3-31
编辑： Bruno Luong 2021-4-1
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?
  2 个评论
Matt J
Matt J 2021-4-1
编辑：Matt J 2021-4-1
Ran in:
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
Bruno Luong 2021-4-1
编辑：Bruno Luong 2021-4-1
"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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

darova
darova 2021-4-1
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
  1 个评论
Joshua Soneson
Joshua Soneson 2021-4-1
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.

请先登录，再进行评论。

Matt J
Matt J 2021-4-1
编辑：Matt J 2021-4-1
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)
  1 个评论
Joshua Soneson
Joshua Soneson 2021-4-1
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.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Interpolation 的更多信息

标签

产品


版本

R2020b

Community Treasure Hunt

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

Start Hunting!

Translated by