1 /**
2 * libdmtx - Data Matrix Encoding/Decoding Library
3 * Copyright 2008, 2009 Mike Laughton. All rights reserved.
4 * Copyright 2012-2016 Vadim A. Misbakh-Soloviov. All rights reserved.
5 *
6 * See LICENSE file in the main project directory for full
7 * terms of use and distribution.
8 *
9 * Contact:
10 * Vadim A. Misbakh-Soloviov <dmtx@mva.name>
11 * Mike Laughton <mike@dragonflylogic.com>
12 *
13 * \file dmtxscangrid.c
14 * \brief Scan grid tracking
15 */
16
17 /**
18 * \brief Initialize scan grid pattern
19 * \param dec
20 * \return Initialized grid
21 */
22 static DmtxScanGrid
InitScanGrid(DmtxDecode * dec)23 InitScanGrid(DmtxDecode *dec)
24 {
25 int scale, smallestFeature;
26 int xExtent, yExtent, maxExtent;
27 int extent;
28 DmtxScanGrid grid;
29
30 memset(&grid, 0x00, sizeof(DmtxScanGrid));
31
32 scale = dmtxDecodeGetProp(dec, DmtxPropScale);
33 smallestFeature = dmtxDecodeGetProp(dec, DmtxPropScanGap) / scale;
34
35 grid.xMin = dmtxDecodeGetProp(dec, DmtxPropXmin);
36 grid.xMax = dmtxDecodeGetProp(dec, DmtxPropXmax);
37 grid.yMin = dmtxDecodeGetProp(dec, DmtxPropYmin);
38 grid.yMax = dmtxDecodeGetProp(dec, DmtxPropYmax);
39
40 /* Values that get set once */
41 xExtent = grid.xMax - grid.xMin;
42 yExtent = grid.yMax - grid.yMin;
43 maxExtent = (xExtent > yExtent) ? xExtent : yExtent;
44
45 assert(maxExtent > 1);
46
47 for(extent = 1; extent < maxExtent; extent = ((extent + 1) * 2) - 1)
48 if(extent <= smallestFeature)
49 grid.minExtent = extent;
50
51 grid.maxExtent = extent;
52
53 grid.xOffset = (grid.xMin + grid.xMax - grid.maxExtent) / 2;
54 grid.yOffset = (grid.yMin + grid.yMax - grid.maxExtent) / 2;
55
56 /* Values that get reset for every level */
57 grid.total = 1;
58 grid.extent = grid.maxExtent;
59
60 SetDerivedFields(&grid);
61
62 return grid;
63 }
64
65 /**
66 * \brief Return the next good location (which may be the current location),
67 * and advance grid progress one position beyond that. If no good
68 * locations remain then return DmtxRangeEnd.
69 * \param grid
70 * \return void
71 */
72 static int
PopGridLocation(DmtxScanGrid * grid,DmtxPixelLoc * locPtr)73 PopGridLocation(DmtxScanGrid *grid, DmtxPixelLoc *locPtr)
74 {
75 int locStatus;
76
77 do {
78 locStatus = GetGridCoordinates(grid, locPtr);
79
80 /* Always leave grid pointing at next available location */
81 grid->pixelCount++;
82
83 } while(locStatus == DmtxRangeBad);
84
85 return locStatus;
86 }
87
88 /**
89 * \brief Extract current grid position in pixel coordinates and return
90 * whether location is good, bad, or end
91 * \param grid
92 * \return Pixel location
93 */
94 static int
GetGridCoordinates(DmtxScanGrid * grid,DmtxPixelLoc * locPtr)95 GetGridCoordinates(DmtxScanGrid *grid, DmtxPixelLoc *locPtr)
96 {
97 int count, half, quarter;
98 DmtxPixelLoc loc;
99
100 /* Initially pixelCount may fall beyond acceptable limits. Update grid
101 * state before testing coordinates */
102
103 /* Jump to next cross pattern horizontally if current column is done */
104 if(grid->pixelCount >= grid->pixelTotal) {
105 grid->pixelCount = 0;
106 grid->xCenter += grid->jumpSize;
107 }
108
109 /* Jump to next cross pattern vertically if current row is done */
110 if(grid->xCenter > grid->maxExtent) {
111 grid->xCenter = grid->startPos;
112 grid->yCenter += grid->jumpSize;
113 }
114
115 /* Increment level when vertical step goes too far */
116 if(grid->yCenter > grid->maxExtent) {
117 grid->total *= 4;
118 grid->extent /= 2;
119 SetDerivedFields(grid);
120 }
121
122 if(grid->extent == 0 || grid->extent < grid->minExtent) {
123 locPtr->X = locPtr->Y = -1;
124 return DmtxRangeEnd;
125 }
126
127 count = grid->pixelCount;
128
129 assert(count < grid->pixelTotal);
130
131 if(count == grid->pixelTotal - 1) {
132 /* center pixel */
133 loc.X = grid->xCenter;
134 loc.Y = grid->yCenter;
135 }
136 else {
137 half = grid->pixelTotal / 2;
138 quarter = half / 2;
139
140 /* horizontal portion */
141 if(count < half) {
142 loc.X = grid->xCenter + ((count < quarter) ? (count - quarter) : (half - count));
143 loc.Y = grid->yCenter;
144 }
145 /* vertical portion */
146 else {
147 count -= half;
148 loc.X = grid->xCenter;
149 loc.Y = grid->yCenter + ((count < quarter) ? (count - quarter) : (half - count));
150 }
151 }
152
153 loc.X += grid->xOffset;
154 loc.Y += grid->yOffset;
155
156 *locPtr = loc;
157
158 if(loc.X < grid->xMin || loc.X > grid->xMax ||
159 loc.Y < grid->yMin || loc.Y > grid->yMax)
160 return DmtxRangeBad;
161
162 return DmtxRangeGood;
163 }
164
165 /**
166 * \brief Update derived fields based on current state
167 * \param grid
168 * \return void
169 */
170 static void
SetDerivedFields(DmtxScanGrid * grid)171 SetDerivedFields(DmtxScanGrid *grid)
172 {
173 grid->jumpSize = grid->extent + 1;
174 grid->pixelTotal = 2 * grid->extent - 1;
175 grid->startPos = grid->extent / 2;
176 grid->pixelCount = 0;
177 grid->xCenter = grid->yCenter = grid->startPos;
178 }
179