Chronicles of a Restless Mind

Sunday, 2014-12-21

Minkowski Difference of Convex Polygons

(‘p’ and ‘o’ toggle rotation of the turquoise Player and purple Obstacle, respectively, while ‘h’ hides the player.)

This shows the Minkowski "difference" of a regular pentagon and an equilateral triangle. That is, it shows the Minkowski sum of the pentagon and the negation of the triangle. If the triangle's origin is within the resulting shape (which is called a configuration space obstacle or CSO), then the triangle overlaps the pentagon.

The Minkowski sum of convex polygons can be computed very simply: you just sort all the edges of both polygons by angle and string them together end-to-end in that order to make a new polygon. Since the polygons are convex, the edges of each polygon are already in order by angle, so you just have to loop through and merge them together.

Most places I have seen which mention this algorithm suggest taking the left-most (or upper-most, or whatever) point on both polygons as a starting point. I have instead chosen to always start with the first point of one polygon and demonstrate the use of the dot product to find the point on the other polygon which is farthest in that direction.

Then, assuming both polygons are "wound" the same direction, we can use the dot product to compare which edge is to the left of the other edge (or to the right, whichever direction is "inside" for your winding direction), and add that edge to the output polygon. We repeat until no edges are left in either input polygon.

Javascript:

// Use the dot product to find the index of the polygon vertex
// which is furthest along the direction given by `dir`.
var startIndex = function(poly, dir) {
    var l, d = Number.NEGATIVE_INFINITY;
    for(var i=0; i<poly.length; ++i) {
        var d2 = dir.dot(poly[i]);
        if(d2 > d) { d = d2; l = i; }
    }
    return l;
}

// Determine whether `this` points to the left of `v` (by taking
// the dot product with v's perpendicular).
Vec2.prototype.inside = function(v) {
    return v.dup().perp().dot(this) > 0;
}

var minkowskiSum = function(p, q) {
    // size of input polygons and starting indices/edges
    var n = p.length, i = 0;
    var m = q.length, j = startIndex(q, p[i]);
    var pe = p[(i+1)%n].dup().sub(p[i]);
    var qe = q[(j+1)%m].dup().sub(q[j]);

    // output polygon and initial vertex
    var out = []
    var vertex = p[i].dup().add(q[j]);

    // loop over all edges
    for(var k=0; k<n+m; ++k) {
        out.push(vertex.dup());

        // add "inside-most" edge to get next output vertex
        if(pe.inside(qe)) {
            vertex.add(pe);
            i = (i+1)%n;  pe.copy(p[(i+1)%n]).sub(p[i]);
        } else {
            vertex.add(qe);
            j = (j+1)%m;  qe.copy(q[(j+1)%m]).sub(q[j]);
        }
    }
    return out;
}

var minkowskiDifference = function(p, q) {
	return minkowskiSum(p, negatePolygon(q));
}