Those of you who write video games for computers or mobile device probably know that simplifying is the rule most of the times. To avoid embarrassing conditions where object go right through each other, we need some kind of collision checking algorithm. This is very easy when the colliding objects are all rectangular and their edges are parallel to the edges of the screen, but in real life objects are often concave and have not-so-regular shapes. One solution to check collisions in video games is checking whether one object collides into a point of the other object where the image is transparent, but that gets very CPU expensive and the framerate would drop drastically. The other option, which I’m going to explain, is to draw a simplified polygon around the edges of the *thing *we want to check for collisions and use it in place of the *thing* itself, as computers are better with maths than anything else.

## Getting the points of the polygon

This is the part I hate the most. You need to write down **all** the coördinates of the vertices of our polygon and put them into a list of tuples. I use GIMP for that, as it shows the coördinates of the point hovered by the mouse pointer.

**Important!** If you’re using Kivy you need to flip the image upside down, or the coördinates will be wrong! Kivy starts counting Xs and Ys from the bottom left corner, as opposed to GIMP (and GTK in general) which starts counting from the top left corner. Select the *flip* tool in GIMP, select *Vertical* in the tool options at the bottom and start writing down the coördinates.

This is what I’ve got for that image:

[(0, 85), (70, 170), (118, 172), (160, 135), (204, 204), (255, 204), (296, 135), (306, 153), (340, 153), (391, 82), (391, 50), (306, 0), (272, 0), (252, 33), (220, 33), (200, 0), (170, 0), (125, 50), (66, 15), (0, 50)]

Make sure all the points are in order. It doesn’t matter where you start. The first and the last are also counted as a segment like every other two points.

## The algorithm

The algorithm is explained very well in this site (currently not accessible, using the WayBack Machine).

This method relies on the fact that if you draw a line starting from the point and going to the right, it’s always going to intersect an even number of times (0 is considered even) if it lies outside of it, and an odd number if it’s inside.

Looking at this picture will make it easier to understand.

So what we’re going to do is checking whether the point lies between the highest and the lowest vertex of the polygon, then iterate over the edges to count the number of intersections. However, we’re trying to check whether two polygons collide, not a point and a polygon. So we need to iterate over every vertex of the first polygon and see if it lies and the second one, and vice versa.

## Writing the Python code

I’ll paste the code first, and then explain it:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
def point_in_polygon(p, vertices): # If the point is a vertex, it's in the polygon if tuple(p) in (tuple(i) for i in vertices): return True xs = [i[0] for i in vertices] ys = [i[1] for i in vertices] # if the point is outside of the polygon's bounding # box, it's not in the polygon if (p[0] > max(*xs) or p[0] < min(*xs)) or \ (p[1] > max(*ys) or p[1] < min(*ys)) return False p1 = vertices[-1] # Start with first and last vertices count = 0 for p2 in vertices: # Check if point is between lines y=p1[1] and y=p2[1] if p[1] <= max(p1[1], p2[1]) and p[1] >= min(p1[1], p2[1]): # Get the intersection with the line that passes # through p1 and p2 x_inters = float(p2[0]-p1[0])*float(p[1]-p1[1])/float(p2[1]-p1[1])+p1[0] # If p[0] is less than or equal to x_inters, # we have an intersection if p[0] <= x_inters: count += 1 print p1, p2, x_inters p1 = p2 # If the intersections are even, the point is outside of # the polygon. return count % 2 != 0 |

First, we check whether the point is one of the vertices. Then, to avoid useless iterations that might slow down the game, we also check if the point lies inside or outside of the polygon’s bounding box. If it’s inside, we go on.

Now that we have a high chance of collision we go on and iterate over all the edges and start counting the intersections. We check whether the point lies between the two points’ Ys, and if it does, we intersect with the line that passes through the edge of the polygon we’re considering. To do that, you start with the basic equation of a line through two points, then you move to the first member and everything else to the second.

If the value you get from this is less than or equal to the X of our point, we have an intersection, because it means the point is *on the left* of the segment.

The last line just checks if the number of collision is even or odd, and returns a bool accordingly.

### Colliding two polygons

If we want to collide a polygon, we can use the previous function together with this one:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
def polygon_in_polygon(polygon1, polygon2): # The polygons are the same if tuple(polygon1) == tuple(polygon2): return True # Sort by vertex number to reduce the number of iterations polys = sorted([polygon1, polygon2], key=lambda x: len(x)) rpolys = tuple(reversed(polys)) # Check for common vertices vs = (tuple(i) for i in polys[1]) for x, y in polys[0]: if (x, y) in vs: return True # Collide each point with the other polygon for p in rpolys: for point in p: if point_in_polygon(point, polys[rpolys.index(p)]): return True return False |

Even if it seems a little weird because of all the list sorting and reversing, what it does is actually very simple: first it checks if the two polygons are the same, then it checks whether the two polygons have common vertices, and if they don’t, it iterates over the vertices of each polygon and collides it with the other polygon.

# Using it with Kivy

I’ve made some simple classes to use this collision system with Kivy. The code was a little longer, so I posted it into a gist: https://gist.github.com/Davideddu/920183c34f8914e88faf

To use it, make your widget inherit from both *Polygon* or *MultiShapePolygon *and your widget class. If you’re using Polygon, make sure you override *abs_vertices* with the list of vertices you got earlier. If your widget can have different shapes (e.g. different positions of the character), make sure you override *_shapes* with **a list of dicts**. Each dict must have a “vertices” key with the list of tuples you got earlier. You can set any other key if you want (e.g. you may want to add an “image” key pointing to the image file corresponding to that shape), but the “vertices” key needs to be there. When you set the *shape* property, the vertices will be updated according to the index of the shape you set. You can use *random_shape* to let the app pick a random shape for you.

Another thing you will probably want to set is the *scale* property, which is needed if you’re scaling the widget associated to the polygon. For example, if you’re scaling the image to half of the original size, this property should be set to 1/2. If you’re not using the polygon as a widget you will also need to set *x *and *y*. Usually these properties are set by Kivy, but if your class does not inherit from both a widget and Polygon you’ll need to update these manually.

Example:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Cloud(MultiShapePolygon, Image): _shapes = [{"image": "atlas://data/clouds/cloud0", "vertices": [(0, 67), (33, 119), (67, 119), (136, 84), (136, 50), (60, 0), (0, 35)]}, {"image": "atlas://data/clouds/cloud1", "vertices": [(0, 87), (51, 153), (87, 153), (168, 134), (221, 85), (221, 50), (135, 0), (67, 0), (35, 0)]}, {"image": "atlas://data/clouds/cloud2", "vertices": [(0, 104), (80, 208), (218, 208), (218, 223), (360, 223), (360, 208), (553, 208), (637, 118), (637, 37), (581, 0), (525, 0), (485, 30), (416, 0), (304, 0), (180, 30), (137, 0), (82, 0), (0, 38)]}] def __init__(self, **kwargs): super(Cloud, self).__init__(**kwargs) self.bind(shape=self.update_image) self.random_shape() def update_image(self, *args): self.source = self.shapes[self.shape]["image"] |

I hope you found this useful! Let me know in the comments what you think 😉 and share!