Minkowski Sum of Convex Polygons

The Minkowski sum P⊕Q contains every vector sum p+q with p∈P and q∈Q. For convex polygons its boundary can be built by merging their edge directions, avoiding all n·m point sums. This is useful for collision geometry and reachable regions. The implementation normalizes both boundary orders and starting vertices, then outputs a strict counterclockwise polygon in linear time.

Prerequisites: Convex polygons; hull boundary conventions; edge-vector angle order.

Build the idea

1. Interpret pairwise addition

   Translate Q by every point of P and take the union; that set is the Minkowski sum. Convexity is preserved because a convex combination of p1+q1 and p2+q2 separates into allowed convex combinations in P and Q. For axis-aligned rectangles, corresponding coordinate ranges simply add, giving an intuitive first example.

2. Normalize before merging

   Inputs are promised simple convex polygons of positive area in cyclic boundary order. Remove consecutive duplicates and an optional repeated closing point, reverse clockwise order using signed area, then remove intermediate collinear boundary vertices. Rotate each polygon to its lowest-y, then lowest-x vertex. This makes its outgoing edge directions cyclically ordered from a common starting sector.

   $$P\oplus Q=\{p+q:p\in P,q\in Q\}$$

3. Merge edge vectors

   Start at p[0]+q[0]. Compare the current edge vectors by cross sign. Advance the polygon with the earlier direction; for equal directions add both and advance both. Adding an edge updates the current output vertex. Once one list ends, append all remaining edges of the other. Do not append the repeated closing position at the end.

4. Explain why edges merge

   For a support direction, the point maximizing dot(direction,p+q) is the sum of independently maximizing points from P and Q. As that direction rotates, a support point changes exactly when one polygon reaches its next edge direction. Thus the sum’s edge sequence is the merged sequence, and equal-direction edges combine. There is no need to enumerate every pair of vertices or sort all their sums.

5. Trace rectangles and limits

   P=[0,2]×[0,1],Q=[0,1]×[0,2] yield [0,3]×[0,3]. Their rightward first edges combine into (3,0), then upward edges into (0,3), followed by opposite directions. The result has four corners. Point/segment-only input requires separate degeneracy rules; this teaching program reports DEGENERATE INPUT for zero-area normalization and assumes convexity instead of repairing an arbitrary polygon with a hull.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
struct Point{
    long long x,y;
    Point operator+(Point p)const{
        return {x+p.x,y+p.y};
    }
    Point operator-(Point p)const{
        return {x-p.x,y-p.y};
    }
    bool operator==(Point p)const{
        return x==p.x&&y==p.y;
    }
};
long long cross(Point a,Point b){
    return a.x*b.y-a.y*b.x;
}
std::vector<Point>normalize(std::vector<Point>p){
    p.erase(std::unique(p.begin(),p.end()),p.end());
    if(p.size()>1&&p.front()==p.back()){
        p.pop_back(); // Optional closing duplicate after deduplication.
    }
    int n=p.size();
    long long twice=0;
    for(int i=0;i<n;++i){
        twice+=cross(p[i],p[(i+1)%n]);
    }
    if(twice<0){
        std::reverse(p.begin(),p.end());
    }
    std::vector<Point>clean;
    for(int i=0;i<n;++i){
        if(cross(p[i]-p[(i+n-1)%n],p[(i+1)%n]-p[i])!=0){
            clean.push_back(p[i]);
        }
    }
    if(clean.size()<3){
        return {}; // Contract requires positive-area convex inputs.
    }
    auto start=std::min_element(clean.begin(),clean.end(),[](Point a,Point b){
        return a.y!=b.y?a.y<b.y:a.x<b.x;
    });
    std::rotate(clean.begin(),start,clean.end());
    return clean;
}
int main(){
    int n,m;
    std::cin>>n>>m;
    std::vector<Point>p(n),q(m);
    for(auto&a:p){
        std::cin>>a.x>>a.y;
    }
    for(auto&a:q){
        std::cin>>a.x>>a.y;
    }
    p=normalize(p);
    q=normalize(q);
    if(p.empty()||q.empty()){
        std::cout<<"DEGENERATE INPUT\n";
        return 0;
    }
    n=p.size();
    m=q.size();
    int i=0,j=0;
    Point current=p[0]+q[0];
    std::vector<Point>result{current};
    // Merge cyclic edge directions; equal directions advance both lists.
    while(i<n||j<m){
        Point a=p[(i+1)%n]-p[i%n],b=q[(j+1)%m]-q[j%m];
        bool takeA=false,takeB=false;
        if(i==n){
            takeB=true;
        }
        else if(j==m){
            takeA=true;
        }
        else{
            long long turn=cross(a,b);
            takeA=turn>=0;
            takeB=turn<=0;
        }
        if(takeA){
            current=current+a;
            ++i;
        }
        if(takeB){
            current=current+b;
            ++j;
        }
        if(i<n||j<m){
            result.push_back(current); // Omit repeated closing vertex.
        }
    }
    std::cout<<result.size()<<'\n';
    for(Point a:result){
        std::cout<<a.x<<' '<<a.y<<'\n';
    }
}

Complexity analysis

O(n+m) normalization and merge time for already cyclic convex boundaries, O(n+m) storage including output. Each edge advances once. This claim excludes any extra hull construction needed for unordered points. Sum coordinates are within ±2·10^6 and determinant/sum bounds still fit long long.

Example input and output

Read n m (3..100000 each), then n vertices of P and m of Q. Both are promised simple convex positive-area integer polygons, coordinates within ±10^6; either orientation, redundant consecutive/closing duplicates and collinear edge points are allowed. Print result size and CCW vertices starting at lowest y/x.

Input

4 4
0 0
2 0
2 1
0 1
0 0
1 0
1 2
0 2

Output

4
0 0
3 0
3 3
0 3

Adding the x-ranges gives [0,3], and adding the y-ranges also gives [0,3]. Equal edge directions merge.

Practical applications

Use for configuration-space obstacles and sums of reachable positions. Collision of translated shapes relates to whether a translation lies in P⊕(−Q), with the appropriate reflection, not blindly P⊕Q. Distances between convex polygons can also be studied via their Minkowski difference.

Check your understanding

What happens when the current edge directions are equal?

Put it into practice

Compare with the convex hull of every vertex sum for small random convex polygons.