Finding cells in a grid with varying grid cell sizes

Question

I have a grid of rectangular cells covering a plane sitting at some distance from the coordinate system origin and would like to identify the grid cell where a straight line starting at the origin would intersect it.

The cells on the grid have equal sizes (dx,dy) and there are no gaps between cells, but since every cell on the plane has a different distance from the origin, the solid angle they cover is not constant -- if it was I could find a simple function that translates a direction (theta,phi) into a cell index (ix,iy).

Currently I use something like a nearest-neighbor search to find cells, but this doesn't exploit the "gridded-ness" of my cells at all. Is there any algorithm that would help me improve on this?

EDIT I know I could just use simple trigonometry to get the cell, but I am more interested in what algorithms there are that do nearest-neighbor searches on regularly spaced inputs.

Answer 1

[...]but I am more interested in what algorithms there are that do nearest-neighbor searches on regularly spaced inputs.

Though they are data structures to be very specific, I think you should take a look at the following:

• R Tree
• BK Tree

Answer 2

But there won't be a unique cell that will be intersected. Do you mean exactly the center of the cell, perhaps?

In general, in the first quadrant (i.e. x>0, y>0) if you have a cell that fills the rectangle (x,y) -> (x+1,y+1), then any line with angles between atan2(y+1,x) and atan2(x,y+1) will intersect at least part of the cell.

Anyway, if you want to do general nearest-neighbor searches, you should divide your data into a quad-tree. It's one of the workhorses of nearest-neighbor calculations in 2D. You can also do multiscale grids if your data is sparse (which is really just a special case of a quad-tree with a particularly regular subdivision pattern, but that gives you constant-time lookup instead of log(N)).