algorithm - 在任意二进制矩阵中查找仅包含零的圆

Question

给定一个任意大小的二进制矩阵，我需要找到适合该矩阵且仅覆盖“0”字段而不覆盖“-1”字段的圆。

对于这个例子

1 0 0 0 0 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 1 1

我想找到下面的最大圆(用+表示)

1 0 0 + 0 1 1
1 0 + + + 0 1
1 + + + + + 1
1 0 + + + 0 1
1 0 0 + 0 1 1

实际上这不是圆，只是它的近似值。可以借助直方图在这样的二进制矩阵中查找矩形，请参见 here .此外，我尝试找到像这样的小圆圈:

1 0 + 0 0 1 1                1 0 0 0 0 1 1
1 + + + 0 0 1                1 0 0 0 0 0 1
1 0 + 0 0 0 1   or this one  1 0 0 + 0 0 1
1 0 0 0 0 0 1                1 0 + + + 0 1
1 0 0 0 0 1 1                1 0 0 + 0 0 1

有没有人对如何识别这些圆圈(或其离散近似值)有聪明的想法(例如矩形的直方图方法)？

Answer 1

执行 nearest neighbour search ，对于每个 0 元素到 find the closest 1 元素，使用欧氏距离并创建另一个矩阵，存储每个元素到最近的 1 的距离(或者只跟踪最大的)。

可以容纳最大圆的空间将由与最近邻元素距离最大的元素给出，每个元素的距离将指定可以容纳以该元素为中心的空间的圆的大小(距离为 1，表示单个 +，距离为 2 表示一个简单的交叉等)。

请注意，这仅适用于以给定元素为中心的圆。它不会处理在一个元素和另一个元素之间居中的圆圈。