Minkowski sum of two convex polygons

Question

Background

Minkowski addition is a binary operation on two sets of points (usually geometric objects) in the Euclidean space. The Minkowski sum of two sets \$A\$ and \$B\$ is formally defined as follows:

$$ A+B = \{\mathbf{a}+\mathbf{b}\,|\,\mathbf{a} \in A,\ \mathbf{b} \in B\} $$

To say in plain English, given the origin and two figures, the Minkowski sum of the two figures is formed by the vector sum of each pair of points in the two figures. In the following image, the red shape is the Minkowski sum of the green and blue shapes.

It has an interesting property for two convex polygons: the edges of the original polygons are preserved (modulo translation) and sorted by polar angle (relevant info in Wikipedia), and therefore can be computed in \$\mathcal{O}(m+n)\$ (where \$m\$ and \$n\$ denote the number of vertices of two polygons respectively).

Task

Given two convex polygons, compute their Minkowski sum.

Each polygon is given as an ordered list of \$(x,y)\$ coordinates, and the output polygon should be represented in the same way. You can choose the ordering of vertices (clockwise or counterclockwise), but your code should handle different starting points of the same polygon ((0,0), (0,1), (1,0) is the same as (0,1), (1,0), (0,0)). A point that is in the middle of a straight edge is not a vertex, and therefore should not appear in the output. (See the first test case)

You may take each coordinate pair as a single complex number. The coordinates are guaranteed to be integers.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

A = [(0, 0), (0, 1), (1, 0)]
B = [(0, 0), (0, 1), (1, 1), (1, 0)]
A + B = [(0, 0), (0, 2), (1, 2), (2, 1), (2, 0)]

A = [(-1, 0), (0, 1), (1, 0)]
B = [(1, 0), (0, -1), (-1, 0)]
A + B = [(-2, 0), (-1, 1), (1, 1), (2, 0), (1, -1), (-1, -1)]

A = [(0, 0), (0, 1), (1, 3), (2, 4), (4, 5), (5, 5)]
B = [(0, 0), (1, 3), (3, 6), (6, 8), (9, 9)]
A + B = [
  (0, 0), (0, 1), (1, 4), (2, 6), (4, 9),
  (5, 10), (8, 12), (10, 13), (13, 14), (14, 14)]

A = [(0, 1), (0, 2), (1, 2), (1, 1)]
B = [(1, 0), (1, 1), (2, 1), (2, 0)]
A + B = [(1, 1), (1, 3), (3, 3), (3, 1)]

Answer 1

J, ⁷⁴ 58 bytes

Implements the algorithm outlined in the linked wiki article, so kinda works in \$O(n + m)\$ (but actually needs to sort the polygons first.) Takes in complex numbers for the coordinates.

