Minkowski Sums of Convex Polygons

Reference: de Berg et al., Computational Geometry: Algorithms and Applications, page 295.

Input: Two convex polygons A and B, given by lists of vertices in counter-clockwise order, starting with the vertex with the smallest y-coordinate (and, in case of a tie, the smallest x-coordinate).
Output: List of vertices of the Minkowski sum, in counter-clockwise order.

minkowskiSum[polyA_,polyB_]:=Module[
{m=Length[polyA],n=Length[polyB],
i=1,j=1,
mSum ={} (* this will store the vertices of the Minkowski sum *),
angleA,angleB
},

(* iterate around both polygons simultaneously *)
While[(i≤m||j≤n),
AppendTo[mSum,polyA[[Mod[i-1,m]+1]]+polyB[[Mod[j-1,n]+1]]];
(* testing: Print[{mSum,i,j}]; *)

(* compute the angles of the next edge of each polygon with the x-axis *)
angleA=angle[polyA[[Mod[i-1,m]+1]],polyA[[Mod[i,m]+1]]];
If[i==m+1,angleA+=2Pi];
angleB=angle[polyB[[Mod[j-1,n]+1]],polyB[[Mod[j,n]+1]]];
If[j==n+1,angleB+=2Pi];

(* increment at least one of the counters *)
If[angleA≤angleB,i++];
If[angleA≥angleB,j++];
];

mSum (* return the Minkowski sum *)
]

The Minkowski sum algorithm requires a function that returns the angle of a vector (OverVector[vw]) with the positive x-axis. The following function returns an angle in the interval [0,2π).

angle[v_,w_]:=Module[{vec = w - v,θ},
θ=VectorAngle[vec,{1,0}];
If[vec[[2]]≥0,θ,2π-θ]
]

Example

Here are two polygons:

vertA={{-1,-1},{2,0.5},{1,3}};
vertB={{0,0},{3,0},{3,3},{0,3}};

GraphicsRow[{
Graphics[{LightBlue,EdgeForm[{Blue, Thick}],Polygon[vertA]},Frame->True],Graphics[{LightGreen,EdgeForm[{Green, Thick}],Polygon[vertB]},Frame->True]
}]

Compute the Minkowski sum A ⊕B:

sumAB=minkowskiSum[vertA,vertB]

To verify that this is correct, let’s draw some diagrams. We will draw copies of one polygon, offset at the vertices of the other polygon. The following function will help with this.

copies[vertA_,vertB_]:=Module[{list={}},
Do[
AppendTo[list,Polygon[#+vertB[[i]]&/@vertA]]
,{i,1,Length[vertB]}];
list
]

Make a list of copies of A, offset at each vertex of B.

copies[vertA,vertB]

Now draw some diagrams. The purple polygon is the Minkowski sum.

Graphics[{
{LightPurple,EdgeForm[{Purple, Thick}],Polygon[sumAB]},
{EdgeForm[{Blue,Thick,JoinForm["Round"]}],FaceForm[],copies[vertA,vertB]},
{EdgeForm[{Green,Thick,JoinForm["Round"]}],FaceForm[],Polygon[vertB]},
},Frame->True
]

Graphics[{
{LightPurple,EdgeForm[{Purple,Thick}],Polygon[sumAB]},
{EdgeForm[{Blue,Thick,JoinForm["Round"]}],FaceForm[],copies[vertB,vertA]},
{EdgeForm[{Green,Thick,JoinForm["Round"]}],FaceForm[],Polygon[vertA]}
},Frame->True
]