### 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));
}
```