AlignmentPatternFinder::find() - Code Metrics - chillerlan/php-qrcode - Measure and Improve Code Quality continuously with Scrutinizer

AlignmentPatternFinder::find() C
last analyzed 2023-06-21 14:22 UTC

↳ Parent: AlignmentPatternFinder

Complexity

Conditions	15
Paths	146

Size

Total Lines	83
Code Lines	40

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	15
eloc	40
c	1
b	0
f	0
nc	146
nop	4
dl	0
loc	83
rs	5.5333

How to fix Long Method Complexity

<?php
/**
 * Class AlignmentPatternFinder
 *
 * @created      17.01.2021
 * @author       ZXing Authors
 * @author       Smiley <[email protected]>
 * @copyright    2021 Smiley
 * @license      Apache-2.0
 */

namespace chillerlan\QRCode\Detector;

use chillerlan\QRCode\Decoder\BitMatrix;
use function abs, count;

/**
 * This class attempts to find alignment patterns in a QR Code. Alignment patterns look like finder
 * patterns but are smaller and appear at regular intervals throughout the image.
 *
 * At the moment this only looks for the bottom-right alignment pattern.
 *
 * This is mostly a simplified copy of FinderPatternFinder. It is copied,
 * pasted and stripped down here for maximum performance but does unfortunately duplicate
 * some code.
 *
 * This class is thread-safe but not reentrant. Each thread must allocate its own object.
 *
 * @author Sean Owen
 */
final class AlignmentPatternFinder{

	private BitMatrix $matrix;
	private float     $moduleSize;
	/** @var \chillerlan\QRCode\Detector\AlignmentPattern[] */
	private array $possibleCenters;

	/**
	 * Creates a finder that will look in a portion of the whole image.
	 *
	 * @param \chillerlan\QRCode\Decoder\BitMatrix $matrix     image to search
	 * @param float                                $moduleSize estimated module size so far
	 */
	public function __construct(BitMatrix $matrix, float $moduleSize){
		$this->matrix          = $matrix;
		$this->moduleSize      = $moduleSize;
		$this->possibleCenters = [];
	}

	/**
	 * This method attempts to find the bottom-right alignment pattern in the image. It is a bit messy since
	 * it's pretty performance-critical and so is written to be fast foremost.
	 *
	 * @param int $startX left column from which to start searching
	 * @param int $startY top row from which to start searching
	 * @param int $width  width of region to search
	 * @param int $height height of region to search
	 *
	 * @return \chillerlan\QRCode\Detector\AlignmentPattern|null
	 */
	public function find(int $startX, int $startY, int $width, int $height):?AlignmentPattern{
		$maxJ       = ($startX + $width);
		$middleI    = ($startY + ($height / 2));
		$stateCount = [];

		// We are looking for black/white/black modules in 1:1:1 ratio;
		// this tracks the number of black/white/black modules seen so far
		for($iGen = 0; $iGen < $height; $iGen++){
			// Search from middle outwards
			$i             = (int)($middleI + ((($iGen & 0x01) === 0) ? ($iGen + 1) / 2 : -(($iGen + 1) / 2)));
			$stateCount[0] = 0;
			$stateCount[1] = 0;
			$stateCount[2] = 0;
			$j             = $startX;
			// Burn off leading white pixels before anything else; if we start in the middle of
			// a white run, it doesn't make sense to count its length, since we don't know if the
			// white run continued to the left of the start point
			while($j < $maxJ && !$this->matrix->check($j, $i)){
				$j++;
			}

			$currentState = 0;

			while($j < $maxJ){

				if($this->matrix->check($j, $i)){
					// Black pixel
					if($currentState === 1){ // Counting black pixels
						$stateCount[$currentState]++;
					}
					// Counting white pixels
					else{
						// A winner?
						if($currentState === 2){
							// Yes
							if($this->foundPatternCross($stateCount)){
								$confirmed = $this->handlePossibleCenter($stateCount, $i, $j);

								if($confirmed !== null){
									return $confirmed;
								}
							}

							$stateCount[0] = $stateCount[2];
							$stateCount[1] = 1;
							$stateCount[2] = 0;
							$currentState  = 1;
						}
						else{
							$stateCount[++$currentState]++;
						}
					}
				}
				// White pixel
				else{
					// Counting black pixels
					if($currentState === 1){
						$currentState++;
					}

					$stateCount[$currentState]++;
				}

				$j++;
			}

			if($this->foundPatternCross($stateCount)){
				$confirmed = $this->handlePossibleCenter($stateCount, $i, $maxJ);

				if($confirmed !== null){
					return $confirmed;
				}
			}

		}

		// Hmm, nothing we saw was observed and confirmed twice. If we had
		// any guess at all, return it.
		if(count($this->possibleCenters)){
			return $this->possibleCenters[0];
		}

		return null;
	}

