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

Question

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.

Answer 1

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:

• split the polygon into its convex parts

• draw each polygon's outline (more precise: each convex part's outline) with Bresenham's line algorithm

• fill the holes (which should be easy since you are working with convex polygons)

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