+&({:@\:p)+,&d(+/\#~[(~:+)@%1&|.)@\:,&(p=.12 o.d=.[-_1&|.)

Try it online!

• d=.[-_1&|. d Translate the polygon to its edges as complex vectors from one point to the next.
• p=.12 o. The vectors polar angles.
• ,&d\:,&p Merge-sort both polygons' edges based on their polar angles.
• +/\ Transform back complex vectors -> points.
• #~[(~:+)@%1&|. but only keep the points where the constructing vector \$B\$ divided by the previous vector \$A\$ has an imaginary part of 0, by checking that the conjugate equals itself. (So \$B = cA\$ for some \$c \notin \mathbb{R} \$.)
• +&({:@\:p) Translate the polygon back from 0j0 to the sum of the starting points.

Answer 2

Jelly, 35 bytes

œ!3ZIZÆḊƲÐḟṢ2ịƊ€
+þẎQḟÇ$µS÷L⁸_æA/¥Þ

Try it online!

man this is ugly

œ!3ZIZÆḊƲÐḟṢ2ịƊ€    Helper Link; get all vertices that lie on an edge
œ!3                 Get all permutations of 3 vertices
   -----ƲÐḟ         Filter; remove triples where
   ZIZ              - the increments (edge vectors)
      ÆḊ            - have a non-zero determinant (keep elements with a 0 determinant; i.e. when they are collinear)
           ---Ɗ€    For each triple
           Ṣ        - sort it
            2ị      - and get the second (middle) item

+þẎQḟÇ$µS÷L⁸_æA/¥Þ  Main Link
+þ                  Product table over sum; get all pairwise sums
  Ẏ                 Tighten / flatten by one level; dump pairwise sums into a flat list of vertices
   Q                Remove duplicates
    ḟÇ$             Filter to remove (result of helper link); basically, delete vertices that lie on an edge between two other vertices
       µ            New monadic chain on the list of vertices
        S÷L         Sum / Length; arithmetic mean but not vectorizing
                 Þ  Sort
           ⁸        The left argument (list of kept vertices)
            ----¥   By order of
            _       - difference with mean point
             æA/    - atan2

Basically, pairwise sum, remove all elements that are the middle element of a collinear triple, and order by atan2 relative to the arithmetic mean of the points.

Answer 3

Ruby, 133 127 bytes

->a,b,*z{a.map{|x|b.map{|y|z|=[x+y]}
z.permutation(3){|i,j,k|q=(j-i)/k-=j;q==q.abs&&z-=[j]}}
z.sort_by{|w|(w*2-z[0]-z[1]).arg}}

Try it online!

Accepts arrays of complex numbers in input. Not really golfed.

The explanation should be straightforward: first get the sum of all the vertices, then remove all the points on the edges and sort by angle relative to the midpoint of the first edge.

Answer 4

Wolfram Language (Mathematica), 239 bytes

({p,q}=(Join[#,#[[;;2]]]&)/@((RotateLeft[#,First@OrderingBy[#,{Last,First}]-1]&)/@#);i = j = 1;res = {};While[i<Length@p-1||j<Length@q-1,AppendTo[res,p[[i]]+q[[j]]];t=Det@{p[[i+1]]-p[[i]],q[[j + 1]]-q[[j]]};If[t>=0,i++];If[t<=0,j++]];res)&

Try it online!

Thanks for the challenge, I have explored an interesting concept!

"Short" answer

Uses this optimized algorithm, accepts list of lists of coordinates, ordered counter-clockwise. Explained:

 ({p, q} =
            (*Must ensure cyclic indexing*)
            (PadRight[#,Length@# +2, #] &) /@ 
            (*Reorder the vertices in such a way that the first vertex of each polygon has the lowest              y-coordinate (in case of several such vertices pick the one   with the smallest x-coordinate*)
((RotateLeft[#,First@OrderingBy[#, {Last, First}] - 1] &) /@ #);
  (*Initialize two pointers and result*)
   i = j = 1; res = {};
   While[i < Length@p - 1 || j < Length@q - 1,
    AppendTo[res, p[[i]] + q[[j]]];
    (*Instead of ATan use cross product*)
    t = Det@{p[[i + 1]] - p[[i]], q[[j + 1]] - q[[j]]};
    If[t >= 0, i++]; If[t <= 0, j++]
     ]; res) &

Long answer (non-convex)

This non-golfed full-named code accepts coordinates (as a ragged list) of any two polygons (may be non-convex). Output a region for to show and list of non-collinear vertices of Minkowski sum:

minkowski[verts_] := With[{polys = Polygon /@ verts},
   (*Decompose the polygons into a disjoint union of convex parts*)
   coords = (PolygonCoordinates /@
        PolygonDecomposition[#, "Convex"]) & /@ polys;
   (*Find Minkowski sum for every convex parts as convex hulls
   and put them together*)
   region = RegionUnion @@ ConvexHullMesh /@ Flatten[
    (Table[Join @@ Outer[Plus, c1, c2, 1], {c1, #1}, {c2, #2}]) & @@
        coords
    , 1];
   (*Select only non-collinear vertices *)
   pickNonColl =
    With[{v = #},
    Pick[v, Function[{k},
        Nor @@ (RegionMember[ConvexHullMesh[#], k] & /@
            Subsets[Complement[v, {k}], {2}])] /@ v]] &;
   {region, pickNonColl@MeshCoordinates@region}
   ];

poly1 = {{-1, -1}, {-2, -4}, {-3, -1}, {-2, -2}};
poly2 = {{1, 1}, {2, 4}, {3, 1}, {2, 2}};
res = minkowski[{poly1, poly2}];
Show[res[[1]], Graphics[Polygon@{poly1, poly2}]]

poly1 = {{-1, 0}, {0, 1}, {1, 0}};
poly2 = {{1, 0}, {0, -1}, {-1, 0}};
res = minkowski[{poly1, poly2}];
res[[2]]

{{-2., 0.}, {-1., -1.}, {-1., 1.}, {1., 1.}, {1., -1.}, {2., 0.}}