Passed
Push — gh-pages ( 20c441...dd59e5 )
by
unknown
02:54 queued 01:00
created

FinderPatternFinder::__construct()   A

Complexity

Conditions 1
Paths 1

Size

Total Lines 3
Code Lines 2

Duplication

Lines 0
Ratio 0 %

Importance

Changes 1
Bugs 0 Features 0
Metric Value
cc 1
eloc 2
c 1
b 0
f 0
nc 1
nop 1
dl 0
loc 3
rs 10
1
<?php
2
/**
3
 * Class FinderPatternFinder
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
 * @phan-file-suppress PhanTypePossiblyInvalidDimOffset
12
 */
13
14
namespace chillerlan\QRCode\Detector;
15
16
use RuntimeException;
17
use chillerlan\QRCode\Decoder\BitMatrix;
18
use function abs, count, usort;
19
use const PHP_FLOAT_MAX;
20
21
/**
22
 * <p>This class attempts to find finder patterns in a QR Code. Finder patterns are the square
23
 * markers at three corners of a QR Code.</p>
24
 *
25
 * <p>This class is thread-safe but not reentrant. Each thread must allocate its own object.
26
 *
27
 * @author Sean Owen
28
 */
29
final class FinderPatternFinder{
30
31
	private const MIN_SKIP      = 2;
32
	private const MAX_MODULES   = 177; // 1 pixel/module times 3 modules/center
33
	private const CENTER_QUORUM = 2; // support up to version 10 for mobile clients
34
	private BitMatrix $bitMatrix;
35
	/** @var \chillerlan\QRCode\Detector\FinderPattern[] */
36
	private array $possibleCenters;
37
	private bool  $hasSkipped = false;
38
39
	/**
40
	 * <p>Creates a finder that will search the image for three finder patterns.</p>
41
	 *
42
	 * @param BitMatrix $bitMatrix image to search
43
	 */
44
	public function __construct(BitMatrix $bitMatrix){
45
		$this->bitMatrix       = $bitMatrix;
46
		$this->possibleCenters = [];
47
	}
48
49
	/**
50
	 * @return \chillerlan\QRCode\Detector\FinderPattern[]
51
	 */
52
	public function find():array{
53
		$dimension = $this->bitMatrix->getDimension();
54
55
		// We are looking for black/white/black/white/black modules in
56
		// 1:1:3:1:1 ratio; this tracks the number of such modules seen so far
57
		// Let's assume that the maximum version QR Code we support takes up 1/4 the height of the
58
		// image, and then account for the center being 3 modules in size. This gives the smallest
59
		// number of pixels the center could be, so skip this often.
60
		$iSkip = (int)((3 * $dimension) / (4 * self::MAX_MODULES));
61
62
		if($iSkip < self::MIN_SKIP){
63
			$iSkip = self::MIN_SKIP;
64
		}
65
66
		$done = false;
67
68
		for($i = $iSkip - 1; $i < $dimension && !$done; $i += $iSkip){
69
			// Get a row of black/white values
70
			$stateCount   = $this->getCrossCheckStateCount();
71
			$currentState = 0;
72
73
			for($j = 0; $j < $dimension; $j++){
74
75
				// Black pixel
76
				if($this->bitMatrix->get($j, $i)){
77
					// Counting white pixels
78
					if(($currentState & 1) === 1){
79
						$currentState++;
80
					}
81
82
					$stateCount[$currentState]++;
83
				}
84
				// White pixel
85
				else{
86
					// Counting black pixels
87
					if(($currentState & 1) === 0){
88
						// A winner?
89
						if($currentState === 4){
90
							// Yes
91
							if($this->foundPatternCross($stateCount)){
92
								$confirmed = $this->handlePossibleCenter($stateCount, $i, $j);
93
94
								if($confirmed){
95
									// Start examining every other line. Checking each line turned out to be too
96
									// expensive and didn't improve performance.
97
									$iSkip = 3;
98
99
									if($this->hasSkipped){
100
										$done = $this->haveMultiplyConfirmedCenters();
101
									}
102
									else{
103
										$rowSkip = $this->findRowSkip();
104
105
										if($rowSkip > $stateCount[2]){
106
											// Skip rows between row of lower confirmed center
107
											// and top of presumed third confirmed center
108
											// but back up a bit to get a full chance of detecting
109
											// it, entire width of center of finder pattern
110
111
											// Skip by rowSkip, but back off by $stateCount[2] (size of last center
112
											// of pattern we saw) to be conservative, and also back off by iSkip which
113
											// is about to be re-added
114
											$i += $rowSkip - $stateCount[2] - $iSkip;
115
											$j = $dimension - 1;
116
										}
117
									}
118
								}
119
								else{
120
									$stateCount   = $this->doShiftCounts2($stateCount);
121
									$currentState = 3;
122
123
									continue;
124
								}
125
								// Clear state to start looking again
126
								$currentState = 0;
127
								$stateCount   = $this->getCrossCheckStateCount();
128
							}
129
							// No, shift counts back by two
130
							else{
131
								$stateCount   = $this->doShiftCounts2($stateCount);
132
								$currentState = 3;
133
							}
134
						}
135
						else{
136
							$stateCount[++$currentState]++;
137
						}
138
					}
139
					// Counting white pixels
140
					else{
141
						$stateCount[$currentState]++;
142
					}
143
				}
144
			}
145
146
			if($this->foundPatternCross($stateCount)){
147
				$confirmed = $this->handlePossibleCenter($stateCount, $i, $dimension);
148
149
				if($confirmed){
150
					$iSkip = $stateCount[0];
151
152
					if($this->hasSkipped){
153
						// Found a third one
154
						$done = $this->haveMultiplyConfirmedCenters();
155
					}
156
				}
157
			}
158
		}
159
160
		return $this->orderBestPatterns($this->selectBestPatterns());
161
	}
162
163
	/**
164
	 * @return int[]
165
	 */
166
	private function getCrossCheckStateCount():array{
167
		return [0, 0, 0, 0, 0];
168
	}
169
170
	/**
171
	 * @param int[] $stateCount
172
	 *
173
	 * @return int[]
174
	 */
175
	private function doShiftCounts2(array $stateCount):array{
176
		$stateCount[0] = $stateCount[2];
177
		$stateCount[1] = $stateCount[3];
178
		$stateCount[2] = $stateCount[4];
179
		$stateCount[3] = 1;
180
		$stateCount[4] = 0;
181
182
		return $stateCount;
183
	}
184
185
	/**
186
	 * Given a count of black/white/black/white/black pixels just seen and an end position,
187
	 * figures the location of the center of this run.
188
	 *
189
	 * @param int[] $stateCount
190
	 */
191
	private function centerFromEnd(array $stateCount, int $end):float{
192
		return (float)(($end - $stateCount[4] - $stateCount[3]) - $stateCount[2] / 2.0);
193
	}
194
195
	/**
196
	 * @param int[] $stateCount
197
	 */
198
	private function foundPatternCross(array $stateCount):bool{
199
		// Allow less than 50% variance from 1-1-3-1-1 proportions
200
		return $this->foundPatternVariance($stateCount, 2.0);
201
	}
202
203
	/**
204
	 * @param int[] $stateCount
205
	 */
206
	private function foundPatternDiagonal(array $stateCount):bool{
207
		// Allow less than 75% variance from 1-1-3-1-1 proportions
208
		return $this->foundPatternVariance($stateCount, 1.333);
209
	}
210
211
	/**
212
	 * @param int[] $stateCount count of black/white/black/white/black pixels just read
213
	 *
214
	 * @return bool true if the proportions of the counts is close enough to the 1/1/3/1/1 ratios
215
	 *              used by finder patterns to be considered a match
216
	 */
217
	private function foundPatternVariance(array $stateCount, float $variance):bool{
218
		$totalModuleSize = 0;
219
220
		for($i = 0; $i < 5; $i++){
221
			$count = $stateCount[$i];
222
223
			if($count === 0){
224
				return false;
225
			}
226
227
			$totalModuleSize += $count;
228
		}
229
230
		if($totalModuleSize < 7){
231
			return false;
232
		}
233
234
		$moduleSize  = $totalModuleSize / 7.0;
235
		$maxVariance = $moduleSize / $variance;
236
237
		return
238
			abs($moduleSize - $stateCount[0]) < $maxVariance
239
			&& abs($moduleSize - $stateCount[1]) < $maxVariance
240
			&& abs(3.0 * $moduleSize - $stateCount[2]) < 3 * $maxVariance
241
			&& abs($moduleSize - $stateCount[3]) < $maxVariance
242
			&& abs($moduleSize - $stateCount[4]) < $maxVariance;
243
	}
244
245
	/**
246
	 * After a vertical and horizontal scan finds a potential finder pattern, this method
247
	 * "cross-cross-cross-checks" by scanning down diagonally through the center of the possible
248
	 * finder pattern to see if the same proportion is detected.
249
	 *
250
	 * @param $centerI ;  row where a finder pattern was detected
0 ignored issues
show
Documentation Bug introduced by
The doc comment ; at position 0 could not be parsed: Unknown type name ';' at position 0 in ;.
Loading history...
251
	 * @param $centerJ ; center of the section that appears to cross a finder pattern
252
	 *
253
	 * @return bool true if proportions are withing expected limits
254
	 */
255
	private function crossCheckDiagonal(int $centerI, int $centerJ):bool{
256
		$stateCount = $this->getCrossCheckStateCount();
257
258
		// Start counting up, left from center finding black center mass
259
		$i = 0;
260
261
		while($centerI >= $i && $centerJ >= $i && $this->bitMatrix->get($centerJ - $i, $centerI - $i)){
262
			$stateCount[2]++;
263
			$i++;
264
		}
265
266
		if($stateCount[2] === 0){
267
			return false;
268
		}
269
270
		// Continue up, left finding white space
271
		while($centerI >= $i && $centerJ >= $i && !$this->bitMatrix->get($centerJ - $i, $centerI - $i)){
272
			$stateCount[1]++;
273
			$i++;
274
		}
275
276
		if($stateCount[1] === 0){
277
			return false;
278
		}
279
280
		// Continue up, left finding black border
281
		while($centerI >= $i && $centerJ >= $i && $this->bitMatrix->get($centerJ - $i, $centerI - $i)){
282
			$stateCount[0]++;
283
			$i++;
284
		}
285
286
		if($stateCount[0] === 0){
287
			return false;
288
		}
289
290
		$dimension = $this->bitMatrix->getDimension();
291
292
		// Now also count down, right from center
293
		$i = 1;
294
		while($centerI + $i < $dimension && $centerJ + $i < $dimension && $this->bitMatrix->get($centerJ + $i, $centerI + $i)){
295
			$stateCount[2]++;
296
			$i++;
297
		}
298
299
		while($centerI + $i < $dimension && $centerJ + $i < $dimension && !$this->bitMatrix->get($centerJ + $i, $centerI + $i)){
300
			$stateCount[3]++;
301
			$i++;
302
		}
303
304
		if($stateCount[3] === 0){
305
			return false;
306
		}
307
308
		while($centerI + $i < $dimension && $centerJ + $i < $dimension && $this->bitMatrix->get($centerJ + $i, $centerI + $i)){
309
			$stateCount[4]++;
310
			$i++;
311
		}
312
313
		if($stateCount[4] === 0){
314
			return false;
315
		}
316
317
		return $this->foundPatternDiagonal($stateCount);
318
	}
319
320
	/**
321
	 * <p>After a horizontal scan finds a potential finder pattern, this method
322
	 * "cross-checks" by scanning down vertically through the center of the possible
323
	 * finder pattern to see if the same proportion is detected.</p>
324
	 *
325
	 * @param int $startI   ;  row where a finder pattern was detected
326
	 * @param int $centerJ  ; center of the section that appears to cross a finder pattern
327
	 * @param int $maxCount ; maximum reasonable number of modules that should be
328
	 *                      observed in any reading state, based on the results of the horizontal scan
329
	 * @param int $originalStateCountTotal
330
	 *
331
	 * @return float|null vertical center of finder pattern, or null if not found
332
	 */
333
	private function crossCheckVertical(int $startI, int $centerJ, int $maxCount, int $originalStateCountTotal):?float{
334
		$maxI       = $this->bitMatrix->getDimension();
335
		$stateCount = $this->getCrossCheckStateCount();
336
337
		// Start counting up from center
338
		$i = $startI;
339
		while($i >= 0 && $this->bitMatrix->get($centerJ, $i)){
340
			$stateCount[2]++;
341
			$i--;
342
		}
343
344
		if($i < 0){
345
			return null;
346
		}
347
348
		while($i >= 0 && !$this->bitMatrix->get($centerJ, $i) && $stateCount[1] <= $maxCount){
349
			$stateCount[1]++;
350
			$i--;
351
		}
352
353
		// If already too many modules in this state or ran off the edge:
354
		if($i < 0 || $stateCount[1] > $maxCount){
355
			return null;
356
		}
357
358
		while($i >= 0 && $this->bitMatrix->get($centerJ, $i) && $stateCount[0] <= $maxCount){
359
			$stateCount[0]++;
360
			$i--;
361
		}
362
363
		if($stateCount[0] > $maxCount){
364
			return null;
365
		}
366
367
		// Now also count down from center
368
		$i = $startI + 1;
369
		while($i < $maxI && $this->bitMatrix->get($centerJ, $i)){
370
			$stateCount[2]++;
371
			$i++;
372
		}
373
374
		if($i === $maxI){
375
			return null;
376
		}
377
378
		while($i < $maxI && !$this->bitMatrix->get($centerJ, $i) && $stateCount[3] < $maxCount){
379
			$stateCount[3]++;
380
			$i++;
381
		}
382
383
		if($i === $maxI || $stateCount[3] >= $maxCount){
384
			return null;
385
		}
386
387
		while($i < $maxI && $this->bitMatrix->get($centerJ, $i) && $stateCount[4] < $maxCount){
388
			$stateCount[4]++;
389
			$i++;
390
		}
391
392
		if($stateCount[4] >= $maxCount){
393
			return null;
394
		}
395
396
		// If we found a finder-pattern-like section, but its size is more than 40% different than
397
		// the original, assume it's a false positive
398
		$stateCountTotal = $stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4];
399
400
		if(5 * abs($stateCountTotal - $originalStateCountTotal) >= 2 * $originalStateCountTotal){
401
			return null;
402
		}
403
404
		if(!$this->foundPatternCross($stateCount)){
405
			return null;
406
		}
407
408
		return $this->centerFromEnd($stateCount, $i);
409
	}
