Regular Grids

Description

In the regular grids decomposition method, the pattern to place on top of our object is a regular grid. Assuming that the x and y coordinates are merged into a single ‘composite’ number, this could be used as the key for a hashed index or be translated directly into a relative record address of a direct access file.

The choice of the cell size is an important issue when defining the manner to discretize the continuous domain of interest into a regular scheme grid. The content of each cell is stored in one or more records of a file. To avoid wasted space within the record, it is useful to match the quantity of data in the cells to the size of the record or vice versa.

An example

We consider a grid extend from 0 to 100 units in each direction and each cell of 10 units square.

Grid 100x100 units

The key K for a cell A with coordinates:

x = 70
y = 50

could be: K=75

Note that the last digit of each value is redundant since cells are 10 units apart.

To retrieve data from a rectangular spatial window (B), it is only necessary to derive the address of all cells covering the window.
For the window:

x_min=15 x_max=37
y_min=20 y_max=45

The corresponding range of cell addresses would be all those keys whose x components lay between 10 and 30 and whose y components were between 20 and 40 (inclusive), the most south-westerly key being the corresponding range of cell addresses would be all those keys whose x components lay between 10 and 30 and whose y components were between 20 and 40 (inclusive), the most south-westerly key being K=12.