Calculating the position of QR Code alignment patt

问题:

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.

回答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)))

回答2:

There are some comments on the top rated answer that suggest it isn't 100% accurate, so i'm contributing my solution as well.

My solution is written in C#. It should be easy to translate it to a language of your choice.

private static int[] getAlignmentCoords(int version)
    {
        if (version <= 1)
        {
            return new int[0];
        }

        int num = (version / 7) + 2;//number of coordinates to return
        int[] result = new int[num];

        result[0] = 6;

        if (num == 1)
        {
            return result;
        }

        result[num - 1] = 4 * version + 10;

        if (num == 2)
        {
            return result;
        }

        result[num - 2] = 2 * ((result[0] + result[num - 1] * (num - 2)) / ((num - 1) * 2)); //leave these brackets alone, because of integer division they ensure you get a number that's divisible by 2

        if (num == 3)
        {
            return result;
        }

        int step = result[num - 1] - result[num - 2];

        for (int i = num - 3; i > 0; i--)
        {
            result[i] = result[i + 1] - step;
        }

        return result;
    }

The values i get with it are the same as shown here: http://www.thonky.com/qr-code-tutorial/alignment-pattern-locations/

To sum it up, the first coordinate is always 6.

The last coordinate is always 7 less than the image size. The image size is calculated as 4*version+17, therefore the last coordinate is 4*version+10.

If the coordinates were precisely evenly spaced, the position of one coordinate before the last would be (first_coordinate+(num-2) * last_coordinate)/(num-1), where num is the number of all coordinates. But the coordinates are not evenly spaced, so this position has to be reduced to an even number.

Each of the remaining coordinates is spaced the same distance from the next one as the last two are from each other.

Disclaimer: I didn't read any of the documentation, i just wrote some code that generates a sequence of numbers that's the same as in the table i linked to.

回答3:

I don't know if this is a useful question to ask. It just is the way it is, and it doesn't really matter much if it were {22,24,22}. Why are you asking? My guess it that the spacing should be multiples of 4 modules.

回答4:

sorry about my English. I hope this can help you, and not to later reply. first things, the standard forget a important thing is that the top left is define with (0,0). the { 6, 26, 50, 74 } means the alignment points row coordinate and col coordinate, and I don't know why they do like this, maybe for save space. but we combine all the values for example the:

{ 6, 26, 50, 74 }

and we get :

{ 6 , 6  } ---> ( the x coordinate is 6, and the y is 6, from top/left )
{ 6 , 26 }
{ 6 , 50 }
{ 6 , 74 }
{ 26, 26 }
{ 26, 50 }
{ 26, 74 }
{ 50, 50 }
{ 50, 74 }
{ 74, 74 }

those point's are the actual coordinate of alignment patterns center. Ps: if a position has the position detection patterns, we ignore output alignment, like the position (6, 6).

I also have this question before, but now, I solve it, so I hope you can solve it too.

good luck~

回答5:

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.