Markus Markus - 18 days ago 4
Python Question

How to find the coordinates of 2D rectangular array in another array

I have some 2D array of different values for example:

array = [[1, 1, 2, 5, 6, 1],
[5, 1, 1, 1, 6, 7],
[10, 12, 1, 1, 11, 11],
[8, 10, 1, 1, 1, 9],
6, 5, 10, 1, 15]]


and, I would like to find coordinates (upper left corner and bottom right corner) of the biggest rectangular array of same values and print them.

In this array are coordinates:

x=1, y=2
x=3, y=3


Any ideas?

Answer

You can use this algorithm:

  • Start at each x/y coordinate of the array.
  • Walk right and to the bottom as long as the value does not change.
  • Check at each step whether a new largest field with equal values has been found.

Here is the script. Note that I have added a 1 at the end of the last line of the array so that all entries have the same length. The variables x and y refer to the first and second array index, respectively, which correspond to line and column, respectively (not column and line!).

array =[[ 1,  1,  2,  5,  6,  1],
        [ 5,  1,  1,  1,  6,  7],
        [10, 12,  1,  1, 11, 11],
        [ 8, 10,  1,  1,  1,  9],
        [ 6,  5, 10,  1, 15,  1]]

xMax = len(array)
yMax = len(array[1])

maxSize = 0
for xUL in range(xMax):
    for yUL in range(yMax):

        valueRef = array[xUL][yUL]
        yBRMax = yMax

        for x in range(xUL, xMax):

            if (array[x][yUL] != valueRef):
                break

            for y in range(yUL, yBRMax):

                size = (y-yUL+1)*(x-xUL+1)

                if (array[x][y] != valueRef):
                    yBRMax = y
                    break
                else:
                    size = (y-yUL+1)*(x-xUL+1)
                    if (size > maxSize):
                        print("New max size: xUL: %d yUL: %d x: %d y %d size: %d" %(xUL, yUL, x, y, size))
                        maxSize = size
                        xMaxUL = xUL
                        yMaxUL = yUL
                        xMaxBR = x
                        yMaxBR = y

The following output is produced by running python3 max.py:

New max size: xUL: 0 yUL: 0 x: 0 y 0 size: 1
New max size: xUL: 0 yUL: 0 x: 0 y 1 size: 2
New max size: xUL: 1 yUL: 1 x: 1 y 3 size: 3
New max size: xUL: 1 yUL: 2 x: 2 y 3 size: 4
New max size: xUL: 1 yUL: 2 x: 3 y 3 size: 6
Comments