410
411
	/**
412
	 * <p>Like {@link #crossCheckVertical(int, int, int, int)}, and in fact is basically identical,
413
	 * except it reads horizontally instead of vertically. This is used to cross-cross
414
	 * check a vertical cross check and locate the real center of the alignment pattern.</p>
415
	 */
416
	private function crossCheckHorizontal(int $startJ, int $centerI, int $maxCount, int $originalStateCountTotal):?float{
417
		$maxJ       = $this->bitMatrix->getDimension();
418
		$stateCount = $this->getCrossCheckStateCount();
419
420
		$j = $startJ;
421
		while($j >= 0 && $this->bitMatrix->get($j, $centerI)){
422
			$stateCount[2]++;
423
			$j--;
424
		}
425
426
		if($j < 0){
427
			return null;
428
		}
429
430
		while($j >= 0 && !$this->bitMatrix->get($j, $centerI) && $stateCount[1] <= $maxCount){
431
			$stateCount[1]++;
432
			$j--;
433
		}
434
435
		if($j < 0 || $stateCount[1] > $maxCount){
436
			return null;
437
		}
438
439
		while($j >= 0 && $this->bitMatrix->get($j, $centerI) && $stateCount[0] <= $maxCount){
440
			$stateCount[0]++;
441
			$j--;
442
		}
443
444
		if($stateCount[0] > $maxCount){
445
			return null;
446
		}
447
448
		$j = $startJ + 1;
449
		while($j < $maxJ && $this->bitMatrix->get($j, $centerI)){
450
			$stateCount[2]++;
451
			$j++;
452
		}
453
454
		if($j === $maxJ){
455
			return null;
456
		}
457
458
		while($j < $maxJ && !$this->bitMatrix->get($j, $centerI) && $stateCount[3] < $maxCount){
459
			$stateCount[3]++;
460
			$j++;
461
		}
462
463
		if($j === $maxJ || $stateCount[3] >= $maxCount){
464
			return null;
465
		}
466
467
		while($j < $maxJ && $this->bitMatrix->get($j, $centerI) && $stateCount[4] < $maxCount){
468
			$stateCount[4]++;
469
			$j++;
470
		}
471
472
		if($stateCount[4] >= $maxCount){
473
			return null;
474
		}
475
476
		// If we found a finder-pattern-like section, but its size is significantly different than
477
		// the original, assume it's a false positive
478
		$stateCountTotal = $stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4];
