title: Algorithm: Cutting Polygon by grid
body: <p>I have a polygon which is located in a 2D grid:<br>
  (lets assume I'm able to paint a grid where the distances between each line is the same)</p>
  
  <p><img src="https://i.stack.imgur.com/NuFbC.png" alt="enter image description here"></p>
  
  <p>I'm now searching for an algorithm or some sort of implementation which could cut the polygon into several smaller polygons along the grid.</p>
  
  <p>Some example code in C++ which basically shows what I want to do:</p>
  
  <pre><code>struct Point2D
  {
      double x;
      double y;
  }
  
  struct Polygon
  {
      std::vector&lt;Point2D&gt; points;
  }
  
  /**
   * givenPolygon is the 'big' polygon which should be divided
   * gridSize is the distance between the gridlines
   * return value is a vector of the resulting subpolygons
   */
  std::vector&lt;Polygon&gt; getSubpolygons( Polygon givenPolygon, double gridSize )
  {
      Code here...
  }
  </code></pre>
  
  <p>Are there any algorithms or implemented libraries which could do that?</p>