PHP: What's the mathematically efficient way to find a 'subgrid' of a larger grid?

Question

Hi,

i'm trying to find an efficient way to find a subportion of a large grid. Currently I'm looping through rows to define a FROM-TO selection of ids in that row, but this doesn't feel right...

Let's say I have a grid of 200x200 fields (x between 1 and 200, y between 1 and 200). Every field also has it's unique ID, starting at X1,Y1 (fieldid = 1) to X200,Y200 (fieldid = 40000).

I have a subportion of the grid that I need to select from the database (based on XY-ranges or unique id's, where uniqueids are much faster so preferred). The subportion is defined by the upperleft field (again based on XY value or a unique id) and then 16 fields wide and 9 fields high.

So, how can I efficiently select a subgrid of 144 fields (16x9) of a large grid of 40000 fields (200x200) based on the unique-id or XY-value of the upperleft field in the 16x9 subgrid?

Answer 1

Not too sure if I understand the problem you are trying to overcome, some context would probably help... anyway, here goes...

x1 -> x2 = 16 spaces y1 -> y2 = 9 spaces

x1*y1 = start ID

x2*y2 = end ID

you will have nine ranges (where 'a' is the valid range):

x1*y1 < a < (x1*y1)+16
x1*(y1+1) < a < (x1*(y1+1))+16
x1*(y1+2) < a < (x1*(y1+2))+16
....
x1*(y1+8) < a < (x1*(y1+8))+16

Answer 2

I have found that the geometry extension in MySQL is pretty well optimized. So the most efficient way would be to add a column of type POINT to your table holding the position in the matrix.

ALTER TABLE YourTable ADD COLUMN pos POINT NOT NULL;

Then you can select using the extension's functions (Example for selecting 16x9 area starting at coordinates 10/10):

SET @polygon = GeomFromText('Polygon((10 10, 26 10, 26 19, 10 19, 10 10))');
SELECT * FROM YourTable WHERE MBRContains(@polygon, pos);