7

以下是我今天遇到的一个视觉问题。这里的问题只是图片中有多少个正方形。

您将如何通过代码解决这样的问题？此外，如果不处理实际图片，您将如何对其进行建模？

方块拼图

PS：我觉得实际的分辨率需要一个规则来定义什么可以被视为正方形。类似于说边的长度相等并且可以由任意数量的线段组成，只要它们适合封闭的正方形。不过，我不确定您如何代表一个职位。

4

4 回答 4

1

如果您可以将其建模为矩阵，那么您需要的唯一信息就是顶点的位置。然后为每个顶点检查同一行中的所有顶点，并为每个找到的顶点检查它们的列。然后删除处理过的顶点。逐列执行相同的操作。最坏情况的复杂度是 n! （？）

我添加了代码以进行澄清。 

public class SqFinder {
        int calculateSquares(int[][] vertices, int n) {
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (vertices[i][j] == 1) {
                        for (int k = 1; k < n-j; k++) {
                            if (i + k < n && vertices[i][j+k] == 1 && vertices[i + k][j] == 1 && vertices[i + k][j + k] == 1)
                                count++;
                        }
                    }
                    vertices[i][j] =0;
                }
            }
            return count;
        }

        public static void main(String[] args) {
            SqFinder a = new SqFinder();
    //      int [][] test = {{1,1,1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1}};
            int [][] test = {{1,1,1},{1,1,1},{1,1,1}};
            System.out.println(a.calculateSquares(test, 3));
        }
    }
于 2012-07-25T02:10:53.487 回答
1

编码：你所拥有的是一个网络。将其编码为连接位于离散二维空间中的节点的网络。

问题实际上是要求您计算满足以下属性的路径数：

  1. 有3转
  2. 每个这样的转弯之间的长度是相等的
  3. 路径的起点和终点是相同的。

这种情况下的转折是（a）如果先前的移动导致 y 坐标发生变化，则该移动导致 x 坐标发生变化；或 (b) 如果先前的移动导致 x 坐标发生变化，则此移动会导致 y 坐标发生变化。

至于跟踪该过程：我在此页面上看到的最佳建议是简单地遍历每个节点，并为每个这样的节点检查所有可能的正方形大小。这应该避免进一步跟踪的需要。

如果你有一个更聪明的方法，只要你的路径总是左手或右手，每个正方形都由起始顶点和边长唯一标识。

于 2012-07-25T01:17:04.950 回答
1

最简单的方法是遍历每个顶点，并检查它是否可以是宽度为 1、宽度为 2、宽度为 3 等的正方形的左上角顶点。

于 2012-07-25T03:41:17.253 回答
0

这样的事情应该这样做：

int line_width = 1; //the width of the square line
int squares = 0;
for (int x = 0; x < width; ++x)
{
    for (int y = 0; y < height; ++y)
    {
        for (int size = line_width; x + size < width && y + size < height; ++x)
        {
            if (valid_square_at(x, y, x + size, y + size, line_width))
            {
                ++squares;
            }
        }
    }
}
return squares;

bool valid_square_at(x_0, y_0, x_1, y_1, width) 
{
    return valid_line(x_0, y_0, x_0_ x_1, width)
        && valid_line(x_0, y_0, x_1_ x_0, width)
        && valid_line(x_0, y_1, x_1_ x_1, width)
        && valid_line(x_1, y_0, x_1_ x_1, width);
}

bool valid_line(x_0, y_0, x_1, y_1, width) 
{
    //check that all pixel in that line are black...
}

基本上对于图片中的每个点，您检查每个可能大小的正方形，如果该大小的正方形从该像素开始。这很容易，因为你的方块都与边界“对齐”......问题是如果它们不是......

于 2012-07-25T02:05:34.427 回答