	/**
	 * @param int[] $stateCount count of black/white/black pixels just read
	 *
	 * @return bool true if the proportions of the counts is close enough to the 1/1/1 ratios
	 *         used by alignment patterns to be considered a match
	 */
	private function foundPatternCross(array $stateCount):bool{
		$maxVariance = ($this->moduleSize / 2.0);

		for($i = 0; $i < 3; $i++){
			if(abs($this->moduleSize - $stateCount[$i]) >= $maxVariance){
				return false;
			}
		}

		return true;
	}

	/**
	 * This is called when a horizontal scan finds a possible alignment pattern. It will
	 * cross-check with a vertical scan, and if successful, will see if this pattern had been
	 * found on a previous horizontal scan. If so, we consider it confirmed and conclude we have
	 * found the alignment pattern.
	 *
	 * @param int[] $stateCount reading state module counts from horizontal scan
	 * @param int   $i          row where alignment pattern may be found
	 * @param int   $j          end of possible alignment pattern in row
	 *
	 * @return \chillerlan\QRCode\Detector\AlignmentPattern|null if we have found the same pattern twice, or null if not
	 */
	private function handlePossibleCenter(array $stateCount, int $i, int $j):?AlignmentPattern{
		$stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2]);
		$centerJ         = $this->centerFromEnd($stateCount, $j);
		$centerI         = $this->crossCheckVertical($i, (int)$centerJ, (2 * $stateCount[1]), $stateCountTotal);

		if($centerI !== null){
			$estimatedModuleSize = (($stateCount[0] + $stateCount[1] + $stateCount[2]) / 3.0);

			foreach($this->possibleCenters as $center){
				// Look for about the same center and module size:
				if($center->aboutEquals($estimatedModuleSize, $centerI, $centerJ)){
					return $center->combineEstimate($centerI, $centerJ, $estimatedModuleSize);
				}
			}

			// Hadn't found this before; save it
			$point                   = new AlignmentPattern($centerJ, $centerI, $estimatedModuleSize);
			$this->possibleCenters[] = $point;
		}

		return null;
	}

	/**
	 * Given a count of black/white/black pixels just seen and an end position,
	 * figures the location of the center of this black/white/black run.
	 *
	 * @param int[] $stateCount
	 * @param int   $end
	 *
	 * @return float
	 */
	private function centerFromEnd(array $stateCount, int $end):float{
		return (float)(($end - $stateCount[2]) - $stateCount[1] / 2);
	}

	/**
	 * After a horizontal scan finds a potential alignment pattern, this method
	 * "cross-checks" by scanning down vertically through the center of the possible
	 * alignment pattern to see if the same proportion is detected.
	 *
	 * @param int $startI   row where an alignment pattern was detected
	 * @param int $centerJ  center of the section that appears to cross an alignment pattern
	 * @param int $maxCount maximum reasonable number of modules that should be
	 *                      observed in any reading state, based on the results of the horizontal scan
	 * @param int $originalStateCountTotal
	 *
	 * @return float|null vertical center of alignment pattern, or null if not found
	 */
	private function crossCheckVertical(int $startI, int $centerJ, int $maxCount, int $originalStateCountTotal):?float{
		$maxI          = $this->matrix->getSize();
		$stateCount    = [];
		$stateCount[0] = 0;
		$stateCount[1] = 0;
		$stateCount[2] = 0;

		// Start counting up from center
		$i = $startI;
		while($i >= 0 && $this->matrix->check($centerJ, $i) && $stateCount[1] <= $maxCount){
			$stateCount[1]++;
			$i--;
		}
		// If already too many modules in this state or ran off the edge:
		if($i < 0 || $stateCount[1] > $maxCount){
			return null;
		}

		while($i >= 0 && !$this->matrix->check($centerJ, $i) && $stateCount[0] <= $maxCount){
			$stateCount[0]++;
			$i--;
		}

		if($stateCount[0] > $maxCount){
			return null;
		}

		// Now also count down from center
		$i = ($startI + 1);
		while($i < $maxI && $this->matrix->check($centerJ, $i) && $stateCount[1] <= $maxCount){
			$stateCount[1]++;
			$i++;
		}

		if($i == $maxI || $stateCount[1] > $maxCount){
			return null;
		}

		while($i < $maxI && !$this->matrix->check($centerJ, $i) && $stateCount[2] <= $maxCount){
			$stateCount[2]++;
			$i++;
		}

		if($stateCount[2] > $maxCount){
			return null;
		}

		if((5 * abs(($stateCount[0] + $stateCount[1] + $stateCount[2]) - $originalStateCountTotal)) >= (2 * $originalStateCountTotal)){
			return null;
		}

		if(!$this->foundPatternCross($stateCount)){
			return null;
		}

		return $this->centerFromEnd($stateCount, $i);
	}

}


