How many squares does my rectangle touch in 2d square grid?
Clash Royale CLAN TAG#URR8PPP
How many squares does my rectangle touch in 2d square grid?
I've encountered the following riddle:
How many squares in my 2d square grid does a given rectangle placed randomly touch?
Notice that the rectangle can be of course rotated, which complicates stuff.
Example - it touches 4x6 = 24 squares, however if I rotate it will touch more:
My efforts were:
Go over each square and for each rib see if it intersects the original square. I've seen a pretty elegant way to see if two sections of a line intersect, but still I think it is a little bit ugly.
A better approach would be find points that are near the original a,b,c,d points and go over them until we get a point that is not in the rectangle. There is an elegant solution to find if a point is contained in a rectangle.
However here there are a lot of edge cases I'm not sure how to handle.
To get a help, you would better to show own efforts.
– MBo
Aug 5 at 14:38
I'm sorry, Now I've shown my efforts. Hope it is enough
– The Capacitor
Aug 5 at 17:35
I do believe you should rephrase the question and add the word Max: How many squares in my 2d square grid does a given rectangle, placed randomly, maximal touch? I would say (ceiling(Width) + 1) * ceiling(Height) + 1). I do believe rotating does not have an impact because what you loose on the bottom of the triangle you gain on the top.
– Aldert
Aug 5 at 17:37
Gassa is having same issue as I am having: clear problem statement would be appriciated (I am facinated by the problem).
– Aldert
Aug 5 at 17:43
2 Answers
2
When rectangle is rotated, counting touched cells might be rather complex problem. But you can use a kind of rasterization to get all touched cells.
Sort vertices by Y. Get top vertex. Go through two incident edges in parallel, counting cells in every scanline (the leftmost cell for left edge, the rightmost cell for right edge) until the next vertex is met. Continue with corresponding edges again.
Note that you cannot use line-drawing algorithms like Bresenham directly because they are not intended to detect all touched cells (while they might be modified).
Here is article of Amanatides and Woo "A Fast Voxel Traversal Algorithm for Ray Tracing" for 2D. Practical implementation.
Example:
Looking for a practical solution, I would go with the following:
1. Draw a rectangle (r2) around the (rotated) rectangle (R1). The squares, R1 touches, is r2 minus all squares left.
2a. Start at the bottom left corner and move one square at the time to the right until you reach c1
2b. For each square, calculate the full squares, move up until you touch R1.
(that is 4 + 3 + 2 + 1)
3a. Start at the bottom right corner and move one square at the time to the left until you reach c1.
3b. For each square, calculate the full squares, move up until you touch R1.
(3 + 2 + 1)
4 repeat for top
(2 + 1) + (4 + 3 + 2 + 1)
R1 takes = r2 - squares counted above = (8 * 8) - (10 + 6 + 3 + 10) = 35
I sort of did something similar, however it takes a really long time to run algorithms like this because you have to scan on all the options you can put the rectangle in the grid.
– The Capacitor
Aug 19 at 4:46
OK, I thought you where looking for an answer based on a placed rectancle, I think you have changed your text a bit from original. Still, I like the riddle, will continue to find a mathematical answer for max of squares.
– Aldert
Aug 19 at 5:50
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
I mean you can rotate it
– The Capacitor
Aug 5 at 13:53