Given a (intersecting) polygon, I'd like find out which tiles are being covered by the polygon.
- 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.