Seeking the algorithm to generate this table of numbers [duplicate]

Question

I need to know how to calculate the positions of the QR Code alignment patterns as defined in the table of ISO/IEC 18004:2000 Annex E.

I don't understand how it's calculated. If you take the Version 16, for example, the positions are calculated using {6,26,50,74} and distance between the points are {20,24,24}. Why isn't it {6,28,52,74}, if the distances between the points, {22,24,22}, is distributed more equally?

I would like to know how this can be generated procedurally.

Answer 1

While the specification does provide a table of the alignment, this is a reasonable question (and one I found myself with :-)) - the possibility of generating the positions procedurally has its merits (less typo-prone code, smaller code footprint, knowing pattern/properties of the positions).

I'm happy to report that, yes, a procedure exists (and it is even fairly simple). The specification itself says most of it:

[The alignment patterns] are spaced as evenly as possible between the Timing Pattern and the opposite side of the symbol, any uneven spacing being accommodated between the timing pattern and the first alignment pattern in the symbol interior.

That is, only the interval between the first and second coordinate may differ from the rest of the intervals. The rest must be equal. Another important bit is of course that, for the APs to agree with the timing patterns, the intervals must be even. The remaining tricky bit is just getting the rounding right.

Anyway - here's code printing the alignment position table:

def size_for_version(version):
    return 17 + 4 * version

def alignment_coord_list(version):
    if version == 1:
        return []
    divs = 2 + version // 7
    size = size_for_version(version)
    total_dist = size - 7 - 6
    divisor = 2 * (divs - 1)
    # Step must be even, for alignment patterns to agree with timing patterns
    step = (total_dist + divisor // 2 + 1) // divisor * 2 # Get the rounding right
    coords = [6]
    for i in range(divs - 2, -1, -1): # divs-2 down to 0, inclusive
        coords.append(size - 7 - i * step)
    return coords

for version in range(1, 40 + 1): # 1 to 40 inclusive
    print("V%d: %s" % (version, alignment_coord_list(version)))

Answer 2

Here's a Python solution which is basically equivalent to the C# solution posted by @jgosar, except that it corrects a deviation from the thonky.com table for version 32 (that other solution reports 110 for the second last position, whereas the linked table says 112):

def get_alignment_positions(version):
    positions = []
    if version > 1:
        n_patterns = version // 7 + 2
        first_pos = 6
        positions.append(first_pos)
        matrix_width = 17 + 4 * version
        last_pos = matrix_width - 1 - first_pos
        second_last_pos = (
            (first_pos + last_pos * (n_patterns - 2)  # Interpolate end points to get point
            + (n_patterns - 1) // 2)                  # Round to nearest int by adding half
                                                      # of divisor before division
            // (n_patterns - 1)                       # Floor-divide by number of intervals
                                                      # to complete interpolation
            ) & -2                                    # Round down to even integer
        pos_step = last_pos - second_last_pos
        second_pos = last_pos - (n_patterns - 2) * pos_step
        positions.extend(range(second_pos, last_pos + 1, pos_step))
    return positions

The correction consists of first rounding the second last position (up or down) to the nearest integer and then rounding down to the nearest even integer (instead of directly rounding down to the nearest even integer).

Disclaimer: Like @jgosar, I don't know whether the thonky.com table is correct (I'm not going to buy the spec to find out). I've simply verified (by pasting the table into a suitable wrapper around the above function) that my solution matches that table in its current version.