Minkowski difference with concave polygons

Question

When trying to calculate the Minkowski difference of two convex polygons I can simply find the set of vertices and use a gift wrapping algorithm to find the convex hull. (see below.)

However for concave polygons the convex hull algorithm is not appropriate as it will give me a false positive on collisions, is there a way I can adapt my code to easily find the correct expansion using the points already generated?

public List<Vector2D> MinkowskiDifference(Polygon other)
{
   List<Vector2D> vList = new List<Vector2D>();

   foreach (Vector2D vT in this.vertices)
   {
        foreach (Vector2D vO in other.vertices)
        {
            vList.Add((vT+this.position) - (vO+other.position));
        }
   }
   return vList;
}

public static Polygon ConvexHull(List<Vector2D> vList)
{
    List<Vector2D> S = vList;
    List<Vector2D> P = new List<Vector2D>();
    Vector2D endpoint;

    Vector2D pointOnHull = LeftMostPoint(S);
    int i = 0;
    do
    {
        P.Add(pointOnHull);
        endpoint = S[0];
        for (int j = 1; j < S.Count; j++)
        {
            if (endpoint == pointOnHull || RelPosition(P[i], endpoint, S[j]) == -1)
            {
                    endpoint = S[j];
            }
        }
        i++;
        pointOnHull = endpoint;
    } while (endpoint != P[0]);
    return new Polygon(P);
}

Jay Lemmon Jay Lemmon · Accepted Answer · 2017-03-16T12:41:43

The usual method is to decompose the concave polygon in to convex pieces, and iterate pairwise between the convex pieces of each polygon looking for a collision. If one of the polygons is too big to do this naively (made up of 100s of convex peices), you can add each piece to a broad phase.

Note that if you're doing something like GJK, you don't explicitly construct the Minkowski difference as a polygon. Rather, you walk around it implicitly by finding "support" vertices on it that are furthest along a given direction. Because the Minkowski difference is linearly separable, you can do this for each polygon in isolation then find their difference.

The idea can be a little hard to grok, but see eg: http://www.dyn4j.org/2010/04/gjk-distance-closest-points/

Minkowski difference with concave polygons

1 Answers