1			<?php
2			/**
3			* Class AlignmentPatternFinder
4			*
5			* @created 17.01.2021
6			* @author ZXing Authors
7			* @author Smiley <[email protected]>
8			* @copyright 2021 Smiley
9			* @license Apache-2.0
10			*/
11
12			namespace chillerlan\QRCode\Detector;
13
14			use chillerlan\QRCode\Decoder\BitMatrix;
15			use function abs, count;
16
17			/**
18			* This class attempts to find alignment patterns in a QR Code. Alignment patterns look like finder
19			* patterns but are smaller and appear at regular intervals throughout the image.
20			*
21			* At the moment this only looks for the bottom-right alignment pattern.
22			*
23			* This is mostly a simplified copy of FinderPatternFinder. It is copied,
24			* pasted and stripped down here for maximum performance but does unfortunately duplicate
25			* some code.
26			*
27			* This class is thread-safe but not reentrant. Each thread must allocate its own object.
28			*
29			* @author Sean Owen
30			*/
31			final class AlignmentPatternFinder{
32
33			private BitMatrix $matrix;
34			private float $moduleSize;
35			/** @var \chillerlan\QRCode\Detector\AlignmentPattern[] */
36			private array $possibleCenters;
37
38			/**
39			* Creates a finder that will look in a portion of the whole image.
40			*
41			* @param \chillerlan\QRCode\Decoder\BitMatrix $matrix image to search
42			* @param float $moduleSize estimated module size so far
43			*/
44			public function __construct(BitMatrix $matrix, float $moduleSize){
45			$this->matrix = $matrix;
46			$this->moduleSize = $moduleSize;
47			$this->possibleCenters = [];
48			}
49
50			/**
51			* This method attempts to find the bottom-right alignment pattern in the image. It is a bit messy since
52			* it's pretty performance-critical and so is written to be fast foremost.
53			*
54			* @param int $startX left column from which to start searching
55			* @param int $startY top row from which to start searching
56			* @param int $width width of region to search
57			* @param int $height height of region to search
58			*
59			* @return \chillerlan\QRCode\Detector\AlignmentPattern\|null
60			*/
61			public function find(int $startX, int $startY, int $width, int $height):?AlignmentPattern{
62			$maxJ = ($startX + $width);
63			$middleI = ($startY + ($height / 2));
64			$stateCount = [];
65
66			// We are looking for black/white/black modules in 1:1:1 ratio;
67			// this tracks the number of black/white/black modules seen so far
68			for($iGen = 0; $iGen < $height; $iGen++){
69			// Search from middle outwards
70			$i = (int)($middleI + ((($iGen & 0x01) === 0) ? ($iGen + 1) / 2 : -(($iGen + 1) / 2)));
71			$stateCount[0] = 0;
72			$stateCount[1] = 0;
73			$stateCount[2] = 0;
74			$j = $startX;
75			// Burn off leading white pixels before anything else; if we start in the middle of
76			// a white run, it doesn't make sense to count its length, since we don't know if the
77			// white run continued to the left of the start point
78			while($j < $maxJ && !$this->matrix->check($j, $i)){
79			$j++;
80			}
81
82			$currentState = 0;
83
84			while($j < $maxJ){
85
86			if($this->matrix->check($j, $i)){
87			// Black pixel
88			if($currentState === 1){ // Counting black pixels
89			$stateCount[$currentState]++;
90			}
91			// Counting white pixels
92			else{
93			// A winner?
94			if($currentState === 2){
95			// Yes
96			if($this->foundPatternCross($stateCount)){
97			$confirmed = $this->handlePossibleCenter($stateCount, $i, $j);
98
99			if($confirmed !== null){
100			return $confirmed;
101			}
102			}
103
104			$stateCount[0] = $stateCount[2];
105			$stateCount[1] = 1;
106			$stateCount[2] = 0;
107			$currentState = 1;
108			}
109			else{
110			$stateCount[++$currentState]++;
111			}
112			}
113			}
114			// White pixel
115			else{
116			// Counting black pixels
117			if($currentState === 1){
118			$currentState++;
119			}
120
121			$stateCount[$currentState]++;
122			}
123
124			$j++;
125			}
126
127			if($this->foundPatternCross($stateCount)){
128			$confirmed = $this->handlePossibleCenter($stateCount, $i, $maxJ);
129
130			if($confirmed !== null){
131			return $confirmed;
132			}
133			}
134
135			}
136
137			// Hmm, nothing we saw was observed and confirmed twice. If we had
138			// any guess at all, return it.
139			if(count($this->possibleCenters)){
140			return $this->possibleCenters[0];
141			}
142
143			return null;
144			}
145
146			/**
147			* @param int[] $stateCount count of black/white/black pixels just read
148			*
149			* @return bool true if the proportions of the counts is close enough to the 1/1/1 ratios
150			* used by alignment patterns to be considered a match
151			*/
152			private function foundPatternCross(array $stateCount):bool{
153			$maxVariance = ($this->moduleSize / 2.0);
154
155			for($i = 0; $i < 3; $i++){
156			if(abs($this->moduleSize - $stateCount[$i]) >= $maxVariance){
157			return false;
158			}
159			}
160
161			return true;
162			}
163
164			/**
165			* This is called when a horizontal scan finds a possible alignment pattern. It will
166			* cross-check with a vertical scan, and if successful, will see if this pattern had been
167			* found on a previous horizontal scan. If so, we consider it confirmed and conclude we have
168			* found the alignment pattern.
169			*
170			* @param int[] $stateCount reading state module counts from horizontal scan
171			* @param int $i row where alignment pattern may be found
172			* @param int $j end of possible alignment pattern in row
173			*
174			* @return \chillerlan\QRCode\Detector\AlignmentPattern\|null if we have found the same pattern twice, or null if not
175			*/
176			private function handlePossibleCenter(array $stateCount, int $i, int $j):?AlignmentPattern{
177			$stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2]);
178			$centerJ = $this->centerFromEnd($stateCount, $j);
179			$centerI = $this->crossCheckVertical($i, (int)$centerJ, (2 * $stateCount[1]), $stateCountTotal);
180
181			if($centerI !== null){
182			$estimatedModuleSize = (($stateCount[0] + $stateCount[1] + $stateCount[2]) / 3.0);
183
184			foreach($this->possibleCenters as $center){
185			// Look for about the same center and module size:
186			if($center->aboutEquals($estimatedModuleSize, $centerI, $centerJ)){
187			return $center->combineEstimate($centerI, $centerJ, $estimatedModuleSize);
188			}
189			}
190
191			// Hadn't found this before; save it
192			$point = new AlignmentPattern($centerJ, $centerI, $estimatedModuleSize);
193			$this->possibleCenters[] = $point;
194			}
195
196			return null;
197			}
198
199			/**
200			* Given a count of black/white/black pixels just seen and an end position,
201			* figures the location of the center of this black/white/black run.
202			*
203			* @param int[] $stateCount
204			* @param int $end
205			*
206			* @return float
207			*/
208			private function centerFromEnd(array $stateCount, int $end):float{
209			return (float)(($end - $stateCount[2]) - $stateCount[1] / 2);
210			}
211
212			/**
213			* After a horizontal scan finds a potential alignment pattern, this method
214			* "cross-checks" by scanning down vertically through the center of the possible
215			* alignment pattern to see if the same proportion is detected.
216			*
217			* @param int $startI row where an alignment pattern was detected
218			* @param int $centerJ center of the section that appears to cross an alignment pattern
219			* @param int $maxCount maximum reasonable number of modules that should be
220			* observed in any reading state, based on the results of the horizontal scan
221			* @param int $originalStateCountTotal
222			*
223			* @return float\|null vertical center of alignment pattern, or null if not found
224			*/
225			private function crossCheckVertical(int $startI, int $centerJ, int $maxCount, int $originalStateCountTotal):?float{
226			$maxI = $this->matrix->getSize();
227			$stateCount = [];
228			$stateCount[0] = 0;
229			$stateCount[1] = 0;
230			$stateCount[2] = 0;
231
232			// Start counting up from center
233			$i = $startI;
234			while($i >= 0 && $this->matrix->check($centerJ, $i) && $stateCount[1] <= $maxCount){
235			$stateCount[1]++;
236			$i--;
237			}
238			// If already too many modules in this state or ran off the edge:
239			if($i < 0 \|\| $stateCount[1] > $maxCount){
240			return null;
241			}
242
243			while($i >= 0 && !$this->matrix->check($centerJ, $i) && $stateCount[0] <= $maxCount){
244			$stateCount[0]++;
245			$i--;
246			}
247
248			if($stateCount[0] > $maxCount){
249			return null;
250			}
251
252			// Now also count down from center
253			$i = ($startI + 1);
254			while($i < $maxI && $this->matrix->check($centerJ, $i) && $stateCount[1] <= $maxCount){
255			$stateCount[1]++;
256			$i++;
257			}
258
259			if($i == $maxI \|\| $stateCount[1] > $maxCount){
260			return null;
261			}
262
263			while($i < $maxI && !$this->matrix->check($centerJ, $i) && $stateCount[2] <= $maxCount){
264			$stateCount[2]++;
265			$i++;
266			}
267
268			if($stateCount[2] > $maxCount){
269			return null;
270			}
271
272			if((5 * abs(($stateCount[0] + $stateCount[1] + $stateCount[2]) - $originalStateCountTotal)) >= (2 * $originalStateCountTotal)){
273			return null;
274			}
275
276			if(!$this->foundPatternCross($stateCount)){
277			return null;
278			}
279
280			return $this->centerFromEnd($stateCount, $i);
281			}
282
283			}
284

chillerlan / php-qrcode

AlignmentPatternFinder::find() C last analyzed 2023-06-21 14:22 UTC

Complexity

Size

Duplication

Importance

How to fix Long Method Complexity

Long Method

Duplication Side-by-Side

Filter issues like

AlignmentPatternFinder::find() C
last analyzed 2023-06-21 14:22 UTC