1

Given a grid inclined at an angle θ (theta) with equal sized square-shaped cells with indices 00, 01, 02, ..., 55 (where first digit being x index and second being y index, for instance 00 means a cell at the intersection of row 0 and column 0), and a point p(x,y), how can we know that in which grid cell does the point lie without checking all the cells?

For instance, in the image below point p lies in the cell with index 23.

enter image description here

I found one answer at Checking if a point is inside a rotated rectangle that explains how to determine if a point lies inside a rotated rectangle, but with this approach I need to check all the grid cells.

shaikh
  • 582
  • 6
  • 24

1 Answers1

2

Perhaps the simplest way - rotate point by the same angle (with negative sign) and check new coordinates in axis-aligned grid

nx = x * cos(theta) - y * sin(theta)
ny = x * sin(theta) + y * cos(theta)
row = (int) (ny / cellsize)
col = (int) (nx / cellsize)
MBo
  • 77,366
  • 5
  • 53
  • 86
  • I think I am not getting the right results. Consider p(5,1), θ = 45 degrees and cellsize = 1. I am getting row = -3 and col = 3. – shaikh Aug 04 '20 at 10:04
  • OK, I made sign change to use the same theta direction as for grid. Now row=2, col=4 – MBo Aug 04 '20 at 11:02
  • That's great. It works. Can you explain what is happening in the above statements? – shaikh Aug 04 '20 at 11:54
  • 1
    Here we apply [rotation matrix](https://en.wikipedia.org/wiki/Rotation_matrix) to find position of point after rotation around coordinate origin – MBo Aug 04 '20 at 15:57
  • Its working, but I don' understand why its working? The rotation matrix (https://en.wikipedia.org/wiki/Rotation_matrix) is for anticlockwise rotation with respect to x-axis, whereas in my case rotation is clockwise with respect to y-axis. Yet it seems to work. What could be the reason? – shaikh Aug 05 '20 at 07:08
  • 1
    We want to see point position in unrotated grid. To achieve this, we have to rotate in another direction. Your grid essentially is rotated by negative angle in usual mathematical coordinate system (where CCW is positive, CW is negative), so we make formula with positive theta value for point. – MBo Aug 05 '20 at 07:17
  • Thanks for you help. One thing more, the solution seems to work for angles less than 90. For angles >= 90, it doesn't work. – shaikh Aug 05 '20 at 08:26
  • 1
    Let angle = 135, x=0, y=-3, so nx= - (-3*0.7)=2.1 ny = -3*(-0.7)=2.1. Cell 2,2, as expected – MBo Aug 05 '20 at 08:38
  • Yes, its correct. Sorry I was mistaken about grid coordinates after its rotation. Thank you very much :) – shaikh Aug 05 '20 at 10:31