title: fast calculation of the intersection area of a triangle and the unit square
body: <p>In my current project I need to calculate the intersection area of triangles and the unit squares in an infinite grid.</p>
  
  <p><img src="https://i.stack.imgur.com/HpK8N.png" alt="enter image description here"></p>
  
  <p>For every triangle (given by three pairs of floating point numbers) I need to know the area (in the interval <code>(0,1]</code>) it has in common with every square it intersects.</p>
  
  <p>Right now I convert both (the triangle and the square) to polygons and use <a href="http://rosettacode.org/wiki/Sutherland-Hodgman_polygon_clipping" rel="nofollow noreferrer">Sutherland-Hodgman polygon clipping</a> to calculate the intersection polygon, which I then use to <a href="http://neonstorm242.blogspot.de/2010/12/area-of-simple-polygon.html" rel="nofollow noreferrer">calculate its area</a>.</p>
  
  <p>This approach now shows to be a performance bottleneck in my application. I guess a more specialized (analytical) algorithm would be much faster. Is there a standard solution for this problem, or do you have any idea? I only need the areas, not the shape of the intersections.</p>