public static function MatrixUtility::findMaxSumSubmatrix in Image Effects 8.2

Same name and namespace in other branches

1. 8.3 src/Component/MatrixUtility.php \Drupal\image_effects\Component\MatrixUtility::findMaxSumSubmatrix()
2. 8 src/Component/MatrixUtility.php \Drupal\image_effects\Component\MatrixUtility::findMaxSumSubmatrix()

Find the sum-matrix of a bi-dimensional matrix having the highest sum.

Parameters

array $matrix: A simple array of matrix rows values. Each row is a simple array of numeric values.

int $rows: The number of rows of the sub-matrix.

int $columns: The number of columns of the sub-matrix.

Return value

array A simple array with the following values:

• the row of the input matrix where the sub-matrix starts;
• the column of the input matrix where the sub-matrix starts;
• the value of the sum of the sub-matrix.

See also

https://stackoverflow.com/questions/39937212/maximum-subarray-of-size-hx...

2 calls to MatrixUtility::findMaxSumSubmatrix()

GDOperationTrait::getEntropyCropByGridding in src/Plugin/ImageToolkit/Operation/gd/GDOperationTrait.php

Computes the entropy crop of an image, using recursive gridding.

MatrixUtilityTest::testFindMaxSumSubmatrix in tests/src/Unit/MatrixUtilityTest.php

@covers ::findMaxSumSubmatrix @dataProvider findMaxSumSubmatrixProvider

File

src/Component/MatrixUtility.php, line 69

Class

MatrixUtility

Matrix handling methods for image_effects.

Namespace

Drupal\image_effects\Component

Code

public static function findMaxSumSubmatrix(array $matrix, $rows, $columns) {
  $matrix_rows = count($matrix);
  $matrix_columns = count($matrix[0]);
  $max_sum = 0;
  $max_sum_position = NULL;
  for ($r1 = 0; $r1 < $matrix_rows; $r1++) {
    for ($c1 = 0; $c1 < $matrix_columns; $c1++) {
      $r2 = $r1 + $rows - 1;
      $c2 = $c1 + $columns - 1;
      if ($r2 >= $matrix_rows || $c2 >= $matrix_columns) {
        continue;
      }
      if ($r1 == 0 && $c1 == 0) {
        $sub_sum = $matrix[$r2][$c2];
      }
      elseif ($r1 == 0) {
        $sub_sum = $matrix[$r2][$c2] - $matrix[$r2][$c1 - 1];
      }
      elseif ($c1 == 0) {
        $sub_sum = $matrix[$r2][$c2] - $matrix[$r1 - 1][$c2];
      }
      else {
        $sub_sum = $matrix[$r2][$c2] - $matrix[$r1 - 1][$c2] - $matrix[$r2][$c1 - 1] + $matrix[$r1 - 1][$c1 - 1];
      }
      if ($max_sum < $sub_sum) {
        $max_sum_position = [
          $r1,
          $c1,
          $sub_sum,
        ];
        $max_sum = $sub_sum;
      }
    }
  }
  return $max_sum_position;
}