Click here to Skip to main content
11,644,284 members (65,921 online)
Click here to Skip to main content

2D Polygon Collision Detection

, 20 Sep 2006 MIT 265.8K 8.9K 150
Rate this:
Please Sign up or sign in to vote.
An article on polygon collision detection. Can be used to implement collision between sprites in a 2D game. The algorithm can also be extended to 3D.

Sample Image

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);

Reference

History

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

License

This article, along with any associated source code and files, is licensed under The MIT License

Share

About the Author

Laurent Cozic
Software Developer Pogopixels Ltd
United Kingdom United Kingdom
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.

Have a look at pogopixels.com for more information.

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

You may also be interested in...

Comments and Discussions

 
SuggestionOnly convex polygons Pin
Piasco5-Jul-15 22:29
memberPiasco5-Jul-15 22:29 
QuestionPoint of Intersection Pin
Member 1137297024-Mar-15 12:58
memberMember 1137297024-Mar-15 12:58 
QuestionIncorrect link to GPWiki article Pin
Sri Harsha Chilakapati4-Dec-14 18:16
memberSri Harsha Chilakapati4-Dec-14 18:16 
BugPossibly incorrect IntervalDistance Pin
Member 1115923520-Oct-14 5:12
memberMember 1115923520-Oct-14 5:12 
QuestionCollision problem? Pin
Member 1040355211-Aug-14 1:18
memberMember 1040355211-Aug-14 1:18 
AnswerRe: Collision problem? Pin
andreivu20-Oct-14 5:31
memberandreivu20-Oct-14 5:31 
QuestionDetect what points did polygons intersect.. Pin
egenita6-Oct-13 23:41
memberegenita6-Oct-13 23:41 
QuestionQuick question for greater understanding Pin
tankerpat15-Sep-13 14:02
membertankerpat15-Sep-13 14:02 
GeneralMy vote of 5 Pin
Milad.D11-Jan-13 13:26
memberMilad.D11-Jan-13 13:26 
BugError in algorithm while translating moving objects position Pin
Shnarwhal13-Nov-11 1:38
memberShnarwhal13-Nov-11 1:38 
BugCollision for moving objects seems to be wrong. [modified] Pin
Thomas Happ30-Aug-11 9:29
memberThomas Happ30-Aug-11 9:29 
Questiongreat, but small problem? Pin
bsabiston6-Jul-11 4:27
memberbsabiston6-Jul-11 4:27 
GeneralMy vote of 5 Pin
MSM_1-Feb-11 4:13
memberMSM_1-Feb-11 4:13 
QuestionMultiple collision Pin
kronenthaler13-May-09 9:34
memberkronenthaler13-May-09 9:34 
GeneralThis algorithm is wrong for moving object detection Pin
twobitshift8-Apr-09 12:25
membertwobitshift8-Apr-09 12:25 
GeneralRe: This algorithm is wrong for moving object detection Pin
Evil OverLord24-Jul-09 21:36
memberEvil OverLord24-Jul-09 21:36 
GeneralRe: This algorithm is wrong for moving object detection Pin
twobitshift30-Jul-09 6:10
membertwobitshift30-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.
GeneralRe: This algorithm is wrong for moving object detection Pin
cajoncillos7-Sep-10 7:38
membercajoncillos7-Sep-10 7:38 
GeneralRe: This algorithm is wrong for moving object detection Pin
seifer50322-Jul-11 8:11
memberseifer50322-Jul-11 8:11 
GeneralRe: This algorithm is wrong for moving object detection Pin
Member 1040355213-Aug-14 23:49
memberMember 1040355213-Aug-14 23:49 
Generalgive example for concave polygons collision Pin
jjqcat18-Mar-09 15:23
memberjjqcat18-Mar-09 15:23 
QuestionHow To Fix Insane Processor Usage Pin
Reelix5-Mar-09 0:15
memberReelix5-Mar-09 0:15 
GeneralJust what I've been looking for... Pin
VCKicks3-Sep-08 9:01
memberVCKicks3-Sep-08 9:01 
QuestionPoints comparing Pin
Varangian28-Apr-08 23:25
memberVarangian28-Apr-08 23:25 
GeneralProblem... Pin
Varangian28-Apr-08 23:23
memberVarangian28-Apr-08 23:23 
GeneralA Small Bug Pin
Walter O Dias26-Dec-07 0:35
memberWalter O Dias26-Dec-07 0:35 
GeneralRe: A Small Bug Pin
salute22-Jan-09 22:47
membersalute22-Jan-09 22:47 
GeneralJust a small thing Pin
Jeppe A.22-Jun-07 21:34
memberJeppe A.22-Jun-07 21:34 
QuestionWhat about?... Pin
Super Lloyd25-Sep-06 13:18
memberSuper Lloyd25-Sep-06 13:18 
AnswerRe: What about?... Pin
Laurent Cozic26-Sep-06 5:50
memberLaurent Cozic26-Sep-06 5:50 
Generalgood article Pin
TomekS22-Sep-06 1:08
memberTomekS22-Sep-06 1:08 
GeneralRe: good article Pin
Khaniya1-Apr-10 0:46
memberKhaniya1-Apr-10 0:46 
GeneralGood article. Here's another... Pin
Shawn Poulson20-Sep-06 15:22
memberShawn Poulson20-Sep-06 15:22 
Questionnow what? Pin
jconwell19-Sep-06 8:37
memberjconwell19-Sep-06 8:37 
AnswerRe: now what? Pin
Laurent Cozic19-Sep-06 9:25
memberLaurent Cozic19-Sep-06 9:25 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.150731.1 | Last Updated 20 Sep 2006
Article Copyright 2006 by Laurent Cozic
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid