Polygon Collision Detection

Detecting collisions with regular polygons is easy. Their shapes and properties are always the same, no matter their size or position.
But what if we’re dealing with irregular polygons? Because they can assume an infinite number of shapes, sides and possible angles their properties are impossible to predict.

pointPolygon Polygon Collision DetectionLets start by detecting if a Point is colliding with a Polygon, according to the Jordan Curve Theorem (there are several techniques, but we’ll be focusing only on this one).

According to the theorem any closed shape divides the space in an “inside” and an “outside” areas.

To find out if a point is inside that shape we need to cast a ray. If the number of intersection points with the shape is even then the point is outside. But if the number of intersection points is odd, then the point is inside the shape.
The only exception to the rule is if the ray passes through one of the vertices. Then the opposite is true.

In other words, to determine the Point-Polygon collision we first need to have the linear equation for the ray and each edge of the polygon. And then we need to find all the intersection points between each edge and the ray:

m1x + b1 = m2x + b2

Since we’re dealing with a ray and not a full line, in order to count the amount of intersection points we need to take into account the direction of the ray:

if( y < py ){
// The intersection is below the Point
}
if( y > py ){
// The intersection is above the Point
}

 

 

 

polygonPolygon Polygon Collision DetectionThe Polygon-Polygon collision is similar, but an important difference is the polygons can be colliding without any of the vertices of one being inside of the other.

In other words, to determine if 2 polygons are colliding we need to loop through all of their edges, find their linear equation, determine their intersection points and then check if those intersection points fall within the limits of the edges, as explained here.

You may also like...