## Detecting Whether Two Convex Polygons Overlap

In a previous post I described how to tell whether two axially aligned bounding boxes (AABB’s) intersected. The solution was presented as a process of elimination: if box A is to the left of B, to the the right of B, above B, or below B, then they cannot intersect.

This rule is a special case application of the separating axis theorem. This theorem says that if two 2D convex polygons don’t intersect, then there exists some line (known as a “separating axis”), such that when the polygons are projected onto that line, the projections of the two polygons will not overlap.

Here are two non-overlapping polygons. The black line is a separating axis for these two polygons, because the projections of the polygons onto that axis (the thick green and blue blues) do not overlap.

A separating axis is really just a direction (we would describe the axis as a vector). Translating the axis does not affect the polygon projections.

This immediately suggests an algorithm to determine if two convex polygons intersect: check all the potential separating axes; if the polygon projections overlap on all such axes, then they polygons intersect. Otherwise, as soon as a separating axis is found, we can declare the polygons to be non-intersecting.

Unfortunately, there are an infinite number of directions. Fortunately, as it turns out, we must only try a limited subset of those directions. In 2D, we need only test the directions that are perpendicular a polygon edge. For example, in the example above, the separating axis is perpendicular to the leftmost edge of the polygon on the right. For 2D AABB’s, all of the polygon edges are horizontal or vertical, so there are only two possible separating axis, one vertical and horizontal. (There were four cases to test, two per axis, because nonoverlapping polygons may be on either side of each other.)

We now have a strategy for detecting the overlap of 2D convex polygons. Scan all the edges of both polygons. For each edge, we form a candidate separating axis that is perpendicular to that edge. We project the two polygons onto the axis, and test whether their projections overlap. If not, the polygons are non-intersecting, and we are done. If they overlap, keep searching. If the polygons are overlapping on all candidate separating axes, then we can declare them to be overlapping — that is what the separating axis theorem guarantees us.

But what exactly does it mean to project the polygons onto an axis? How do we represent that projection, in such a way that we can tell if the projections overlap? The dot product is the answer. Let’s translate our axis so that it contains the origin. (We said that this does not change whether the projections overlap.) Now we can describe the the projection of any given polygon vertex onto this axis by giving the signed distance from the projected vertex to the origin. This distance just so happens to be precisely what we get when we dot the vertex with a unit vector parallel to the axis, which we’ll call v.

The dot product gives us a tool to describe the projection of a polygon onto each candidate separating axis v. For each polygon vertex, we take the dot product of the vertex with v, which gives us a signed distance from the origin. We collect the minimum and maximum of these distance, which gives us the extents of the projection, labeled amin and amax in the figure above. Note that we we don’t know or care ahead of time which points will be a1 and a2 as the figure above might lead you to believe; all we need are amin and amin. A simple one dimensional overlap test of amin and amax against the bmin and bmax tells us if the projections overlap.

In fact, v need not be a unit vector at all. If we scale v by some factor k, then that will scale the numeric values of amin, amax, bmin, and bmax by this same factor, and they will no longer measure the distance to the origin, but it will not affect whether the intervals overlap.

The following code snippet illustrates these ideas.

```// Very simple vector class struct Vec2D { float x,y; };   // Dot product operator float dot(const Vec2D &a, const Vec2D &b) { return a.x*b.x + a.y*b.y; }   // Here is our high level entry point. It tests whether two polygons intersect. The // polygons must be convex, and they must not be degenerate. bool convexPolygonOverlap( int aVertCount, const Vec2D *aVertList, int bVertCount, const Vec2D *bVertList ) {   // First, use all of A's edges to get candidate separating axes if (findSeparatingAxis(aVertCount, aVertList, bVertCount, bVertList)) return false;   // Now swap roles, and use B's edges if (findSeparatingAxis(bVertCount, bVertList, aVertCount, aVertList)) return false;   // No separating axis found. They must overlap return true; }   // Helper routine: test if two convex polygons overlap, using only the edges of // the first polygon (polygon "a") to build the list of candidate separating axes. bool findSeparatingAxis( int aVertCount, const Vec2D *aVertList, int bVertCount, const Vec2D *bVertList ) {   // Iterate over all the edges int prev = aVertCount-1; for (int cur = 0 ; cur < aVertCount ; ++cur) {   // Get edge vector. (Assume operator- is overloaded) Vec2D edge = aVertList[cur] - aVertList[prev];   // Rotate vector 90 degrees (doesn't matter which way) to get // candidate separating axis. Vec2D v; v.x = edge.y; v.y = -edge.x;   // Gather extents of both polygons projected onto this axis float aMin, aMax, bMin, bMax; gatherPolygonProjectionExtents(aVertCount, aVertlist, v, aMin, aMax); gatherPolygonProjectionExtents(bVertCount, bVertlist, v, bMin, bMax);   // Is this a separating axis? if (aMax < bMin) return true; if (bMax < aMin) return true;   // Next edge, please prev = cur; }   // Failed to find a separating axis return false; }   // Gather up one-dimensional extents of the projection of the polygon // onto this axis. void gatherPolygonProjectionExtents( int vertCount, const Vec2D *vertList, // input polygon verts const Vec2D &v, // axis to project onto float &outMin, float &outMax // 1D extents are output here ) {   // Initialize extents to a single point, the first vertex outMin = outMax = dot(v, vertList[0]);   // Now scan all the rest, growing extents to include them for (int i = 1 ; i < vertCount ; ++i) { float d = dot(v, vertList[i]); if (d < outMin) outMin = d; else if (d > outMax) outMax = d; } }```

Let’s hasten to add a few words of warning. The first is a warning concerning robustness: this code assumes valid convex polygons. If any of the edges are degenerate, or if the polygon is concave, this routine can produce unexpected results. Of course, the separating axis theorem applies only to convex polygons. Detecting the intersection of concave polygons is a trickier business. The second warning is concerning performance. The algorithm above is clearly O(N2). For large values of N, different algorithms can be faster. A standard approach is to sort the vertices vertically, and then sweep a horizontal line through the polygons, stopping at “event points” to see if the polygons have horizontal overlap at the given location. With a small bit of extra work, this approach can also be made to work for concave polygons.

The separating axis extends naturally into 3D, to test whether convex polyhedra overlap. It is this use of the theorem that gets the most attention in video games, since this test is needed in collision detection. The set of potential separating axes starts with vectors perpendicular to the polygon faces, which is analogous to what we did here in 2D. Unfortunately, in 3D things are a bit trickier and this list is not sufficient; there are cases where the polyhedra to not intersect, but a separating axis cannot be found among this simple set. We must also include certain cross products in the candidate set.

This entry was posted in Uncategorized and tagged . Bookmark the permalink.