Your question implicitly triggers another, even more important vector mapping related question, namely - is it necessary to pre-create the inner/trivial tiles of a polygon/area or those can be regenerated on the fly. I will try to answer both but on a generalized algorithmic level.

I assume we have a common understanding of tiles, a tiled coordinate space, of tile referencing, when a point belongs to a tile (inside or on the left or top edge), a tile coverage ... and a like. Further, you have some basic and effective functions like: pointTOpolygon(...) that checks the relation of a given point to a given polygon (on, inside, outside); pointTOline(...) that checks the relation of a point to a (straight) line (on, one-side, other-side) ... and a like. So, the major algorithm steps are:

1. Find the tile coverage/matrix of the polygon's bounding box (detect the tiles containing three corners of the box the rest of the coverage is then predefined). All the other tiles are of no interest further.

2. For any edge-vectors of the polygon detect the tile candidates that might have common points with the edge. The candidates are quickly detectable (early filtering). They are never under, over, left or right to the vector.

3. For any tile candidates check whether it has a common point with the edge-vector. If any two corner points are on the different sides of the line defined by the edge, or the edge is horizontal and has common points with the top tile-edge (excluding the top-right corner), or the polygon edge is vertical and has common points with the left tile edge (excluding the bottom-left corner) then mark the tile candidate as a member of the polygon tile coverage.

Note that the tile coverage (the set of the marked tiles) is still organized in a row/column structure. In any of the tile rows the consecutive marked tiles are forming tile-runs. Any of the rows must have at least one run. If more runs exist they are separated by empty/unmarked tiles. Let us denote the runs R1, R2 ... Rn from the left to right in a tile row. Now, if you want the inner/trivial tiles (if any), the next procedure might be used to detect them:

4. In any tile rows, where the number of runs is n>1, start with the first pair of runs (Rf,Rs) from the left. Select a point P (example gratia, the central point) of the first empty/unmarked tile just to the right from Rf. If P is inside the polygon, then all the tiles between Rf and Rs are inner/trivial tiles (you may mark them). Reset n-=2 and if n>1 take the pair to the right from Rs as (Rf,Rs). If P is not inside the polygon then all the tiles between Rf and Rs are outside the polygon and may be just ignored. In this case reset n-=1 and if n>1 take the pair to the right of Rs as (Rf,Rs). Finally, if n>1 just repeat the procedure from selecting the point P.

Now, in this way you have all the none trivial tiles covering the polygon (area borders) and the trivial tiles that are inside the polygon (area).

answered
**07 Feb '15, 01:33**

sanser

695●38●39●55

accept rate:
5%

Your question is not quite clear, do you want to

count how many tiles are needed to cover the polygon

get a list of the tile g the numbers covering the polygon

get, as a variant of the above, the tiles just for the polygon outline or do you need them for the area