text: Q:
  
  Filling a polygon with maximum number of grid squares
  
  I've got a 2d polygon.
  
  I'm placing it on a square grid and marking the squares that are completely inside the shape.
  
  I need to find the placement that maximizes number of marked squares. The polygon orientation is fixed, it can be only translated.
  
  How can I do so?
  
  A:
  
  Let's solve the problem for the case if we can only move our polygon P to the right and the width of the cell equals w.
  First of all, notice that it is enough to explore shifts for the distance dP in [0; w), because if we move P to w to the right we get the same situation as if we didn't move it at all.
  Let SP to be an amount of cells currently in P. Suppose we moved P for a little. What could happen? Well, some of the vertices of the grid now could be out of P (let's call this set O), and some new vertices could be now in P (set I). How to determine if we lost or acquired any cells? If a cell was in P and had corner, which is in O, then we should decrease SP. If, on the contrary, a cell has corners in I and other corners are already in P, then we should increase SP.
  Let's now sort these events (acquiring and losing of vertices) by increasing it's distances from the initial position of P. Thus we formalized the order of our "little steps" in algorithm.
  Now we can write some pseudocode:
  def signedDistance(vertex, edge):
      p = [ closest point of edge to vertex ]
      return vertex.x - p.x
  
  Events = { (vertex, edge) : 0 <= signedDistance(vertex, edge) < w }
  sort(Events, [ by increasing signedDistance ])
  EventsEquiv = { E' : E' is subset of Events and
                      for any a, b from E'
                      signedDistance(a.vertex, a.edge) = signedDistance(b.vertex, b.edge) }
  S = [ cells in P initially ]
  maxS = S
  for E' in EventsEquiv:
      for e in E':
          if e is loss: S -= 1
          else if e is acquirement: S += 1
      if S > maxS:
          maxS = S
  
  The method is close to the sweep line.
  UPD: To generalize this we need to notice that for any optimal position of P exists another optimal position that P has a grid vertex on an edge. So the solution is to fix some grid vertex G and move P "around" it so P always has G on an edge step by step, where steps are produced by the events occuring, which were described above. Algorithm takes O(|P| / w).
  
  