Debian Codegraph @

vendor/chillerlan/php-qrcode/src/Detector/FinderPatternFinder.php

raw
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 declare(strict_types=1);
12
13 namespace chillerlan\QRCode\Detector;
14
15 use chillerlan\QRCode\Decoder\BitMatrix;
16 use function abs, count, intdiv, usort;
17 use const PHP_FLOAT_MAX;
18
19 /**
20 * This class attempts to find finder patterns in a QR Code. Finder patterns are the square
21 * markers at three corners of a QR Code.
22 *
23 * This class is thread-safe but not reentrant. Each thread must allocate its own object.
24 *
25 * @author Sean Owen
26 */
27 final class FinderPatternFinder{
28
29 private const MIN_SKIP = 2;
30 private const MAX_MODULES = 177; // 1 pixel/module times 3 modules/center
31 private const CENTER_QUORUM = 2; // support up to version 10 for mobile clients
32 /** @var int[] */
33 private const crossCheckStateCount = [0, 0, 0, 0, 0];
34 private BitMatrix $matrix;
35 /** @var \chillerlan\QRCode\Detector\FinderPattern[] */
36 private array $possibleCenters;
37 private bool $hasSkipped = false;
38
39 /**
40 * Creates a finder that will search the image for three finder patterns.
41 *
42 * @param BitMatrix $matrix image to search
43 */
44 public function __construct(BitMatrix $matrix){
45 $this->matrix = $matrix;
46 $this->possibleCenters = [];
47 }
48
49 /**
50 * @return \chillerlan\QRCode\Detector\FinderPattern[]
51 */
52 public function find():array{
53 $dimension = $this->matrix->getSize();
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 = intdiv((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 = self::crossCheckStateCount;
71 $currentState = 0;
72
73 for($j = 0; $j < $dimension; $j++){
74
75 // Black pixel
76 if($this->matrix->check($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 = self::crossCheckStateCount;
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 * @param int[] $stateCount
165 *
166 * @return int[]
167 */
168 private function doShiftCounts2(array $stateCount):array{
169 $stateCount[0] = $stateCount[2];
170 $stateCount[1] = $stateCount[3];
171 $stateCount[2] = $stateCount[4];
172 $stateCount[3] = 1;
173 $stateCount[4] = 0;
174
175 return $stateCount;
176 }
177
178 /**
179 * Given a count of black/white/black/white/black pixels just seen and an end position,
180 * figures the location of the center of this run.
181 *
182 * @param int[] $stateCount
183 */
184 private function centerFromEnd(array $stateCount, int $end):float{
185 return (float)(($end - $stateCount[4] - $stateCount[3]) - $stateCount[2] / 2);
186 }
187
188 /**
189 * @param int[] $stateCount
190 */
191 private function foundPatternCross(array $stateCount):bool{
192 // Allow less than 50% variance from 1-1-3-1-1 proportions
193 return $this->foundPatternVariance($stateCount, 2.0);
194 }
195
196 /**
197 * @param int[] $stateCount
198 */
199 private function foundPatternDiagonal(array $stateCount):bool{
200 // Allow less than 75% variance from 1-1-3-1-1 proportions
201 return $this->foundPatternVariance($stateCount, 1.333);
202 }
203
204 /**
205 * @param int[] $stateCount count of black/white/black/white/black pixels just read
206 *
207 * @return bool true if the proportions of the counts is close enough to the 1/1/3/1/1 ratios
208 * used by finder patterns to be considered a match
209 */
210 private function foundPatternVariance(array $stateCount, float $variance):bool{
211 $totalModuleSize = 0;
212
213 for($i = 0; $i < 5; $i++){
214 $count = $stateCount[$i];
215
216 if($count === 0){
217 return false;
218 }
219
220 $totalModuleSize += $count;
221 }
222
223 if($totalModuleSize < 7){
224 return false;
225 }
226
227 $moduleSize = ($totalModuleSize / 7.0);
228 $maxVariance = ($moduleSize / $variance);
229
230 return
231 abs($moduleSize - $stateCount[0]) < $maxVariance
232 && abs($moduleSize - $stateCount[1]) < $maxVariance
233 && abs(3.0 * $moduleSize - $stateCount[2]) < (3 * $maxVariance)
234 && abs($moduleSize - $stateCount[3]) < $maxVariance
235 && abs($moduleSize - $stateCount[4]) < $maxVariance;
236 }
237
238 /**
239 * After a vertical and horizontal scan finds a potential finder pattern, this method
240 * "cross-cross-cross-checks" by scanning down diagonally through the center of the possible
241 * finder pattern to see if the same proportion is detected.
242 *
243 * @param int $centerI row where a finder pattern was detected
244 * @param int $centerJ center of the section that appears to cross a finder pattern
245 *
246 * @return bool true if proportions are withing expected limits
247 */
248 private function crossCheckDiagonal(int $centerI, int $centerJ):bool{
249 $stateCount = self::crossCheckStateCount;
250
251 // Start counting up, left from center finding black center mass
252 $i = 0;
253
254 while($centerI >= $i && $centerJ >= $i && $this->matrix->check(($centerJ - $i), ($centerI - $i))){
255 $stateCount[2]++;
256 $i++;
257 }
258
259 if($stateCount[2] === 0){
260 return false;
261 }
262
263 // Continue up, left finding white space
264 while($centerI >= $i && $centerJ >= $i && !$this->matrix->check(($centerJ - $i), ($centerI - $i))){
265 $stateCount[1]++;
266 $i++;
267 }
268
269 if($stateCount[1] === 0){
270 return false;
271 }
272
273 // Continue up, left finding black border
274 while($centerI >= $i && $centerJ >= $i && $this->matrix->check(($centerJ - $i), ($centerI - $i))){
275 $stateCount[0]++;
276 $i++;
277 }
278
279 if($stateCount[0] === 0){
280 return false;
281 }
282
283 $dimension = $this->matrix->getSize();
284
285 // Now also count down, right from center
286 $i = 1;
287 // phpcs:ignore
288 while(($centerI + $i) < $dimension && ($centerJ + $i) < $dimension && $this->matrix->check(($centerJ + $i), ($centerI + $i))){
289 $stateCount[2]++;
290 $i++;
291 }
292
293 // phpcs:ignore
294 while(($centerI + $i) < $dimension && ($centerJ + $i) < $dimension && !$this->matrix->check(($centerJ + $i), ($centerI + $i))){
295 $stateCount[3]++;
296 $i++;
297 }
298
299 if($stateCount[3] === 0){
300 return false;
301 }
302
303 // phpcs:ignore
304 while(($centerI + $i) < $dimension && ($centerJ + $i) < $dimension && $this->matrix->check(($centerJ + $i), ($centerI + $i))){
305 $stateCount[4]++;
306 $i++;
307 }
308
309 if($stateCount[4] === 0){
310 return false;
311 }
312
313 return $this->foundPatternDiagonal($stateCount);
314 }
315
316 /**
317 * After a horizontal scan finds a potential finder pattern, this method
318 * "cross-checks" by scanning down vertically through the center of the possible
319 * finder pattern to see if the same proportion is detected.
320 *
321 * $startI row where a finder pattern was detected
322 * $centerJ center of the section that appears to cross a finder pattern
323 * $maxCount maximum reasonable number of modules that should be
324 * observed in any reading state, based on the results of the horizontal scan
325 * $originalStateCountTotal
326 *
327 * returns vertical center of finder pattern, or null if not found
328 *
329 * @noinspection DuplicatedCode
330 */
331 private function crossCheckVertical(int $startI, int $centerJ, int $maxCount, int $originalStateCountTotal):float|null{
332 $maxI = $this->matrix->getSize();
333 $stateCount = self::crossCheckStateCount;
334
335 // Start counting up from center
336 $i = $startI;
337 while($i >= 0 && $this->matrix->check($centerJ, $i)){
338 $stateCount[2]++;
339 $i--;
340 }
341
342 if($i < 0){
343 return null;
344 }
345
346 while($i >= 0 && !$this->matrix->check($centerJ, $i) && $stateCount[1] <= $maxCount){
347 $stateCount[1]++;
348 $i--;
349 }
350
351 // If already too many modules in this state or ran off the edge:
352 if($i < 0 || $stateCount[1] > $maxCount){
353 return null;
354 }
355
356 while($i >= 0 && $this->matrix->check($centerJ, $i) && $stateCount[0] <= $maxCount){
357 $stateCount[0]++;
358 $i--;
359 }
360
361 if($stateCount[0] > $maxCount){
362 return null;
363 }
364
365 // Now also count down from center
366 $i = ($startI + 1);
367 while($i < $maxI && $this->matrix->check($centerJ, $i)){
368 $stateCount[2]++;
369 $i++;
370 }
371
372 if($i === $maxI){
373 return null;
374 }
375
376 while($i < $maxI && !$this->matrix->check($centerJ, $i) && $stateCount[3] < $maxCount){
377 $stateCount[3]++;
378 $i++;
379 }
380
381 if($i === $maxI || $stateCount[3] >= $maxCount){
382 return null;
383 }
384
385 while($i < $maxI && $this->matrix->check($centerJ, $i) && $stateCount[4] < $maxCount){
386 $stateCount[4]++;
387 $i++;
388 }
389
390 if($stateCount[4] >= $maxCount){
391 return null;
392 }
393
394 // If we found a finder-pattern-like section, but its size is more than 40% different from
395 // the original, assume it's a false positive
396 $stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4]);
397
398 if((5 * abs($stateCountTotal - $originalStateCountTotal)) >= (2 * $originalStateCountTotal)){
399 return null;
400 }
401
402 if(!$this->foundPatternCross($stateCount)){
403 return null;
404 }
405
406 return $this->centerFromEnd($stateCount, $i);
407 }
408
409 /**
410 * Like #crossCheckVertical(int, int, int, int), and in fact is basically identical,
411 * except it reads horizontally instead of vertically. This is used to cross-cross
412 * check a vertical cross-check and locate the real center of the alignment pattern.
413 * @noinspection DuplicatedCode
414 */
415 private function crossCheckHorizontal(int $startJ, int $centerI, int $maxCount, int $originalStateCountTotal):float|null{
416 $maxJ = $this->matrix->getSize();
417 $stateCount = self::crossCheckStateCount;
418
419 $j = $startJ;
420 while($j >= 0 && $this->matrix->check($j, $centerI)){
421 $stateCount[2]++;
422 $j--;
423 }
424
425 if($j < 0){
426 return null;
427 }
428
429 while($j >= 0 && !$this->matrix->check($j, $centerI) && $stateCount[1] <= $maxCount){
430 $stateCount[1]++;
431 $j--;
432 }
433
434 if($j < 0 || $stateCount[1] > $maxCount){
435 return null;
436 }
437
438 while($j >= 0 && $this->matrix->check($j, $centerI) && $stateCount[0] <= $maxCount){
439 $stateCount[0]++;
440 $j--;
441 }
442
443 if($stateCount[0] > $maxCount){
444 return null;
445 }
446
447 $j = ($startJ + 1);
448 while($j < $maxJ && $this->matrix->check($j, $centerI)){
449 $stateCount[2]++;
450 $j++;
451 }
452
453 if($j === $maxJ){
454 return null;
455 }
456
457 while($j < $maxJ && !$this->matrix->check($j, $centerI) && $stateCount[3] < $maxCount){
458 $stateCount[3]++;
459 $j++;
460 }
461
462 if($j === $maxJ || $stateCount[3] >= $maxCount){
463 return null;
464 }
465
466 while($j < $maxJ && $this->matrix->check($j, $centerI) && $stateCount[4] < $maxCount){
467 $stateCount[4]++;
468 $j++;
469 }
470
471 if($stateCount[4] >= $maxCount){
472 return null;
473 }
474
475 // If we found a finder-pattern-like section, but its size is significantly different from
476 // the original, assume it's a false positive
477 $stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4]);
478
479 if((5 * abs($stateCountTotal - $originalStateCountTotal)) >= $originalStateCountTotal){
480 return null;
481 }
482
483 if(!$this->foundPatternCross($stateCount)){
484 return null;
485 }
486
487 return $this->centerFromEnd($stateCount, $j);
488 }
489
490 /**
491 * This is called when a horizontal scan finds a possible alignment pattern. It will
492 * cross-check with a vertical scan, and if successful, will, ah, cross-cross-check
493 * with another horizontal scan. This is needed primarily to locate the real horizontal
494 * center of the pattern in cases of extreme skew.
495 * And then we cross-cross-cross check with another diagonal scan.
496 *
497 * If that succeeds the finder pattern location is added to a list that tracks
498 * the number of times each location has been nearly-matched as a finder pattern.
499 * Each additional find is more evidence that the location is in fact a finder
500 * pattern center
501 *
502 * @param int[] $stateCount reading state module counts from horizontal scan
503 * @param int $i row where finder pattern may be found
504 * @param int $j end of possible finder pattern in row
505 *
506 * @return bool if a finder pattern candidate was found this time
507 */
508 private function handlePossibleCenter(array $stateCount, int $i, int $j):bool{
509 $stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4]);
510 $centerJ = $this->centerFromEnd($stateCount, $j);
511 $centerI = $this->crossCheckVertical($i, (int)$centerJ, $stateCount[2], $stateCountTotal);
512
513 if($centerI !== null){
514 // Re-cross check
515 $centerJ = $this->crossCheckHorizontal((int)$centerJ, (int)$centerI, $stateCount[2], $stateCountTotal);
516 if($centerJ !== null && ($this->crossCheckDiagonal((int)$centerI, (int)$centerJ))){
517 $estimatedModuleSize = ($stateCountTotal / 7.0);
518 $found = false;
519
520 // cautious (was in for fool in which $this->possibleCenters is updated)
521 $count = count($this->possibleCenters);
522
523 for($index = 0; $index < $count; $index++){
524 $center = $this->possibleCenters[$index];
525 // Look for about the same center and module size:
526 if($center->aboutEquals($estimatedModuleSize, $centerI, $centerJ)){
527 $this->possibleCenters[$index] = $center->combineEstimate($centerI, $centerJ, $estimatedModuleSize);
528 $found = true;
529 break;
530 }
531 }
532
533 if(!$found){
534 $point = new FinderPattern($centerJ, $centerI, $estimatedModuleSize);
535 $this->possibleCenters[] = $point;
536 }
537
538 return true;
539 }
540 }
541
542 return false;
543 }
544
545 /**
546 * @return int number of rows we could safely skip during scanning, based on the first
547 * two finder patterns that have been located. In some cases their position will
548 * allow us to infer that the third pattern must lie below a certain point farther
549 * down in the image.
550 */
551 private function findRowSkip():int{
552 $max = count($this->possibleCenters);
553
554 if($max <= 1){
555 return 0;
556 }
557
558 $firstConfirmedCenter = null;
559
560 foreach($this->possibleCenters as $center){
561
562 if($center->getCount() >= self::CENTER_QUORUM){
563
564 if($firstConfirmedCenter === null){
565 $firstConfirmedCenter = $center;
566 }
567 else{
568 // We have two confirmed centers
569 // How far down can we skip before resuming looking for the next
570 // pattern? In the worst case, only the difference between the
571 // difference in the x / y coordinates of the two centers.
572 // This is the case where you find top left last.
573 $this->hasSkipped = true;
574
575 return (int)((abs($firstConfirmedCenter->getX() - $center->getX()) -
576 abs($firstConfirmedCenter->getY() - $center->getY())) / 2);
577 }
578 }
579 }
580
581 return 0;
582 }
583
584 /**
585 * @return bool true if we have found at least 3 finder patterns that have been detected
586 * at least #CENTER_QUORUM times each, and, the estimated module size of the
587 * candidates is "pretty similar"
588 */
589 private function haveMultiplyConfirmedCenters():bool{
590 $confirmedCount = 0;
591 $totalModuleSize = 0.0;
592 $max = count($this->possibleCenters);
593
594 foreach($this->possibleCenters as $pattern){
595 if($pattern->getCount() >= self::CENTER_QUORUM){
596 $confirmedCount++;
597 $totalModuleSize += $pattern->getEstimatedModuleSize();
598 }
599 }
600
601 if($confirmedCount < 3){
602 return false;
603 }
604 // OK, we have at least 3 confirmed centers, but, it's possible that one is a "false positive"
605 // and that we need to keep looking. We detect this by asking if the estimated module sizes
606 // vary too much. We arbitrarily say that when the total deviation from average exceeds
607 // 5% of the total module size estimates, it's too much.
608 $average = ($totalModuleSize / (float)$max);
609 $totalDeviation = 0.0;
610
611 foreach($this->possibleCenters as $pattern){
612 $totalDeviation += abs($pattern->getEstimatedModuleSize() - $average);
613 }
614
615 return $totalDeviation <= (0.05 * $totalModuleSize);
616 }
617
618 /**
619 * @return \chillerlan\QRCode\Detector\FinderPattern[] the 3 best FinderPatterns from our list of candidates. The "best" are
620 * those that have been detected at least #CENTER_QUORUM times, and whose module
621 * size differs from the average among those patterns the least
622 * @throws \chillerlan\QRCode\Detector\QRCodeDetectorException if 3 such finder patterns do not exist
623 */
624 private function selectBestPatterns():array{
625 $startSize = count($this->possibleCenters);
626
627 if($startSize < 3){
628 throw new QRCodeDetectorException('could not find enough finder patterns');
629 }
630
631 usort(
632 $this->possibleCenters,
633 fn(FinderPattern $a, FinderPattern $b) => ($a->getEstimatedModuleSize() <=> $b->getEstimatedModuleSize()),
634 );
635
636 $distortion = PHP_FLOAT_MAX;
637 $bestPatterns = [];
638
639 for($i = 0; $i < ($startSize - 2); $i++){
640 $fpi = $this->possibleCenters[$i];
641 $minModuleSize = $fpi->getEstimatedModuleSize();
642
643 for($j = ($i + 1); $j < ($startSize - 1); $j++){
644 $fpj = $this->possibleCenters[$j];
645 $squares0 = $fpi->getSquaredDistance($fpj);
646
647 for($k = ($j + 1); $k < $startSize; $k++){
648 $fpk = $this->possibleCenters[$k];
649 $maxModuleSize = $fpk->getEstimatedModuleSize();
650
651 // module size is not similar
652 if($maxModuleSize > ($minModuleSize * 1.4)){
653 continue;
654 }
655
656 $a = $squares0;
657 $b = $fpj->getSquaredDistance($fpk);
658 $c = $fpi->getSquaredDistance($fpk);
659
660 // sorts ascending - inlined
661 if($a < $b){
662 if($b > $c){
663 if($a < $c){
664 $temp = $b;
665 $b = $c;
666 $c = $temp;
667 }
668 else{
669 $temp = $a;
670 $a = $c;
671 $c = $b;
672 $b = $temp;
673 }
674 }
675 }
676 else{
677 if($b < $c){
678 if($a < $c){
679 $temp = $a;
680 $a = $b;
681 $b = $temp;
682 }
683 else{
684 $temp = $a;
685 $a = $b;
686 $b = $c;
687 $c = $temp;
688 }
689 }
690 else{
691 $temp = $a;
692 $a = $c;
693 $c = $temp;
694 }
695 }
696
697 // a^2 + b^2 = c^2 (Pythagorean theorem), and a = b (isosceles triangle).
698 // Since any right triangle satisfies the formula c^2 - b^2 - a^2 = 0,
699 // we need to check both two equal sides separately.
700 // The value of |c^2 - 2 * b^2| + |c^2 - 2 * a^2| increases as dissimilarity
701 // from isosceles right triangle.
702 $d = (abs($c - 2 * $b) + abs($c - 2 * $a));
703
704 if($d < $distortion){
705 $distortion = $d;
706 $bestPatterns = [$fpi, $fpj, $fpk];
707 }
708 }
709 }
710 }
711
712 if($distortion === PHP_FLOAT_MAX){
713 throw new QRCodeDetectorException('finder patterns may be too distorted');
714 }
715
716 return $bestPatterns;
717 }
718
719 /**
720 * Orders an array of three ResultPoints in an order [A,B,C] such that AB is less than AC
721 * and BC is less than AC, and the angle between BC and BA is less than 180 degrees.
722 *
723 * @param \chillerlan\QRCode\Detector\FinderPattern[] $patterns array of three FinderPattern to order
724 *
725 * @return \chillerlan\QRCode\Detector\FinderPattern[]
726 */
727 private function orderBestPatterns(array $patterns):array{
728
729 // Find distances between pattern centers
730 $zeroOneDistance = $patterns[0]->getDistance($patterns[1]);
731 $oneTwoDistance = $patterns[1]->getDistance($patterns[2]);
732 $zeroTwoDistance = $patterns[0]->getDistance($patterns[2]);
733
734 // Assume one closest to other two is B; A and C will just be guesses at first
735 if($oneTwoDistance >= $zeroOneDistance && $oneTwoDistance >= $zeroTwoDistance){
736 [$pointB, $pointA, $pointC] = $patterns;
737 }
738 elseif($zeroTwoDistance >= $oneTwoDistance && $zeroTwoDistance >= $zeroOneDistance){
739 [$pointA, $pointB, $pointC] = $patterns;
740 }
741 else{
742 [$pointA, $pointC, $pointB] = $patterns;
743 }
744
745 // Use cross product to figure out whether A and C are correct or flipped.
746 // This asks whether BC x BA has a positive z component, which is the arrangement
747 // we want for A, B, C. If it's negative, then we've got it flipped around and
748 // should swap A and C.
749 if($this->crossProductZ($pointA, $pointB, $pointC) < 0.0){
750 $temp = $pointA;
751 $pointA = $pointC;
752 $pointC = $temp;
753 }
754
755 return [$pointA, $pointB, $pointC];
756 }
757
758 /**
759 * Returns the z component of the cross product between vectors BC and BA.
760 */
761 private function crossProductZ(FinderPattern $pointA, FinderPattern $pointB, FinderPattern $pointC):float{
762 $bX = $pointB->getX();
763 $bY = $pointB->getY();
764
765 return ((($pointC->getX() - $bX) * ($pointA->getY() - $bY)) - (($pointC->getY() - $bY) * ($pointA->getX() - $bX)));
766 }
767
768 }