479
480
		if(5 * abs($stateCountTotal - $originalStateCountTotal) >= $originalStateCountTotal){
481
			return null;
482
		}
483
484
		if(!$this->foundPatternCross($stateCount)){
485
			return null;
486
		}
487
488
		return $this->centerFromEnd($stateCount, $j);
489
	}
490
491
	/**
492
	 * <p>This is called when a horizontal scan finds a possible alignment pattern. It will
493
	 * cross check with a vertical scan, and if successful, will, ah, cross-cross-check
494
	 * with another horizontal scan. This is needed primarily to locate the real horizontal
495
	 * center of the pattern in cases of extreme skew.
496
	 * And then we cross-cross-cross check with another diagonal scan.</p>
497
	 *
498
	 * <p>If that succeeds the finder pattern location is added to a list that tracks
499
	 * the number of times each location has been nearly-matched as a finder pattern.
500
	 * Each additional find is more evidence that the location is in fact a finder
501
	 * pattern center
502
	 *
503
	 * @param int[] $stateCount reading state module counts from horizontal scan
504
	 * @param int   $i          row where finder pattern may be found
505
	 * @param int   $j          end of possible finder pattern in row
506
	 *
507
	 * @return bool if a finder pattern candidate was found this time
508
	 */
509
	private function handlePossibleCenter(array $stateCount, int $i, int $j):bool{
510
		$stateCountTotal = $stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4];
