geometry/minkowski.cpp

• View this file on GitHub
• Last update: 2025-03-21 23:27:46+08:00
• Link: https://cp-algorithms.com/geometry/minkowski.html#implementation

Code

//source: https://cp-algorithms.com/geometry/minkowski.html#implementation

template<class pt>
void reorder_polygon(vector<pt> & P){
  size_t pos = 0;
  for(size_t i = 1; i < P.size(); i++){
    if(P[i].y < P[pos].y || (P[i].y == P[pos].y && P[i].x < P[pos].x))
      pos = i;
  }
  rotate(P.begin(), P.begin() + pos, P.end());
}

template<class pt>
vector<pt> minkowski(vector<pt> P, vector<pt> Q){
  reorder_polygon(P);
  reorder_polygon(Q);
  P.push_back(P[0]);
  P.push_back(P[1]);
  Q.push_back(Q[0]);
  Q.push_back(Q[1]);
  vector<pt> result;
  size_t i = 0, j = 0;
  while(i < P.size() - 2 || j < Q.size() - 2){
    result.push_back(P[i] + Q[j]);
    auto cross = (P[i + 1] - P[i]).cross(Q[j + 1] - Q[j]);
    if(cross >= 0 && i < P.size() - 2)
      ++i;
    if(cross <= 0 && j < Q.size() - 2)
      ++j;
  }
  return result;
}

#line 1 "geometry/minkowski.cpp"
//source: https://cp-algorithms.com/geometry/minkowski.html#implementation

template<class pt>
void reorder_polygon(vector<pt> & P){
  size_t pos = 0;
  for(size_t i = 1; i < P.size(); i++){
    if(P[i].y < P[pos].y || (P[i].y == P[pos].y && P[i].x < P[pos].x))
      pos = i;
  }
  rotate(P.begin(), P.begin() + pos, P.end());
}

template<class pt>
vector<pt> minkowski(vector<pt> P, vector<pt> Q){
  reorder_polygon(P);
  reorder_polygon(Q);
  P.push_back(P[0]);
  P.push_back(P[1]);
  Q.push_back(Q[0]);
  Q.push_back(Q[1]);
  vector<pt> result;
  size_t i = 0, j = 0;
  while(i < P.size() - 2 || j < Q.size() - 2){
    result.push_back(P[i] + Q[j]);
    auto cross = (P[i + 1] - P[i]).cross(Q[j + 1] - Q[j]);
    if(cross >= 0 && i < P.size() - 2)
      ++i;
    if(cross <= 0 && j < Q.size() - 2)
      ++j;
  }
  return result;
}

Back to top page