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.

28 Responses to Detecting Whether Two Convex Polygons Overlap

  1. Pingback: Printable Laundry Detergent Coupons 2012

  2. Pingback: free credit reports

  3. cash advance says:

    One contrasting option to here and now subsidizing by means of payday advances is to utilize charge cards.

  4. I was looking at some of your articles on this internet
    site and I conceive this website is real informative! Keep on posting.

  5. The arrangement of potential isolating tomahawks begins with vectors opposite of the polygon confronts, which is undifferentiated from what we did here in 2D. Tragically, in 3D things are somewhat trickier and this rundown is not adequate; there are situations where the polyhedral to not meet, but rather an isolating hub can’t be found among this straightforward set.

  6. ArleneDatte says:

    Absolutely NEW update of SEO/SMM package “XRumer 16.0 + XEvil 3.0″:
    captchas breaking of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another categories of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM programms: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? You can find a lot of introducing videos about XEvil in YouTube.
    See you later ;)

    XRumer20170721

  7. ArleneDatte says:

    Revolutional update of SEO/SMM software “XRumer 16.0 + XEvil 3.0″:
    captchas breaking of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another types of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM programms: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? There are a lot of demo videos about XEvil in YouTube.
    Good luck!

    XRumer20170721

  8. ArleneDatte says:

    Absolutely NEW update of SEO/SMM software “XRumer 16.0 + XEvil 3.0″:
    captcha recognition of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another subtypes of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM software: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? There are a lot of impessive videos about XEvil in YouTube.
    See you later!

    XRumer20170721

  9. ArleneDatte says:

    Absolutely NEW update of SEO/SMM package “XRumer 16.0 + XEvil”:
    captchas regignizing of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another size-types of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM programms: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? There are a lot of impessive videos about XEvil in YouTube.
    Good luck!

    XRumer20170721

  10. Flossiecow says:

    Absolutely NEW update of SEO/SMM package “XRumer 16.0 + XEvil”:
    captcha breaking of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another categories of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM software: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other programms.

    Interested? There are a lot of impessive videos about XEvil in YouTube.
    See you later!

    XRumer20170725

  11. Flossiecow says:

    Revolutional update of SEO/SMM package “XRumer 16.0 + XEvil”:
    captchas regignizing of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another subtypes of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM software: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? You can find a lot of impessive videos about XEvil in YouTube.
    Good luck ;)

    XRumer20170725

  12. Flossiecow says:

    Revolutional update of SEO/SMM software “XRumer 16.0 + XEvil”:
    captcha regignizing of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another types of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM programms: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other programms.

    Interested? There are a lot of impessive videos about XEvil in YouTube.
    Good luck!

    XRumer20170725

  13. Flossiecow says:

    Revolutional update of SEO/SMM package “XRumer 16.0 + XEvil”:
    captchas recognition of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another categories of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM programms: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? You can find a lot of impessive videos about XEvil in YouTube.
    Good luck!

    XRumer20170725

  14. Flossiecow says:

    Absolutely NEW update of SEO/SMM package “XRumer 16.0 + XEvil”:
    captcha regignizing of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another categories of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM software: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other programms.

    Interested? There are a lot of demo videos about XEvil in YouTube.
    See you later ;)

    XRumer20170725

  15. Limited Time says:

    Nice post! I simply wished to follow up by letting you learn about this great system that I simply found. I made $459 simply in the very first 2 days of using it! Perfect for newbies.

  16. Carolynknoxy says:

    Revolutional update of SEO/SMM software “XRumer 16.0 + XEvil 3.0″:
    captchas solution of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another types of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM programms: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? You can find a lot of impessive videos about XEvil in YouTube.
    You read it – then IT WORKS!
    Good luck!

    XRumer201708

  17. Carolynknoxy says:

    Absolutely NEW update of SEO/SMM package “XRumer 16.0 + XEvil 3.0″:
    captcha solving of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another subtypes of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM software: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other programms.

    Interested? There are a lot of introducing videos about XEvil in YouTube.
    You read it – then IT WORKS!
    Good luck!

    XRumer201708

  18. Carolynknoxy says:

    Revolutional update of SEO/SMM package “XRumer 16.0 + XEvil 3.0″:
    captcha solution of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another size-types of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM software: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? You can find a lot of demo videos about XEvil in YouTube.
    You read it – then IT WORKS!
    Good luck ;)

    XRumer201708

  19. Carolynknoxy says:

    Absolutely NEW update of SEO/SMM software “XRumer 16.0 + XEvil”:
    captcha regignizing of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another size-types of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM programms: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other programms.

    Interested? You can find a lot of impessive videos about XEvil in YouTube.
    You read it – then IT WORKS!
    Good luck ;)

    XRumer201708

  20. Carolynknoxy says:

    Revolutional update of SEO/SMM package “XRumer 16.0 + XEvil 3.0″:
    captcha regignizing of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another types of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM programms: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? There are a lot of introducing videos about XEvil in YouTube.
    You read it – then IT WORKS!
    See you later ;)

    XRumer201708

  21. Carolynknoxy says:

    Revolutional update of SEO/SMM package “XRumer 16.0 + XEvil 3.0″:
    captchas regignizing of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another size-types of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM software: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? There are a lot of introducing videos about XEvil in YouTube.
    You read it – then IT WORKS!
    See you later ;)

    XRumer201708

  22. Carolynknoxy says:

    Revolutional update of SEO/SMM package “XRumer 16.0 + XEvil 3.0″:
    captcha solution of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another subtypes of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM software: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? You can find a lot of impessive videos about XEvil in YouTube.
    You read it – then IT WORKS!
    Good luck!

    XRumer201708

  23. Carolynknoxy says:

    Revolutional update of SEO/SMM software “XRumer 16.0 + XEvil”:
    captcha breaking of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another subtypes of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM software: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other programms.

    Interested? There are a lot of introducing videos about XEvil in YouTube.
    You read it – then IT WORKS!
    See you later ;)

    XRumer201708

  24. Carolynknoxy says:

    Revolutional update of SEO/SMM package “XRumer 16.0 + XEvil 3.0″:
    captcha solution of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another subtypes of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM programms: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? There are a lot of impessive videos about XEvil in YouTube.
    You read it – then IT WORKS!
    Good luck ;)

    XRumer201708

  25. Leeannjef says:

    Revolutional update of SEO/SMM software “XRumer 16.0 + XEvil”:
    captcha solution of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another types of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM programms: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other software.

    Interested? There are a lot of introducing videos about XEvil in YouTube.
    You read it – then IT WORKS!
    Good luck ;)

    XRumer201708c

  26. Leeannjef says:

    Revolutional update of SEO/SMM software “XRumer 16.0 + XEvil 3.0″:
    captchas solving of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another subtypes of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM software: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other programms.

    Interested? You can find a lot of introducing videos about XEvil in YouTube.
    You read it – then IT WORKS!
    Good luck!

    XRumer201708c

Leave a Reply to Buy essays online Cancel reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">