intersection test for convex polygon (variant of SAT)

convex_polygon_intersection.cc

#include <iostream>
#include <vector>

#include <Eigen/Dense>

using namespace std;
using Point2 = Eigen::Vector2d;
using Polygon = vector<Point2>;

Point2 EdgeNormal(const Point2& p1, const Point2& p2) {
  return {-p2.y() + p1.y(), p2.x() - p1.x()};
}

bool IsOnNegativeSide(const Point2& point, const Point2& normal, const Polygon& poly) {
  for(const auto& test_p : poly) {
    if(
      (test_p - point).dot(normal) > 0.0
    ) {
      return false;
    }
  }
  
  return true;
}

bool IntersectImpl(const Polygon& axis_generating_poly, const Polygon& test_poly) {
  for(size_t ii = 0; ii < axis_generating_poly.size(); ++ii) {
    const Point2 normal = EdgeNormal(axis_generating_poly[ii], axis_generating_poly[(ii+1) % axis_generating_poly.size()]);
    
    if(IsOnNegativeSide(axis_generating_poly[ii], normal, test_poly)) { return false; }
  }
  
  return true;
}

bool Intersect(const Polygon& poly1, const Polygon& poly2) {
  return IntersectImpl(poly1, poly2) && IntersectImpl(poly2, poly1);
}


int main() {
  Polygon p1{
    {0.0, 0.0},
    {1.0, 0.0},
    {1.0, 1.0},
    {0.0, 1.0},
  };
  
  Polygon p2{
    {2.0, 0.0},
    {3.0, 0.0},
    {3.0, 1.0},
  };
  
  cout << Intersect(p1, p2) << endl;
  
  Polygon p3{
    {0.5, 0.0},
    {1.0, 0.5},
    {0.0, 1.0},
  };
  
  cout << Intersect(p1, p3) << endl;
  cout << Intersect(p2, p3) << endl;
}