Date: 2006 November

Imagine a rectangular region which is placed quite arbitrarily inside a rectangular grid. It is questioned which gridpoints are inside this rectangular region.

A picture says more than a thousand words:

When rounding the floating point values of the transformed interior points to integer values, memory locations may be obtained, in principle.

Such a method is commonly called
**hashing**.

It can be demonstrated (: make a drawing) that at most two collisions can happen when rounding these (x,y) coordinates: just try to bring two grid points together in one grid cell. You will see that they can only fit in if their mutual distance is smaller than √2, the diagonal of the cell:

But two different grid points can oly give rise to the same round off values - giving the midpoint of the grid cell - if they fit into the same grid cell. The big trick is now that all lengths may be multiplied with this factor √2 (preferrably even somewhat larger for safety):

It is clear that all collisions have disappeared then: it's impossible to
bring two grid points with mutual distance greater than √2 together
into one 1x1 grid cell and round them to the same midpoint. With other words:
we have a **perfect hash** (though maybe it doesn't look like it, not yet):

But if these values are rounded . . . Look ! Here we are:

Therefore what we need is a table which is √2 times √2 = twice as big as the minimal size which would be needed for storing all grid point values "without gaps". The advantage of the overhead by a factor 2 is that an adress is attached to a grid point immediately, without any need for re-hashing (due to a collision) or searching.

The procedure is as follows. Traverse all adresses in our twice-too-big table; and apply the inverse of all transformations in reverse order. Inverse rounding in the first place, corresponding to plus or minus 1/2 with both coordinates, resulting in a little square with four vertices. Then dividing all coordinates by √2 instead of a multiply. Rotate over minus the angle, perform a translation backwards. The end-result of this (floating point) procedure is the little square with, yes or no, a grid point in it. Iff the grid point is within that little square, then it can be found by rounding the coordinates of the center of the square.

This center corresponds with the end-result by rounding, in the Forward Hash procedure. Rounding the center gives whole-number coordinates, hence a possible grid point. Next check if the candidate grid point is within that little square as well. (This is not necessarily true: approximately half of the grid points will be outside and approximately half of the grid points will be inside the little square.) At last check if the candidate grid point is within the large skew rectangle we started with. In this manner, the Inverse Hashing procedure enables us to find all grid points corresponding to adresses which can be filled with Forward Hashing.

My English may be better than your Dutch.