Algorithms for collision detection between concave polygons

Question

Is there any good algorithm for detection between concave polygons? I'd appreciate any help as so far I've only found algorithms for detection between convex polygons.

Answer 1

This paper from 2004 explores an efficient collision detection algorithm for 2D polygons, regardless of concave- or convex-ness.

In case the link ever goes dead, here's some authorship/citation information:

Juan José Jiménez, Rafael J. Segura, Francisco R. Feito
Departamento de Informática. E.P.S.J. Universidad de Jaén

Journal of WSCG, Vol.12, No.1-3, ISSN 1213-6972

Answer 2

This is old, but still relevant and there doesn't seem to be alot of answers for this question, so here goes:

For polygons whose overall shape does not change (may rotate and scale, but relationships between vertices may not change), there are ways to pre-process the vertex data to achieve an and/or series of tests for the lines in the polygon to test if the other polygon collides with it.

I'm in the process of writing this algorithm, so I will provide you with the theory behind it instead of a ready-made one:

---

Legend: && means AND, || means OR.

Step 1a:

Going through the lines of the polygon and testing each line against all other points of it, we separate the lines where all other points are on the line or on the 'inside' side of the line.

These collected lines form a new node in the collision checking formula and they are considered to be logical AND checks in relation to one another.

Step 1b:

Separate each islanded vertexgroup into their own collections and feed them to the next steps separately: These islands are considered logical AND in relation to one another.

Step 1c:

If any lines were collected during step 1a and we are collecting more than one line at a time due to getting to step 3a/3b, reset any variables set in steps 3a/3b and step right back into 1a.

Step 2a:

Going through the lines of the polygon and testing each line against all other points of it, we separate the lines where all other points are on the 'outside' side of the polygon (or to put it more specifically, all on the non-colliding side of the line).

These collected lines form a new node in the collision checking formula and they are considered to be logical OR checks in relation to one another.

Step 2b:

Separate each islanded vertexgroup into their own collections and feed them to the next steps separately. These islands are considered logical OR in relation to one another.

Step 2c:

If any lines were collected during step 2a, reset any variables set in steps 3a / 3b and step right back into 1a.

Step 3a:

Getting to this stage means there are no lines left for which all vertices fall on one side of, which means we need to collect the lines more aggressively:

Raise the number of consecutive lines to be collected in steps 1a and 2a. This means instead of all vertices falling one a side of one line, they must fall on one side of at least one of the collected lines (inside in 1a and outside in 2a). This gets reset back to 1 once any lines are collected.

Step 3b:

If number of consecutive lines to be collected exceeds the number of lines in the shape, reset the number to 2 and allow collection of non-consecutive lines (arriving here is also a good indication that your mesh is a bit complicated and you may want to think about cutting it down a bit, getting to 3a is no big deal though, as a simple star shape requires entering it to solve).

---

When using the resulting nodes for collision testing, simply feed the shapes (point / line / circle) of the object to test against the processed mesh into the nodes one by one.

For two polygons to be collision tested, only one of them must be processed like this.

---

Creating the formula for an example polygon:

1) Feed the example polygon to step 1a:

Example polygon after step 1a

The red lines in the picture are all lines of which all other vertices fall inside of, so a shape must be inside of all of them for the shape to be able to collide with the polygon.

The polygon will be islanded into two (A and B) after 1b.

2) Feed A and B to Step 2a:

Example polygon after step 2a

The green lines in the picture are all lines of which all other vertices fall outside of, so a collision will occur if the shape is inside one of them.

Both islanded polygons A and B will be further islanded into C, D, E and F after 2b.

3) Feed C, D, E and F to step 1a:

Example polygon after step 1a

The polygon C will lose one line (lets call the new shape G), D will be islanded into two (H and I) after step 1b and polygons E and F have no lines left to collect.

4) Feed G, H and I to step 2a:

Example polygon after step 2b

The polygon G will be islanded into two (J and K) after step 2c, H will lose 2 lines (call the new shape L) and I will have no lines left to collect.

5) Feed J, K and L to Step 1a:

Example polygon after step 1a

After this, all lines have been collected in just 3 repetitions of the steps.

The final formula for the original polygon then becomes: Final formula on one line and with phases marked down A bit more visual representation: Final formula with visual representation

Here's the original polygon with the lines marked: Polygon with lines marked

---

Using this method, concave polygons are the same speed or even faster to test collision against than if they were broken down into convex polygons (worst case scenario is the same time if both have same amount of vertices, best case scenario can cut tests down to all lines from step 1 and one line from step 2, cutting out testing for any of the more complex squiggles of the shape if collision happens elsewhere).

---

The limitations of this algorithm are at least the following:

1) If vertices of polygon are being animated, the above formula no longer applies and it has to be re-made. This is not a problem for a small amount of not-too-complicated polygons though, as the above steps are not very complicated (requires (n - 2)^2 of "which side of the line this point resides" -tests whose results can be cached and re-used throughout the steps).

2) Does not automatically handle holes in the polygon. Holes can be processed as above too though and just apply the following rule to it: a shape that collides with the original polygon must also either a) intersect with the lines of the hole or b) not collide with hole polygon for the collision to occurr.

3) The rules I presented for how to break the polygon down are not tested for arbitarily complex polygons and further rules may be needed to handle them.

4) You have to write the code for the algorithm yourself, as I have no intention of making a release until I have a working universal version, which may take a while.