Cartesian to Quadcode Conversion

The process of converting between Cartesian and quadcode representations is surprisingly simple, thanks to the conversion algorithm devised by Gargantini. Consider the quadcode 23 in Figure 2. It is located in row 3, column 1 (using zero-based row and column numbers). The row and column numbers, in binary, are:

I = 11
J = 01

If the individual bits are named, with bit 0 the least-significant one, we have:

I0 = 1, I1 = 1, J0 = 1, J1 = 0

Next these two binary numbers are combined by alternately taking bits from the I and J coordinates. Specifically, we will use the bits in this order:

I1, J1, I0, J0

where I have shown them in left-to-right order. The result is:

Q = 1011

This is actually the binary representation of the quadcode 23! The two highest-order bits (10) are the 2, and the lowest-order bits (11) are the 3.

To use a little more complicated example, consider the quadcode A in Figure 3, which has a value of 213 and has (I,J) coordinates of (5,3). Expressed in binary, the coordinates are:

I = 101
J = 011

which corresponds to:

I0 = 1, I1 = 0, I2 = 1, J0 = 1, J1 = 1, J2 = 0

Now combine these two sets of bits in order

I2, J2, I1, J1, I0, J0

to get:

Q = 100111

By considering each group of two bits to be one quit, the result is 2 (10), 1 (01), and 3 (11).

Actually, since I have chosen to zero-pad any extra bits in the byte, the actual storage would be:

Q = 10011100

This makes it very easy to compare one quadcode to another for purposes of ordering. QuadCode::Compare does this by comparing each byte of two quadcodes, starting with the first and working left-to-right.