2

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

Example:

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? – Patrick Hughes May 15 '14 at 6:48
  • 1
    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. – Doc Brown May 15 '14 at 6:50
  • 1
    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 '14 at 6:59
  • 1
    @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 '14 at 15:18
  • @gnat Unfortunately, I couldn't find a solution better than just iterating over all tiles. – Ted May 15 '14 at 15:20
2

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. – Doc Brown May 15 '14 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 '14 at 15:42
  • Look up simplices and simplicial complexes and Voronoi diagrams and their duals. – daaxix May 16 '14 at 4:25
  • The coverage problem was solved on SO - I edited the question to include the link. – Tibo May 16 '14 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.