Calculate positions occupied by a polygon after rotation in a grid

Question

I looked for some similar questions, but I think that no one of them are related to my problem.

I am coding in C++ the translation and rotation of a simple polygon (i.e a rectangle, a polygon like a L shape, ...) in a grid cell of 10x10.

Let's say that I have a rectangle of width = 1 cell and height = 3 cells. Translate it in the 8 directions is easy. But if I want to rotate this polygon 45º, I can get it, but I want to calculate which are the cells that are now occupied or partially occupied by the rectangle.

I have the center of mass of the rectangle, that is a cell of it. I can calculate the positions occupied by the rectangle before the rotation depending on the size. But, after the rotation, I cannot find the way to calculate the cell positions occupied by the rectangle.

Thank you very much!

Answer 1

You can definitely treat this like a bounding box problem -

Take the four corners of your rectangle with x,y coordinate of these corners being the cell numbers they occupy - for e.g. for the rectangle of width = 1 cell and height = 3 cells centered at o(2,2) these 4 corners represented in corner(x,y) format would be - a(1.5,3.5) b(2.5,3.5) c(2.5,0.5) d(1.5,0.5).

Once this is clear, i think the remaining procedure you might have already understood as it has been explained before a number of times like here -

Calculate Bounding box coordinates from a rotated rectangle

To summarize, apply the standard matrix for 2D rotation to these 4 corners and get the new corners for e.g.

a'.x = o.x + (a.x - o.x) * cos(t) + (a.y - o.y) * sin(t) 
a'.y = o.y - (a.x - o.x) * sin(t) + (a.y - o.y) * cos(t) 

and similarly for the other points. Then find the max and min x and y and they will represent the cells occupied by your rectangle. Similar stuff can be done for other convex polygon.

UPDATE: As commented by Fang, to get the accurate number of cells occupied by the rotated polygon you would still need to do the square to polygon intersection check for all the square cells within the bounding box- you can take a look at this -

How to check intersection between 2 rotated rectangles?

Answer 2

Here is what I would do:

1) Get the vertices of the original polygon. Since your polygon is composed of connected grid cells, I supposed the coordinates of these vertices will all be integers.

2) Rotate the polygon vertices. I supposed you know how to do this as you know how to rotate the polygon.

3) To detect if a given cell is still occupied by the rotated polygon, check if the cell has any intersection with the rotated polygon. So, this is basically a square-to-polygon intersection check. When there is no intersection at all or the intersection is an edge or a vertex, you can conclude that this cell is not occupied by the rotated polygon.

4) Do step 3 for all the cells.

In step 4, instead of looping thru all cells, you can actually use the bounding box of the rotated polygon to easily exclude some cells from the square-to-polygon intersection check. But if you only have 10x10 cells, you probably can get away without it without seeing any performance difference.