511
		$centerJ         = $this->centerFromEnd($stateCount, $j);
512
		$centerI         = $this->crossCheckVertical($i, (int)$centerJ, $stateCount[2], $stateCountTotal);
513
514
		if($centerI !== null){
515
			// Re-cross check
516
			$centerJ = $this->crossCheckHorizontal((int)$centerJ, (int)$centerI, $stateCount[2], $stateCountTotal);
517
			if($centerJ !== null && ($this->crossCheckDiagonal((int)$centerI, (int)$centerJ))){
518
				$estimatedModuleSize = $stateCountTotal / 7.0;
519
				$found               = false;
520
521
				for($index = 0; $index < count($this->possibleCenters); $index++){
0 ignored issues
show
Performance Best Practice introduced by
It seems like you are calling the size function count() as part of the test condition. You might want to compute the size beforehand, and not on each iteration.

If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration:

for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}

// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
Loading history...
522
					$center = $this->possibleCenters[$index];
523
					// Look for about the same center and module size:
524
					if($center->aboutEquals($estimatedModuleSize, $centerI, $centerJ)){
525
						$this->possibleCenters[$index] = $center->combineEstimate($centerI, $centerJ, $estimatedModuleSize);
526
						$found                         = true;
527
						break;
528
					}
529
				}
530
531
				if(!$found){
532
					$point                   = new FinderPattern($centerJ, $centerI, $estimatedModuleSize);
533
					$this->possibleCenters[] = $point;
534
				}
535
536
				return true;
537
			}
