# 2D Polygon Collision Detection

By , 20 Sep 2006

## Introduction

This article describes how to detect the collision between two moving (2D) polygons. It's not the first tutorial on the topic, however, the tutorials on the net tend to be a bit too complex for a relatively simple problem. The source codes I could find also had too many abbreviations that I don't get, or were crippled with C optimizations. So here, I'll try to keep it as simple as possible. In any case, it should be possible to include the functions presented here to your C# projects quite straightforwardly. The technique can be used to detect collisions between sprites as an alternative to pixel-perfect collisions which are usually too slow.

## Background

To detect if two polygons are intersecting, we use the Separating Axis Theorem. The idea is to find a line that separates both polygons - if such a line exists, the polygons are not intersecting (Fig. 1). The implementation of this theorem is relatively simple, and could be summed up in this pseudo code:

• For each edge of both polygons:
• Find the axis perpendicular to the current edge.
• Project both polygons on that axis.
• If these projections don't overlap, the polygons don't intersect (exit the loop).

This can be easily extended to deal with moving polygons by adding one additional step. After having checked that the current projections do not overlap, project the relative velocity of the polygons on the axis. Extend the projection of the first polygon by adding to it the velocity projection (Fig. 2). This will give you the interval spanned by the polygon over the duration of the motion. From there, you can use the technique used for static polygons: if the projections of polygons A and B don't overlap, the polygons won't collide. (NB: However, remember that if the intervals do overlap, it doesn't necessarily mean that the polygons will collide. We need to do the test for all the edges before knowing that.)

Once we have found that the polygons are going to collide, we calculate the translation needed to push the polygons apart. The axis on which the projection overlapping is minimum will be the one on which the collision will take place. We will push the first polygon along this axis. Then, the amount of translation will simply be the amount of overlapping on this axis (Fig. 3).

That is it! Now, each time a collision occurs, the first polygon will nicely slide along the surface of the other polygon.

Figure 1: Projections of the polygons onto an axis.

Figure 2: Projections for moving polygons.

Figure 3: Find the minimum interval overlapping, then calculate the translation required to push the polygons apart.

## Using the code

The `PolygonCollision()` function does all of the above, and returns a `PolygonCollisionResult` structure containing all the necessary information to handle the collision:

```// Structure that stores the results of the PolygonCollision function
public struct PolygonCollisionResult {
// Are the polygons going to intersect forward in time?
public bool WillIntersect;
// Are the polygons currently intersecting?
public bool Intersect;
// The translation to apply to the first polygon to push the polygons apart.
public Vector MinimumTranslationVector;
}```

Two helper functions are used by the `PolygonCollision` function. The first one is used to project a polygon onto an axis:

```// Calculate the projection of a polygon on an axis
// and returns it as a [min, max] interval
public void ProjectPolygon(Vector axis, Polygon polygon,
ref float min, ref float max) {
// To project a point on an axis use the dot product
float dotProduct = axis.DotProduct(polygon.Points[0]);
min = dotProduct;
max = dotProduct;
for (int i = 0; i < polygon.Points.Count; i++) {
dotProduct = polygon.Points[i].DotProduct(axis);
if (d < min) {
min = dotProduct;
} else {
if (dotProduct> max) {
max = dotProduct;
}
}
}
}```

The second one returns the signed distance between two given projections:

```// Calculate the distance between [minA, maxA] and [minB, maxB]
// The distance will be negative if the intervals overlap
public float IntervalDistance(float minA, float maxA, float minB, float maxB) {
if (minA < minB) {
return minB - maxA;
} else {
return minA - maxB;
}
}```

Finally, here is the main function:

```// Check if polygon A is going to collide with polygon B.
// The last parameter is the *relative* velocity
// of the polygons (i.e. velocityA - velocityB)
public PolygonCollisionResult PolygonCollision(Polygon polygonA,
Polygon polygonB, Vector velocity) {
PolygonCollisionResult result = new PolygonCollisionResult();
result.Intersect = true;
result.WillIntersect = true;

int edgeCountA = polygonA.Edges.Count;
int edgeCountB = polygonB.Edges.Count;
float minIntervalDistance = float.PositiveInfinity;
Vector translationAxis = new Vector();
Vector edge;

// Loop through all the edges of both polygons
for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) {
if (edgeIndex < edgeCountA) {
edge = polygonA.Edges[edgeIndex];
} else {
edge = polygonB.Edges[edgeIndex - edgeCountA];
}

// ===== 1. Find if the polygons are currently intersecting =====

// Find the axis perpendicular to the current edge
Vector axis = new Vector(-edge.Y, edge.X);
axis.Normalize();

// Find the projection of the polygon on the current axis
float minA = 0; float minB = 0; float maxA = 0; float maxB = 0;
ProjectPolygon(axis, polygonA, ref minA, ref maxA);
ProjectPolygon(axis, polygonB, ref minB, ref maxB);

// Check if the polygon projections are currentlty intersecting
if (IntervalDistance(minA, maxA, minB, maxB) > 0)\
result.Intersect = false;

// ===== 2. Now find if the polygons *will* intersect =====

// Project the velocity on the current axis
float velocityProjection = axis.DotProduct(velocity);

// Get the projection of polygon A during the movement
if (velocityProjection < 0) {
minA += velocityProjection;
} else {
maxA += velocityProjection;
}

// Do the same test as above for the new projection
float intervalDistance = IntervalDistance(minA, maxA, minB, maxB);
if (intervalDistance > 0) result.WillIntersect = false;

// If the polygons are not intersecting and won't intersect, exit the loop
if (!result.Intersect && !result.WillIntersect) break;

// Check if the current interval distance is the minimum one. If so store
// the interval distance and the current distance.
// This will be used to calculate the minimum translation vector
intervalDistance = Math.Abs(intervalDistance);
if (intervalDistance < minIntervalDistance) {
minIntervalDistance = intervalDistance;
translationAxis = axis;

Vector d = polygonA.Center - polygonB.Center;
if (d.DotProduct(translationAxis) < 0)
translationAxis = -translationAxis;
}
}

// The minimum translation vector
// can be used to push the polygons appart.
if (result.WillIntersect)
result.MinimumTranslationVector =
translationAxis * minIntervalDistance;

return result;
}```

The function can be used this way:

```Vector polygonATranslation = new Vector();

PolygonCollisionResult r = PolygonCollision(polygonA, polygonB, velocity);

if (r.WillIntersect) {
// Move the polygon by its velocity, then move
// the polygons appart using the Minimum Translation Vector
polygonATranslation = velocity + r.MinimumTranslationVector;
} else {
// Just move the polygon by its velocity
polygonATranslation = velocity;
}

polygonA.Offset(polygonATranslation);```

## History

• September 13, 2006: First version.
• September 14, 2006: Minor changes, and added the Reference section.

 Laurent Cozic Software Developer Pogopixels Ltd United Kingdom Member
Pogopixels is a London based software company specialising in the development of widgets, Flash and internet-based software.

It delivers innovative software solutions to companies using the latest technologies including Adobe AIR, Yahoo Widgets, or Google Desktop.

On my spare time, I work on the Appetizer open source project: http://app.etizer.org It's a portable dock for Windows.

Votes of 3 or less require a comment

 Search this forum Profile popups    Spacing RelaxedCompactTight   Noise Very HighHighMediumLowVery Low   Layout Open AllThread ViewNo JavascriptPreview   Per page 102550
 First PrevNext
 My vote of 5 Milad.D 11 Jan '13 - 13:26
 Error in algorithm while translating moving objects position Shnarwhal 13 Nov '11 - 1:38
 I found an error too and made a diagram. Here: http://i.imgur.com/HgNU5.png[^]   Let's make the big square static, then by common sense the small object's position should be translated to the left along the x axis. But the overlap is smaller in the y axis, so the algorithm would translate it downwards and that's not good. Am I right? Sign In·View Thread·Permalink
 Collision for moving objects seems to be wrong. [modified] Thomas Happ 30 Aug '11 - 9:29
 I changed the example code to use squares of size 100, and set the arrow keys to move them 50 units a press. I also mapped the numpad to allow me to move at diagonals (50 in x and 50 in y). That was the only change I made.   When I do this, I get very strange results when moving one cube at a diagonal next to another. In one case, when you would expect them to collide, my moving cube ended up shooting an addition 50 pixels in y.   I had the idea that maybe there is a flaw in computing both the current and future collision in the same loop; maybe it should be separated out. I haven't tried it; I don't think I can use this method for my game anyway.   EDIT: I found this on the ubiquitous "N" tutorial (http://www.metanetsoftware.com/technique/tutorialA.html[^]) which may explain these results:   " note that the projection vector sometimes "jumps" from one axis to the other suddenly. This means that while you might see an AABB move down into another, it will be pushed out to the left or right (instead of upward) because, due to how far down it moved in one frame, the left/right direction produces a smaller projection vector.   This problem is an unavoidable part of the projection method of collision response, and happens if objects in the world move too far in one frame. The smaller an object is, and the faster it is moving, the more likely it is that this problem will occur." modified on Wednesday, August 31, 2011 4:05 PM Sign In·View Thread·Permalink
 great, but small problem? bsabiston 6 Jul '11 - 4:27
 Hello,   This was a great example, it really helped me with my game. But I have found that sometimes the repositioning vector seems wrong. I'm talking about the vector which tells you how to move the intersecting object so that they no longer intersect. Sometimes when I run one object into another, it will bump along the edge like it should, then suddenly it is transported all the way through and to the other side of the object! Do you know why this might happen? It happens infrequently enough that I haven't been able to catch it in a debugger.   Thanks Bob Sign In·View Thread·Permalink
 My vote of 5 MSM_ 1 Feb '11 - 4:13
 Multiple collision kronenthaler 13 May '09 - 9:34
 Hi,   it is a great article, i have some specific questions:   In the example (MainForm.cs) you break the collision detection test after detect a intersection. But, if the player is in contact with 2 object at the same time(e.g, the floor and the enemy) and the player's position is updated one time.   1. Which collision is resolved first? 2. How do you combine the multiple translation vectors? or just keep the shortest or the longest one?   any idea will be welcome. Sign In·View Thread·Permalink
 This algorithm is wrong for moving object detection twobitshift 8 Apr '09 - 12:25
 Consider a simple case. Of two axis aligned, squares that are moving.   A:1-by-1 axis aligned square center: (2.5, 2.5) velocity: <-4,-4> (Va) B: 1-by-1 axis aligned square center: (-1.5, 2.5) velocity: <1, 0> (Vb)   Using the above algorithm:   relative velocity Vr = Va - Vb = <-4,-4> - <1,0> = <-5,-4>   Since these are axis aligned, only two "edge-axis" to test: x-axis, y-axis   Lets start with x-axis: axis = <1,0> Projection of A (Ax): min=2 max=3 Projection of B (Bx): min=-2 max=-1 Projection of Vr(Vx): -5   (Ax.min < Bx.min) = false: so IntervalDistance (ID) = Ax.min - Ax.max = 2 - (-1) = 3 ID >0 : so Intersect = false; Vx < 0: so A.min - Vx = 2 + (-5) = -7 -7 < Bx.min: so IntervalDistance for moving (IDm) = Bx.min - Ax.max = -1 - 3 = -4 IDm < 0: so WillIntersect = true!   Now y-axis axis = <0, 1> Projection of A (Ay): min=2, max=3 Projection of B (By): min=2, max=3 Projection of Vr(Vy): -4   (Ay.min < By.min) = false: so ID = Ay.min - By.max = 2 - 3 = -1 ID <0: so Intersect = true Vy < 0: so A.min - Vy = 2 + (-4) = -6 -6 < By.min: so IDm = By.min = Ay.max = 1 -3 = -2 IDm < 0 so WillIntersect = true!   So we have completed our loop and WillIntersect is set to True. Although this is also not true since the paths of these objects never actually cross.   This is a short-cut that CAN be used to determine whether you need to perform a real detection test. This is very similar to sweep algorithms, if you are familiar with those. However it is no substitute (not even as an estimate) of real collision detection.   modified on Wednesday, April 8, 2009 7:38 PM Sign In·View Thread·Permalink
 Re: This algorithm is wrong for moving object detection Evil OverLord 24 Jul '09 - 21:36
 What do you mean?   You showed that the calculation proves that the objects will collide. And they will!   You said "So we have completed our loop and WillIntersect is set to True. Although this is also not true since the paths of these objects never actually cross."..   But they do cross. Have you drawn out the example you gave? They cross. Sign In·View Thread·Permalink
 Re: This algorithm is wrong for moving object detection twobitshift 30 Jul '09 - 6:10
 If you extend the paths of these objects, the paths will in fact intersect. But the intersection information is useless. BECAUSE: the point at which they intersect is not a point shared by both objects.   object A is at the point of intersection at time=0 object B is at the point of intersection at time=4   Although the PROJECTION of the objects intersect, the objects themselves do not. So the proposed algorithm, without additional computation is useless. Sign In·View Thread·Permalink
 Hy.   If you treat one of the objects as static, and substract the speed of the "static" object from the speed of the "moving" object, the algorithm will work flawlessly (i don't remember shurely if its substracting or obtaining the cross product of the speeds :P) Sign In·View Thread·Permalink
 Re: This algorithm is wrong for moving object detection seifer503 22 Jul '11 - 8:11
 I noticed the same thing. The algorithm as specified above will not detect the (non) collision in this case. I think I may have a solution... What if, after we are done processing all edges of both polygons, we project both polygons onto an axis perpendicular to the movement vector? These projections would not intersect in this case, causing the algorithm to determine that the objects did not collide. Sign In·View Thread·Permalink
 give example for concave polygons collision jjqcat 18 Mar '09 - 15:23
 How To Fix Insane Processor Usage Reelix 5 Mar '09 - 0:15
 1.) Remove the Invalidate(); from the Paint   2.) Create an enabled timer with a 5ms delay.   3.) Add the Invalidate(); under the timer's Tick event.   Voila! 0 - 1% Processor Usage down from full   -= Reelix =- Sign In·View Thread·Permalink
 Just what I've been looking for... VCKicks 3 Sep '08 - 9:01
 Points comparing Varangian 28 Apr '08 - 23:25
 Hi,   do the points and edges have to correspond with the collided Polygon?   I mean if I have 4 points and 4 edges... does it mean that point X of Polygon A has to be compared with same point X of Polygon B? or point X of Polygon A can be compared with point Y of Polygon B?   Thank! Sign In·View Thread·Permalink
 Problem... Varangian 28 Apr '08 - 23:23
 Hi,   do the points and edges have to correspond with the collided Polygon?   I mean if I have 4 points and 4 edges... does it mean that point X of Polygon A has to be compared with same point X of Polygon B? or point X of Polygon A can be compared with point Y of Polygon B?   Thank! Sign In·View Thread·Permalink
 A Small Bug Walter O Dias 26 Dec '07 - 0:35
 I trie to check collision between a player 2d poligon and a Star. When the player check a collision in star, the logic not work perfectly.   Star Object Polygon:   ```p = new Polygon(); p.Points.Add(new Vector(179, 1)); // 01 p.Points.Add(new Vector(233, 112)); // 02 p.Points.Add(new Vector(356, 130)); // 03 p.Points.Add(new Vector(267, 216)); // 04 p.Points.Add(new Vector(288, 399)); // 05 p.Points.Add(new Vector(179, 291)); // 06 p.Points.Add(new Vector(69, 399)); // 07 p.Points.Add(new Vector(90, 216)); // 08 p.Points.Add(new Vector(1, 130)); // 09 p.Points.Add(new Vector(124, 112)); // 10 p.Offset(100, 100);   polygons.Add(p);```;   You can solve this little issue.   Ps.: I got my five Sign In·View Thread·Permalink
 Re: A Small Bug salute 22 Jan '09 - 22:47
 That should not be a bug. I assume the star is concave. You could split up the star to convex polygons (e.g. triangles). Then it should work ... Sign In·View Thread·Permalink
 Just a small thing Jeppe A. 22 Jun '07 - 21:34
 Just a small comment about your ProjectPolygon function. You calculate the dot product between the axis and polygon.Points[0] twice . You could simply start your loop from 1 instead to avoid this, i.e. for (int i=1; i < polygon.Points.Count; i++), or set the initial values for min and max to float.MinValue and float.MaxValue respectively   JeppeBeCool Sign In·View Thread·Permalink
 What about?... Super Lloyd 25 Sep '06 - 13:18
 Re: What about?... Laurent Cozic 26 Sep '06 - 5:50
 Hi thanks   Actually I never tried to deal with concave polygons. It's a more complex problem but basically I imagine one solution could be to divide the concave polygons into a set of convex polygons and then do your collisions on this.   There's some examples here on how to triangulate a polygon. It might be worth having a look at it. Sign In·View Thread·Permalink
 good article TomekS 22 Sep '06 - 1:08
 I am looking for 2d polygon intersecion method, it should return polygon2d object as a result of intersecion of two 2dpolygons. can you help me ?   tomekS Sign In·View Thread·Permalink
 Re: good article Khaniya 1 Apr '10 - 0:46
 Hi TomerkS   I am also looking for same   If you find solution, please let me know Thank you   Life's Like a mirror. Smile at it & it smiles back at you.- P Pilgrim So Smile Please Sign In·View Thread·Permalink
 Good article. Here's another... Shawn Poulson 20 Sep '06 - 15:22
 I found this web tutorial also very informative. It's a little more thorough in that it starts out easy and works into more complicated problems. Also includes interactive Flash demos with draggable objects. I found this very easy to comprehend.   http://www.harveycartel.org/metanet/tutorials/tutorialA.html     --- Shawn Poulson spoulson@explodingcoder.com Sign In·View Thread·Permalink
 now what? jconwell 19 Sep '06 - 8:37
 I downloaded the source...compiled it...ran it...and now i've got 3 shapes on the form that dont move. there are no menus, or any sort of way to interact with the app.   How can you show collision detection, if the shapes dont move?   John Conwell Sign In·View Thread·Permalink
 Last Visit: 31 Dec '99 - 18:00     Last Update: 25 May '13 - 7:21 Refresh 12 Next »