Vector sums of convex polygons
Given two convex polygons P and Q on the plane, the vector sum of P and Q, denoted P + Q is defined as follows:
P+Q={p+q} for all p and q belonging to P and Q respectively.
The vector sums of polygons, also referred to as the Minkowski sum is used in motion planning.
Considering the definition above, many questions can be asked about the nature of the set P+Q, the properties it holds, etc. The following result help characterize vector sums of polygons:
- P+Q is a convex polygon.
- The vertices of P+Q are sums of vertices of P and Q
- The vertices of P+Q are sums of co-podal pairs between P and Q.
- Given that P and Q have m and n vertices each, P+Q has no more than m+n vertices.
Finally, the following result not only characterizes the problem, but provides a way of incrementally computing the vector sum of two convex polygons, vertex by vertex:
Given the k-th vertex z(k) of P+Q, with z(k) = p(i) + q(j). Construct two parallel lines of support at p(i) and q(j) such that the polygons lie to the right of their respective lines. The lines determine angles theta(i) and phi(j) at p(i) and q(j) respectively (see the illustration below)
Then the next vertex z(k+1) equals:
- p(i+1) + q(j) if theta(i) < phi(j)
- p(i) + q(j+1) if theta(i) > phi(j)
- p(i+1) + q(j+1) if theta(i) = phi(j)
Consider as an example, the following polygons, and their vector sum (below).
Two convex polygons. The first polygon's edges are in red, the second's in blue.
The vector sum of the above polygons. Its edges' colours correspond to the originating polygon's.
Using the last result, it is very easy to formulate an algorithm computing the vector sun. The first vertex can be the sum of the extreme vertices in a given direction (say the negative y direction). Lines of support are constructed, and upon computation of the angles, the next point is clear. All that is needed is to rotate the lines simultaneously to the new position, to determine the new angles.
The algorithm's correctness follows from the main result; it has linear time complexity, from the fact that at each step one vertex for the vector sum is output, and since there are at most m+n of these, the total running time is m+n.
December 17th, 1998