9
\$\begingroup\$

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.

enter image description here

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 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)]
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

J, 74 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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.