# concave 2d polygon collision

This topic is 4858 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

sorry if this topic is a repeat. I am looking for a method to deal with the collision of two concave polygons. I am well aware of the point in polygon algorithms, however as my prgram is set up now, the toy is just moved backed to it's last position when a collision is detected. Clearly, this is not sufficient for my game. I've looked at several articles about collision however all of them describe ways of dealing with _convex_ polygons. Has anyone dealt with or know of a way of dealing with concave polygons?

##### Share on other sites
While it's conceivable that there might be an algorithm for intersecting concave polygons, I suggest that you simply tesselate them into convex polygons and check each pair. How concave are we talking about, anyway?

##### Share on other sites
I would like to tesselate, it seems like there would be a better solution when dealing with a complex polygon(like a spiral)

##### Share on other sites
Presumably there are two things you want to do - (1) see if the objects are intersecting and (2) if they are work out the minimum delta that's required to separate them (works as both a collision normal and a penetration depth/direction) .

Since it's 2D, you might be able to get away with a rather brute-force approach:

1. For intersection, just test all the edges of one polygon against the edges of the other (can speed this up using a tree-structure if your objects are moderately/very complicated), and vice-versa.

2. For the penetration bit:

2.1 Pre-process each object (before you start the simulation) to set up a grid of points that just covers it, in object space. At each point record (a) if it's inside or outside the polygon and (b) the direction and distance to the nearest edge. Then make a function that will take any position in world space and, using interpolation, indicate if that world position is inside/outside, and if the former, the direction/distance to the nearest edge.

2.2 During your collision detection, walk around the edge of the first polygon (let's say you start at a point that is outside the second polygon). When you reach an intersection point from step 1 above, start sampling the second polygon to find the maximum penetration depth/direction. When you leave the second polygon record the maximum depth that you found. At the end of this (and when you process the second polygon against the first) you'll have got a list of contact points/directions/depths.

So long as objects don't move too far compared to their "feature size", you should get sensible results from this. I did something similar in 3D and it worked OK, but it was a bit slow and used a lot of memory - in 2D these problems won't be so bad.

##### Share on other sites
Mr. Rowl, the brute force solution you describe seems rather limited and unflexible,(what if i want to rotate or move in object? i would have to rotate every precalculated point). Is the problem of concave collision so rare? I thought it would be relatively common, such as terrain for a 2d game like soldat. but perhaps tesselating is the best solution, thanks for your help.

##### Share on other sites
google search "Point-In-Polygon Algorithm — Determining Whether A Point Is Inside A Complex Polygon"

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5
JoeJ
18

• 13
• 10
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632998
• Total Posts
3009805
• ### Who's Online (See full list)

There are no registered users currently online

×