concave 2d polygon collision

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?

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

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.

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.