Intersecting polgons True/ False

Hello,

My game is struggling to effectively determine whether it has intercepted a polygon. Currently there are numerous ways I have considered engaging this issue, however the one I have a question about is using is 'inpolygon' or 'polybool' functions to determine of a point for the racer polygon (black triangle) is intersecting an object. The current attempt in the code below is to simply see if a fixed point will engage the function inpolygon as 'true'. It does not even though it appears to check itself against each polygon. Am I misunderstanding the function?

My Professor and I are scratching our heads, maybe someone here can be more helpful.

The function 'inpolygon' (line 156) is contained within the nested 'function checkWALL'. All obstacles are randomly created polygons using patch, the racer is a patch that can be moved by the arrow keys left to right.

I'd be happy to add any information that I have left out at your request. Thank you for your time and assistance.

Answer 1

[Sean de Wolski]

Use one of the intersecting functions in geom2d

old

inpolygon will tell you if a specific vertex is inside of the other polygon. This should be sufficient for identifying if one polygon is intersected with another.

Can you provide a minimal working example of where your function is failing?

[Chris Alkire]

I felt the same, but the return values keep showing false. I must be overlooking something. Attached is a simplified code (<200 lines) where the function 'inpolygon' is on (line 156)

I will update the question with this shorter version of the code.

[Roger Stafford]

To Sean: That is only true if the polygons are convex. For arbitrary polygons the problem is considerably more difficult. In that case you probably need to investigate every pair of line segments from the two respective polygons to see if they intersect each other. That is comparatively easy to do, but for polygons with many sides there will be a very large number of possible pairings.

[Sean de Wolski]

Roger, can you show an example? My understanding of inpolygon is that it works just fine with non-convex polygons (at least to a tolerance) and I can't think of an example where an edge of one polygon would intersect another without at least one vertex from one polygon being inside the other.

[Patrik Ek]

I agree with Roger Stafford that inpolygon is insufficient. Even convex polygons may fail here. Two polygons may still intersect even if all points are outside. However, there is a mex file in file exchange on this.

http://www.mathworks.com/matlabcentral/fileexchange/36241-polygon-clipping-and-offsetting

You can also check all intersecting line segments as Roger proposed. This is however quite time consuming, so identifying the cases that you do not need to test may speed the code up considerably.

[Sean de Wolski]

I don't know what kind of speeds you need, for a MATLAB game I would doubt the polygons will be all that complex and since you'd only be looking at their vertices I can't imagine more than a few thousand:

xy = (rand(10000,2)-0.5)*2; % 10000 points to sample
xx = linspace(0,2*pi,1000); % 1000 points in polygon
poly = [sin(xx);cos(xx)].';
plot(xy(:,1),xy(:,2),'b*',poly(:,1),poly(:,2),'r-')
timeit(@()inpolygon(xy(:,1),xy(:,2),poly(:,1),poly(:,2)))

About 0.68s on my relatively wimpy laptop.

[Patrik Ek]

Well, ok the polygon described above and which is now removed, does still fulfill your criterion, but there are cases where even convex polygons may fail. Try this,

x1 = [0,1,1,0,0]; y1 = [0,0,1,1,0]; x2 = [0.5,1,0,0.5]; y2 = [-0.5,1.5,1.5,-0.5];
plot(x1,y1,'r',x2,y2,'k'); xlim([-1,2]); ylim([-1,2]);

All polygons are convex, and there is no points inside any of the polygons, but they are still intersecting. So inpolygon for every vertex will not do. And this is only the 2D case, which is quite easy to discover. If this is the 2D projection of the 3D case, this may occur frequently and finding out if this is a permitted structure would be much worse.

[Sean de Wolski]

Nice example Patrik!

In that case, use one of the intersecting functions in geom2d