538
		}
539
540
		return false;
541
	}
542
543
	/**
544
	 * @return int number of rows we could safely skip during scanning, based on the first
545
	 *         two finder patterns that have been located. In some cases their position will
546
	 *         allow us to infer that the third pattern must lie below a certain point farther
547
	 *         down in the image.
548
	 */
549
	private function findRowSkip():int{
550
		$max = count($this->possibleCenters);
551
552
		if($max <= 1){
553
			return 0;
554
		}
555
556
		$firstConfirmedCenter = null;
557
558
		foreach($this->possibleCenters as $center){
559
560
			if($center->getCount() >= self::CENTER_QUORUM){
561
562
				if($firstConfirmedCenter === null){
563
					$firstConfirmedCenter = $center;
564
				}
565
				else{
566
					// We have two confirmed centers
567
					// How far down can we skip before resuming looking for the next
568
					// pattern? In the worst case, only the difference between the
569
					// difference in the x / y coordinates of the two centers.
570
					// This is the case where you find top left last.
571
					$this->hasSkipped = true;
572
573
					return (int)((abs($firstConfirmedCenter->getX() - $center->getX()) -
0 ignored issues
show
Bug introduced by
The method getX() does not exist on null. ( Ignorable by Annotation )

If this is a false-positive, you can also ignore this issue in your code via the ignore-call  annotation

573
					return (int)((abs($firstConfirmedCenter->/** @scrutinizer ignore-call */ getX() - $center->getX()) -

This check looks for calls to methods that do not seem to exist on a given type. It looks for the method on the type itself as well as in inherited classes or implemented interfaces.

This is most likely a typographical error or the method has been renamed.

Loading history...
574
					              abs($firstConfirmedCenter->getY() - $center->getY())) / 2);
575
				}
576
			}
577
		}
578
579
		return 0;
580
	}
581
582
	/**
583
	 * @return bool true if we have found at least 3 finder patterns that have been detected
584
	 *              at least {@link #CENTER_QUORUM} times each, and, the estimated module size of the
585
	 *              candidates is "pretty similar"
586
	 */
587
	private function haveMultiplyConfirmedCenters():bool{
588
		$confirmedCount  = 0;
589
		$totalModuleSize = 0.0;
590
		$max             = count($this->possibleCenters);
591
592
		foreach($this->possibleCenters as $pattern){
593
			if($pattern->getCount() >= self::CENTER_QUORUM){
594
				$confirmedCount++;
595
				$totalModuleSize += $pattern->getEstimatedModuleSize();
596
			}
597
		}
598
599
		if($confirmedCount < 3){
600
			return false;
601
		}
602
		// OK, we have at least 3 confirmed centers, but, it's possible that one is a "false positive"
603
		// and that we need to keep looking. We detect this by asking if the estimated module sizes
604
		// vary too much. We arbitrarily say that when the total deviation from average exceeds
605
		// 5% of the total module size estimates, it's too much.
606
		$average        = $totalModuleSize / (float)$max;
607
		$totalDeviation = 0.0;
608
609
		foreach($this->possibleCenters as $pattern){
610
			$totalDeviation += abs($pattern->getEstimatedModuleSize() - $average);
611
		}
612
613
		return $totalDeviation <= 0.05 * $totalModuleSize;
614
	}
615
616
	/**
617
	 * @return \chillerlan\QRCode\Detector\FinderPattern[] the 3 best {@link FinderPattern}s from our list of candidates. The "best" are
618
	 *         those that have been detected at least {@link #CENTER_QUORUM} times, and whose module
619
	 *         size differs from the average among those patterns the least
620
	 * @throws \RuntimeException if 3 such finder patterns do not exist
621
	 */
622
	private function selectBestPatterns():array{
623
		$startSize = count($this->possibleCenters);
624
625
		if($startSize < 3){
626
			throw new RuntimeException('could not find enough finder patterns');
627
		}
628
629
		usort(
630
			$this->possibleCenters,
631
			fn(FinderPattern $a, FinderPattern $b) => $a->getEstimatedModuleSize() <=> $b->getEstimatedModuleSize()
632
		);
633
634
		$distortion   = PHP_FLOAT_MAX;
635
		$bestPatterns = [];
636
637
		for($i = 0; $i < $startSize - 2; $i++){
638
			$fpi           = $this->possibleCenters[$i];
639
			$minModuleSize = $fpi->getEstimatedModuleSize();
640
641
			for($j = $i + 1; $j < $startSize - 1; $j++){
642
				$fpj      = $this->possibleCenters[$j];
643
				$squares0 = $fpi->getSquaredDistance($fpj);
644
645
				for($k = $j + 1; $k < $startSize; $k++){
646
					$fpk           = $this->possibleCenters[$k];
647
					$maxModuleSize = $fpk->getEstimatedModuleSize();
648
649
					// module size is not similar
650
					if($maxModuleSize > $minModuleSize * 1.4){
651
						continue;
652
					}
653
654
					$a = $squares0;
655
					$b = $fpj->getSquaredDistance($fpk);
656
					$c = $fpi->getSquaredDistance($fpk);
657
658
					// sorts ascending - inlined
659
					if($a < $b){
660
						if($b > $c){
661
							if($a < $c){
662
								$temp = $b;
663
								$b    = $c;
664
								$c    = $temp;
665
							}
666
							else{
667
								$temp = $a;
668
								$a    = $c;
669
								$c    = $b;
670
								$b    = $temp;
671
							}
672
						}
673
					}
674
					else{
675
						if($b < $c){
676
							if($a < $c){
677
								$temp = $a;
678
								$a    = $b;
679
								$b    = $temp;
680
							}
681
							else{
682
								$temp = $a;
683
								$a    = $b;
684
								$b    = $c;
685
								$c    = $temp;
686
							}
687
						}
688
						else{
689
							$temp = $a;
690
							$a    = $c;
691
							$c    = $temp;
692
						}
693
					}
694
695
					// a^2 + b^2 = c^2 (Pythagorean theorem), and a = b (isosceles triangle).
696
					// Since any right triangle satisfies the formula c^2 - b^2 - a^2 = 0,
697
					// we need to check both two equal sides separately.
698
					// The value of |c^2 - 2 * b^2| + |c^2 - 2 * a^2| increases as dissimilarity
699
					// from isosceles right triangle.
700
					$d = abs($c - 2 * $b) + abs($c - 2 * $a);
701
702
					if($d < $distortion){
703
						$distortion   = $d;
704
						$bestPatterns = [$fpi, $fpj, $fpk];
705
					}
706
				}
707
			}
708
		}
709
710
		if($distortion === PHP_FLOAT_MAX){
711
			throw new RuntimeException('finder patterns may be too distorted');
712
		}
713
714
		return $bestPatterns;
715
	}
716
717
	/**
718
	 * Orders an array of three ResultPoints in an order [A,B,C] such that AB is less than AC
719
	 * and BC is less than AC, and the angle between BC and BA is less than 180 degrees.
720
	 *
721
	 * @param \chillerlan\QRCode\Detector\FinderPattern[] $patterns array of three FinderPattern to order
722
	 *
723
	 * @return \chillerlan\QRCode\Detector\FinderPattern[]
724
	 */
725
	private function orderBestPatterns(array $patterns):array{
726
727
		// Find distances between pattern centers
728
		$zeroOneDistance = $patterns[0]->getDistance($patterns[1]);
729
		$oneTwoDistance  = $patterns[1]->getDistance($patterns[2]);
730
		$zeroTwoDistance = $patterns[0]->getDistance($patterns[2]);
731
732
		// Assume one closest to other two is B; A and C will just be guesses at first
733
		if($oneTwoDistance >= $zeroOneDistance && $oneTwoDistance >= $zeroTwoDistance){
734
			[$pointB, $pointA, $pointC] = $patterns;
735
		}
736
		elseif($zeroTwoDistance >= $oneTwoDistance && $zeroTwoDistance >= $zeroOneDistance){
737
			[$pointA, $pointB, $pointC] = $patterns;
738
		}
739
		else{
740
			[$pointA, $pointC, $pointB] = $patterns;
741
		}
742
743
		// Use cross product to figure out whether A and C are correct or flipped.
744
		// This asks whether BC x BA has a positive z component, which is the arrangement
745
		// we want for A, B, C. If it's negative, then we've got it flipped around and
746
		// should swap A and C.
747
		if($this->crossProductZ($pointA, $pointB, $pointC) < 0.0){
748
			$temp   = $pointA;
749
			$pointA = $pointC;
750
			$pointC = $temp;
751
		}
752
753
		return [$pointA, $pointB, $pointC];
754
	}
755
756
	/**
757
	 * Returns the z component of the cross product between vectors BC and BA.
758
	 */
759
	private function crossProductZ(FinderPattern $pointA, FinderPattern $pointB, FinderPattern $pointC):float{
760
		$bX = $pointB->getX();
761
		$bY = $pointB->getY();
762
763
		return (($pointC->getX() - $bX) * ($pointA->getY() - $bY)) - (($pointC->getY() - $bY) * ($pointA->getX() - $bX));
764
	}
765
766
}
767