在二维列表中检测矩形(具有相同元素值的子数组) [英] Detecting rectangles (sub-arrays of same element value) in 2-d list

问题描述

将矩形定义为1s和0s的二维数组中零的任何矩形截面.典型示例:

A rectangle is defined as any rectangular-shaped section of zeros within a 2-d array of 1s and 0s. Typical example:

[
  [1, 1, 1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1, 1, 0],
  [1, 1, 1, 0, 0, 0, 1, 0, 0],
  [1, 0, 1, 0, 0, 0, 1, 0, 0],
  [1, 0, 1, 1, 1, 1, 1, 1, 1],
  [1, 0, 1, 0, 0, 1, 1, 1, 1],
  [1, 1, 1, 0, 0, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1, 1, 1],
]

在此示例中，有三个这样的数组:

In this example, there are three such arrays:

我的目标是确定每个数组的坐标(外部3个极端).

My goal is to determine the coordinates (outer 3 extremeties) of each array.

我首先将2-d list转换为numpy数组:

I start by converting the 2-d list into a numpy array:

image_as_np_array = np.array(two_d_list)

然后我可以得到所有零的坐标:

I can then get the coordinates of all the zeros thus:

np.argwhere(image_as_np_array == 0)

但这只是通过以下方式提供一种获取索引的捷径:遍历每行并调用.index()，然后将其与2-d列表中该行的索引合并.

But this merely provides a shortcut to getting the indices by iterating over each row and calling .index(), then combining with the index of that row within the 2-d list.

我现在想做些类似删除np.argwhere()(或np.where())中所有仅出现0的元素的事情(实际上忽略了不能构成行的一部分的任何行).矩形)，然后尝试对齐连续坐标，但是我一直想弄清楚如何处理任何行可能包含多个矩形中的一部分的情况(如上述第三行和第四行的情况).有numpy个功能或我可以利用的功能吗?

I envisage now doing something like removing any element of np.argwhere() (or np.where()) where there is only a single occurrence of a 0 (effectively disregarding any row that cannot form part of a rectangle), and then trying to align contiguous coordinates, but I'm stuck with figuring out how to handle cases where any row may contain part of more than just one single rectangle (as is the case in the 3rd and 4th rows above). Is there a numpy function or functions I can leverage?

推荐答案

我不知道numpy，所以这是一个简单的Python解决方案:

I don't know numpy, so here's a plain Python solution:

from collections import namedtuple

Rectangle = namedtuple("Rectangle", "top bottom left right")

def find_rectangles(arr):

    # Deeply copy the array so that it can be modified safely
    arr = [row[:] for row in arr]

    rectangles = []

    for top, row in enumerate(arr):
        start = 0

        # Look for rectangles whose top row is here
        while True:
            try:
                left = row.index(0, start)
            except ValueError:
                break

            # Set start to one past the last 0 in the contiguous line of 0s
            try:
                start = row.index(1, left)
            except ValueError:
                start = len(row)

            right = start - 1

            if (  # Width == 1
                  left == right or
                  # There are 0s above
                  top > 0 and not all(arr[top-1][left:right + 1])):
                continue

            bottom = top + 1
            while (bottom < len(arr) and
                   # No extra zeroes on the sides
                   (left == 0 or arr[bottom][left-1]) and
                   (right == len(row) - 1 or arr[bottom][right + 1]) and
                   # All zeroes in the row
                   not any(arr[bottom][left:right + 1])):
                bottom += 1

            # The loop ends when bottom has gone too far, so backtrack
            bottom -= 1

            if (  # Height == 1
                  bottom == top or
                  # There are 0s beneath
                  (bottom < len(arr) - 1 and
                   not all(arr[bottom + 1][left:right+1]))):
                continue

            rectangles.append(Rectangle(top, bottom, left, right))

            # Remove the rectangle so that it doesn't affect future searches
            for i in range(top, bottom+1):
                arr[i][left:right+1] = [1] * (right + 1 - left)

    return rectangles

对于给定的输入，输出为:

For the given input, the output is:

[Rectangle(top=2, bottom=3, left=3, right=5),
 Rectangle(top=5, bottom=6, left=3, right=4)]

这是正确的，因为注释指示不计入右边的矩形"，因为还会有额外的0伸出.我建议您尽管添加更多测试用例.

This is correct because the comments indicate that the 'rectangle' on the right is not to be counted since there is an extra 0 sticking out. I suggest you add more test cases though.

我希望它会相当快，因为​​许多低级迭代都是通过调用index和any完成的，因此即使没有numpy的帮助，C代码的使用也很不错.

I expect it to be reasonably fast since much of the low-level iteration is done with calls to index and any, so there's decent usage of C code even without the help of numpy.

这篇关于在二维列表中检测矩形(具有相同元素值的子数组)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！