13,259,771 members (53,971 online)

#### Stats

325.3K views
153 bookmarked
Posted 13 Sep 2006

# 2D Polygon Collision Detection

, 20 Sep 2006
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.
 PolygonIntersection (Intersection).application PolygonIntersection (Intersection).exe PolygonIntersection (Intersection).exe.manifest obj Debug PolygonIntersection (Intersection).exe.manifest Refactor TempPE Release PolygonIntersection (Intersection).exe.manifest Refactor TempPE Properties ```using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace PolygonIntersection { public partial class MainForm : Form { // Structure that stores the results of the PolygonCollision function public struct PolygonCollisionResult { public bool WillIntersect; // Are the polygons going to intersect forward in time? public bool Intersect; // Are the polygons currently intersecting public Vector MinimumTranslationVector; // The translation to apply to polygon A to push the polygons appart. } // Check if polygon A is going to collide with polygon B for the given velocity 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. // First moves the polygons by their velocity // then move polygonA by MinimumTranslationVector. if (result.WillIntersect) result.MinimumTranslationVector = translationAxis * minIntervalDistance; return result; } // 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; } } // 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 d = axis.DotProduct(polygon.Points[0]); min = d; max = d; for (int i = 0; i < polygon.Points.Count; i++) { d = polygon.Points[i].DotProduct(axis); if (d < min) { min = d; } else { if (d > max) { max = d; } } } } } } ```

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

## Share

 Software Developer Pogopixels Ltd 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.

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...

Web01 | 2.8.171114.1 | Last Updated 20 Sep 2006
Article Copyright 2006 by Laurent Cozic