Given a (intersecting) polygon, I'd like to cover it with rectangular tiles. I'd like to use as few tiles as possible but enough to be sure that the whole polygon is covered.

Example:

Details:

• Tiles are square, 1 unit wide/high
• The grid begins in (0,0)
• The corners of the polygon can have floating point coordinates (i.e. 3.433, 5.234)
• In general, an edge of the polygon might be as long as 1000 - 10000 tiles

I tried to iterate over all tiles and check whether they are in the polygon, however as I have to iterate over 10000² tiles it takes a quite a long time.

I'm interested in a solution which allows me to quickly answer "Is tile (x,y) covered by the polygon?" without recomputing everything from scratch for each question.

Any solution/approach/pseudo-code/hint which leads me to a correct solution will be accepted.