# How to find out if a tile is being covered by a polygon?

Given a (intersecting) polygon, I'd like find out which tiles are being covered by the polygon.

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.

• Shrink wrap it, perhaps a modified cs.sfu.ca/~haoz/teaching/projects/cmpt469/0501/shrink_wrap/… that pays attention to the grid size you've chosen? May 15, 2014 at 6:48
• Your question is unclear. Is the size of your tiles fixed? Is the orientation and position of the grid given, or is it arbitrary? Please clarify. May 15, 2014 at 6:50
• Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask
– gnat
May 15, 2014 at 6:59
• @DocBrown: I'd like to apologize for my unclear question. I added some further details, please let me know when something remains unclear...
– Ted
May 15, 2014 at 15:18
• @gnat Unfortunately, I couldn't find a solution better than just iterating over all tiles.
– Ted
May 15, 2014 at 15:20

It seems that you want to do polygon rasterization, where your "pixels" are your grid elements.

An approach I would try (as chances are you will find ready-to-use algorithms to do that), is to use an in-memory rasterizer (e.g. Cairo), adjusting the filtering (and of course the coordinates of your polygons so they are expressed in grid units).

You could alternatively roll your own using existing algorithms. For instance:

For step 2, if you want to cover all pixels, see this SO question.

• +1, I think especially if the raster resolution is high compared to the polygon size this approach will work much better than my suggestion. May 15, 2014 at 11:46
• Thank you for your suggestion, is there an easy way to avoid that tiles crossed near a corner are not being painted? E.g. in en.wikipedia.org/wiki/File:Bresenham.svg 4 pixels are white even though the line crosses the pixels.
– Ted
May 15, 2014 at 15:42
• Look up simplices and simplicial complexes and Voronoi diagrams and their duals. May 16, 2014 at 4:25
• The coverage problem was solved on SO - I edited the question to include the link.
– user44761
May 16, 2014 at 17:20