Click here to Skip to main content
12,623,511 members (28,890 online)
Click here to Skip to main content
Articles » Multimedia » GDI+ » General » Downloads

Stats

300.8K views
10.7K downloads
151 bookmarked
Posted

2D Polygon Collision Detection

, 20 Sep 2006 MIT
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;
					}
				}
			}
		}


	}

}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

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.

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

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