# Given a rhombus (square) shaped grid, find which cell a point is in

Sorry for this simple question but I can't find a way to solve it in a simple way. I've found "point location" solutions, but there must be a much simpler way to do this, given that it's a regular grid and not arbitrary polygons.

As seen in the attached picture, I have a rhombus shaped grid. They have 90 degree angles, so they're squares, but I think the word rhombus is more appropriate here because everyone assumes something else when thinking of a square grid. The diagonal of a rhombus can be of any size (although if it makes the solution simpler (unlikely), my diagonals are always an even number). In this picture it's 6.

The center of a rhombus cell is indicated by a green square.

Given a random point on the graph, I need to get the coordinates of the center of the rhombus cell that the point is in. If the point is on the edge of 2 cells, it can favor either of them. 1 http://puu.sh/7Ej6V.png

• Rotate 45 degrees; then it's easy. – bubba Mar 21 '14 at 22:53
• Rotate the point 45 degrees, get the cell in a square grid, then rotate the center of the cell back 45 degrees? Thanks, it was indeed simple. – Wa. Mar 21 '14 at 23:08

Let $L$ be the "diagonal" width of a rhombus, by which I mean the distance between its two opposite corners. Note that by replacing $x$ with $\frac{x+y}{\sqrt{2}}$ and replacing $y$ with $\frac{x-y}{\sqrt{2}}$ we rotate everything by $45$ degrees around the origin.

Thus, given a point $a,b$, set

$$a' = \frac{a+b}{\sqrt{2}}, b' = \frac{a-b}{\sqrt{2}}.$$

This is like rotating 45 degrees around the origin. Then we want to align the square grid with the normal unit grid (I'm assuming the origin was in the center of one of the rhombuses), so we set

$$a'' = \frac{a' + \frac{L}{2}}{L}, b'' = \frac{b + \frac{L}{2}}{L}$$

Now we round down to the nearest integer to move each point to the bottom left of its square, and shift it by $\frac{1}{2}$ to move it to the center of that square:

$$a''' = \lfloor a''\rfloor + \frac{1}{2}, b''' = \lfloor b''\rfloor + \frac{1}{2}$$

Finally, we can transform these back to our rotated grid by multiplying by $L$ and rotating backwards:

$$a'''' = \frac{\sqrt{2}\left(La''' + Lb'''\right)}{2}, b'''' = \frac{\sqrt{2}\left(La''' - Lb'''\right)}{2}$$

Note that here we're just saying we want $La''' = \frac{a'''' + b''''}{\sqrt{2}}$ and $Lb''' = \frac{a'''' - b''''}{\sqrt{2}}$ and solving for $a''''$ and $b''''$, which will be the center of the rhombus you want.

The diagonal lines have equations $x+y = r + 2ar$ or $x-y= r + 2br$, where $r$ is half the length of the diagonal. Let $a = \left \lfloor \frac{x+y - r}{2r}\right\rfloor$ and $b = \left \lfloor \frac{x-y - r}{2r}\right\rfloor$. Then the point lies in the rhombus with center $\left((a+b+2)r, (a-b)r\right)$.